П.2.3. Типы алгоритмов

Любой сколь угодно сложный алгоритм составляется из трех основных типов, соединяемых в различных сочетаниях:

1. Следования (или линейный алгоритм).

2. Выбора (или ветвления).

3. Повторения (или циклический алгоритм).

Рассмотрим особенности этих стандартных алгоритмов на примерах.

Начало

Ввод х,y

S:=x+y

Вывод S

Начало

Ввод х

Вывод х

Конец

x<0?

Нет Да

х:=-х

Начало

S:=x+y

x:=1; S:=0

x=0?

Нет Да

Ввод х

S:=S+x

Вывод S

Конец

Алгоритм следования

Алгоритм выбора

Алгоритм повтора

Н

Конец

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

В центре представлен алгоритм выбора. Он характеризуется наличием ветвления и отсутствием возврата к ранее выполненным действиям. Если значение х неотрицательное, активен выход «Нет», и значение х не изменяется. Если значение х отрицательное, активен выход «Да», и меняется знак значения х. Этот алгоритм вычисляет модуль числа х.

Справа представлен алгоритм повтора. Его отличительной особенностью является наличие возврата к ранее выполненным действиям. Этот возврат всегда осуществляется через элемент ветвления, в противном случае говорят о «бесконечном» цикле, из которого нет выхода. Поэтому только по наличию элемента ветвления нельзя различить алгоритмы выбора и повтора. В данном алгоритме накалливается сумма введенных чисел, пока не будет введен 0.

Примечание. В математике знак «=» применяется для обозначения двух различных операций: а=5 может означать, что параметру а присвоено значение 5, а может означать сравнение значения параметра а с числом 5 на точное равенство. Человек различает эти операции по смыслу. Компьютеру непонятно, что такое «смысл», поэтому знак «=» используется для обозначения операции сравнения, а для операции присваивания применяется знак «:=».

П.2.4. Стандартные алгоритмы

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

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

Обмен значений двух переменных с использованием дополнительной переменной и линейными комбинациями заключается в следующем. Если надо поменять местами значения в переменных xиy, вводится дополнительная переменная, например,z. Далее выполняются три операции присваивания:z:=x; x:=y; y:=z.Переменнаяzнужна, чтобы сохранить на время значение одной (любой) переменной, чтобы на «освободившееся» в ней место записать значение другой переменной. Последовательность действий может быть и такой:z:=y; y:=x; x:=z.

Обмен значений двух переменных с помощью линейных комбинаций не требует дополнительной переменной и выполняется тремя действиями присваивания: x:=x+y; y:=x-y; x:=x-y.Рассмотрим таблицу значений дляxиy, получаемых на каждом шаге:

Шаг	Значение х	Значение y
Начальные значения	3	7
x=x+y	10	7
y:=x-y	10	3
x:=x-y	7	3
Конечные значения	7	3

На первом шаге можно выполнить не сложение, а вычитание:

Шаг	Значение х	Значение y
Начальные значения	3	7
x=x-y	-4	7
y:=x+y	-4	3
x:=y-х	7	3
Конечные значения	7	3

В качестве упражнения предлагаем читателям записать значение линейной комбинации в переменную y. Заметим, что нельзя применять операции умножения и деления (почему?).

Р

Начало

Ввод х,y,z

Вывод х,y,z

Конец

x>y?

Нет Да

Обмен значений

x и y

Начало

Ввод х,y

x>y?

Нет Да

Обмен значений

x и y

x>z?

Нет Да

Обмен значений

x и z

y>z?

Нет Да

Обмен значений

y и z

Вывод х,y

Конец

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

Слева представлен алгоритм для сортировки по не убыванию двух значений, справа – для трех значений. Для сортировки по не возрастанию надо заменить везде знаки сравнения противоположными. Эти же алгоритмы решают и другую задачу: вывести два (три) значения в порядке не убывания (или не возрастания). При этом количество сравнений определяется формулойN*(N-1)/2,гдеN– число элементов последовательности, и приN=4 будет равно 6, а сам алгоритм имеет регулярную последовательную структуру. Если такую задачу решать методом выделения и вывода экстремального значения по всем элементам, а затем выделять и выводить экстремальное значение среди остальных элементов, количество сравнений определится формулойN!=1*2*3*…*Nи приN=4 будет равно 24, а сам алгоритм будет иметь вид широкого дерева. Алгоритм, реализующий этот метод, здесь не представлен ввиду его трудоемкости и может явиться темой самостоятельных упражнений.

Алгоритм решения стандартной задачи накопления суммы чисел представлен в примере алгоритма повтора ранее. Для накопления произведения чисел в этом алгоритме надо заменить операцию сложения операцией умножения, а переменной Sприсвоить начальное значение, равное 1.

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

Среди задач, связанных с делимостью чисел нацело, особо важное место занимает задача нахождения наибольшего общего делителя (НОД) для двух натуральных чисел. Эту задачу можно решать методом перебора, то есть подозревать в каждом натуральном числе, начиная с 2 и заканчивая половиной максимального из заданных чисел, искомую величину. Те из проверяемых чисел, для которых хотя бы один остаток от деления заданных чисел на него не равен нулю, имеют алиби и не являются общими делителями. Среди остальных же, являющихся общими делителями, остается найти максимальное число. Для этого надо запоминать каждый новый делитель в одной и той же вспомогательной переменной (чем-то похоже на поиск экстремального значения?). Если же вести поиск общих делителей в обратном порядке, первый же найденный общий делитель окажется наибольшим, то есть искомым.

Однако быстрее можно найти НОД, используя алгоритм, известный еще со времен древней Греции. Этот алгоритм приведен ниже.

Алгоритм поиска НОД:

1. Начало.

2. Ввод значений xи y.

3. ЕслиxyТогда

Еслиx>y Тогдаx:=x-y

Иначеy:=y-x

Возврат к действию 3.

ИначеВывод значенияx.

4. Конец.

Если проверку на равенство проводить не в начале цикла, а в конце, при одинаковых исходных числах цикл окажется «бесконечным».

Поиск наименьшего общего кратного (НОК) для двух натуральных чисел можно также выполнить методом перебора. Последовательно проверять следует натуральные числа, начиная от наибольшего из заданных до произведения заданных чисел. Такое упражнение могут выполнить те, кто не уверен, что произведение НОД и НОК равно произведению заданных чисел.

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

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