Предметом обсуждения, разумеется, станут алгоритмы, и удобно было бы начать с формального определения этого понятия. Но сделать это отнюдь не просто: нужно вникать в содержание весьма нетривиальной теории алгоритмов, а ее к вводному курсу уж никак не отнести.

Можно ли обойтись без определения, рассчитывая лишь на интуитивное представление читателя о сущности алгоритма? Пожалуй, настораживает излишняя популярность интересующего нас термина, и, как в таких случаях говорят, его расширительное толкование. Так, автору попадались "алгоритм шахматиста" (в книге), "алгоритм сбора информации" при социологическом опросе (в газетной публикации), и прочие.

Поэтому возьмем за основу представление об алгоритме как описании некоторого вычислительного процесса, а далее введем некоторые уточнения. Тем не менее, иллюстрацией нам часто будут служить примеры невычислительного характера, не связанные напрямую с компьютерной обработкой информации, за что читатель, надеюсь, нас не осудит.

Сначала - уточнения терминологические. Нередко, в целях экономии, сочетание "описание вычислительного процесса" мы будем заменять коротким "процесс", что не должно вводить читателя в заблуждение. В самом деле, мы чаще будем только конструировать алгоритмы, вовсе не стремясь тут же их применить. Кроме того, если алгоритм - это описание процесса, то способ представления алгоритма - это "описание описания процесса". Половину "описаний" так и хочется отбросить.

Итак, условимся, что и форма записи алгоритма, - формат, - и его содержание отнюдь не произвольны, а подчинены вполне определенным ограничениям.

Начнем с форматов записи, коих известно немало. Читатель, знакомый с технологией программирования, следует при записи алгоритма достаточно жестким правилам языка, - безразлично, какого. Вполне вероятно, что первые его уроки были посвящены языку блок-схем. Другую разновидность языка схем представляют весьма компактные диаграммы Насси-Шнейдермана. Оба графических формата обладают как достоинствами, так и недостатками, но здесь нет места их обсуждению. Общей же для всех графических форматов является возможность либо помещать текст описания внутрь блоков, либо выносить комментарий за пределы рисунка.

При всем многообразии способов записи алгоритма мы отдаем предпочтение "первичной" форме, а именно, словесному описанию. Разумеется, в этом варианте также прибегают к ряду обозначений, обычно вполне очевидных, в частности, - явной нумерации шагов. Альтернативой излишней краткости могут стать дополнительные комментарии.

В качестве иллюстрации - как "договаривались", не вычислительной - приведем алгоритмизированное описание беседы небезызвестного почтальона Печкина с Говорящим Галчонком.

Представить алгоритм без выходных данных затруднительно: зачем он тогда нужен? И все же рискнем. Вспомним миф о Сизифе: целью процесса было не закатывание камня на вершину горы, а наказание нечестивца.

Выше мы уже говорили о необходимости анализировать конструируемый алгоритм. Такой анализ должен дать четкое представление, во-первых, о емкостной и, во-вторых, о временной сложности процесса. Первая часть вполне ясна: речь идет о размерах памяти, в которой предстоит размещать все данные, участвующие в вычислительном процессе.

Предположим, алгоритм для решения некоторой задачи нам удалось построить. Раз так, что мешает предположить существование и другого алгоритма, и еще следующего? Но если удается сконструировать целый ряд различных алгоритмов решения одной и той же задачи, то кажется разумным - выбрать "наилучший". Что под этим следует понимать?

Обратимся к примерам.

Мы столько внимания уделили собственно возможности оценивать временную эффективность алгоритма, но пока даже не пытались выяснить, а насколько это нужно практически. В самом деле, вычислительный процесс, согласно сконструированному алгоритму, должен выполняться на современном компьютере, который, кажется нам, работает "довольно быстро".

Гораздо хуже обстоит дело с алгоритмами, трудоемкость которых составляет O(2n), O(nn), O(n!) и более. В этом перечне каждая очередная функция "перекрывает", при достаточно больших n, предыдущие функции того же ряда. Или, как говорят, мажорирует их. При том, любая из них мажорирует трудоемкость полиномиальную. Такие алгоритмы принято характеризовать как имеющие экспоненциальную сложность.

Классический способ приближенного вычисления числа p, вероятно, известен вам из школьного курса геометрии, но на всякий случай напоминаем его.

Постановка задачи, как правило, оставляет программисту возможность выбора пути для ее решения. Свидетельством тому служит разнообразие алгоритмических механизмов, включая не только упомянутые нами выше, но и некоторые другие. Возникают ли сомнения в том, что они должны входить в арсенал программиста?

Примем следующую формулировку: "вычислить по входным значениям пары натуральных чисел соответствующее выходное значение - их произведение".

Так, если мы расширим стандартную таблицу умножения до 15 строк и 26 столбцов, то интересующее нас произведение обнаружим в нижнем правом ее углу.

Возможно, Ваше знакомство с ЭВМ до сих пор не требовало знания устройства оперативной памяти. В таком случае, выясните, что собой представляет оперативная память как структура (размещения) данных?

Вновь обратимся к нашему модельному объекту - таблице умножения. Очевидно, что стандартные размеры этой структуры - 10´10 - продиктованы используемой системой счисления.

Если читателю не пришлось до сих пор сталкиваться с динамическими структурами в своей программистской практике, то желательно этот пробел ликвидировать и познакомиться с соответствующими конструкциями языка программирования.

Выбирается произвольное двузначное число и назначается первым элементом n₁ последовательности псевдослучайных чисел, а затем каждый очередной элемент n_i+1 получается из предыдущего элемента n_i

И вновь возвращаемся к обычному виду таблицы умножения. Вполне естественной выглядит обратная задача, связанная с установлением "адреса" в ней по заданному значению элемента:

Мы уже убедились, что место, занимаемое таблицей умножения избыточно, и вполне можно экономить его, используя альтернативные структуры. Вот еще одна из возможностей, реализуемая многошаговым алгоритмом:

Выучить наизусть таблицу степеней двойки:

Очевидно, чем меньше (больше) основание системы счисления, тем меньше (больше) диапазон представимых, - при одинаковом числе используемых разрядов, - чисел.

Продолжим теперь наше обсуждение позиционных систем счисления и рассмотрим особую разновидность позиционных нумераций с переменным основанием (ранее приводившиеся рассуждения относились к нумерациям с фиксированными основаниями - 2, 8, 10 и прочими).

Предположим, в нашем распоряжении гири в 1, 3, 9 граммов. Составьте таблицу размещения гирь на чашах весов, в соответствии с которой будет видно, как можно взвесить грузы от 0 до 13 граммов. Часть таблицы выглядит так:

В предыдущем занятии мы обсуждали уравновешенные системы счисления и выше приведена таблица соответствия записи первых 10 чисел в десятичной и пятеричной нумерациях, а также в 5-ричной системе счисления с симметричным основанием (это другое название уравновешенных систем счисления).

Что нам дают все эти рассуждения об операциях в уравновешенных системах счисления? Оказывается, понятие дополнение актуально и для "обычных" позиционных нумераций, когда речь идет об отрицательных числах.

Эти операции, как и арифметические, применяются либо к одному операнду (одноместные), либо к двум операндам (двуместные). Операнды могут принимать всего лишь 2 значения

Итак, все операции целочисленной арифметики удалось свести к работе логических элементов AND, NOT и OR и побитовому сдвигу содержимого регистра. Последнее же вполне может осуществляться аппаратно.

Всякий раз, когда мы решаем задачу и располагаем не единственным вариантом решения, естественно выбрать из них тот, который потребует меньшего объема работы. Вольно переиначивая известную сентенцию, можно сказать, что руководством к действию мы выбираем девиз "лень оправдывает средства".

Рассмотрим далее несколько стандартных алгоритмов, часто находящих применение при решении разнообразных задач.

Выше мы уже говорили о том, что понятие шаг алгоритма следует конкретизировать в каждом случае отдельно. В трех рассмотренных алгоритмах, очевидно, под шагом надо понимать реализацию оператора присваивания, включая в него, - в шаг, - все необходимые машинные операции.

Для заданного натурального числа установить местоположение младшего единичного бита.

В число важных задач дискретной математики и современного программирования входит разработка методов и программ шифрования информации. Одним из способов шифрования является использование т.н. перестановочных шифров. Обсуждение этой темы мы планируем в будущих занятиях, а сейчас рассмотрим частную задачу.

Проиллюстрируем механизм работы алгоритма на примере перевода числа 41210 в 6-ричную нумерацию. Как видим, он представляет собой обычное деление в столбик; получающиеся остатки и есть символы из разложения числа в новой нумерации

Применения последовательности (или ряда) Фибоначчи в математике и программировании чрезвычайно многообразны, но сейчас мы остановимся лишь на одном из них.

Из структур, используемых в алгоритмике, организация массивов представляется наиболее удобной для программирования. Это связано, во-первых, с возможностью прямого (непосредственного) логического доступа к любому элементу, без обращения к его "собратьям"

Компонента вектора, в свою очередь, может быть вектором, например, длины N. В этом случае обычной иллюстрацией (рис. E1-2) служит графическое представление массива в виде двумерной таблицы конечных размеров, нередко называемой матрицей.

Информация из школьного классного журнала размещается в трехмерном массиве: внешние компоненты - это страницы журнала, "средние" компоненты - строки на странице, и наконец, "внутренние" компоненты - оценки в строке.

Механизм последовательного перебора E1-1 находит применение нескольких базовых алгоритмах обработки векторов, в том числе, алгоритме поиска наибольшего (аналогично: наименьшего) элемента. Что касается массивов бОльших размерностей, то представление их в виде линейной развертки сохраняет, по сути, работоспособность того же механизма.

Учитывая важность алгоритма поиска максимума, о чем мы говорили еще в Главе D, запишем его первый вариант в общем виде, причем будем считать, что доступ к компоненте обеспечивает непосредственно получение ее ключевого значения item.