П.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
Начальные значения
x=x+y
y:=x-y
x:=x-y
Конечные значения

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

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

В качестве упражнения предлагаем читателям записать значение линейной комбинации в переменную 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. Конец.

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

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

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

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

Дата добавления: 2015-07-26