Лекция 8

Типовые алгоритмы

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

Большинство задач в вычислительной технике связано с группами чисел (ряд чисел, матрица чисел). Для удобства всю группу чисел принимают как единое целое, но, состоящее из нескольких элементов. Такую группу принято называть массив. Массив представляется как единая многоэлементная переменная. Как и любая переменная, массив имеет свое имя. Элементы массива также имеют то же, что и массив имя, но к нему добавляется индекс, который является порядковым номером элемента в составе массива. Следовательно, если группу из n чисел представить как массив с именем а, тогда отдельное число этого массива будет обозначаться как а_i. Здесь индекс i может принимать любое значение в интервале от 1 до n, то есть обозначать порядковый номер числа. Массивам для хранения чисел выделяются в оперативной памяти компьютера ячейки подряд. В большинстве приведенных алгоритмов используются параметрические циклы. У них параметр цикла имеет заданную область изменения (начальное и конечное значение). В таких циклах заголовок цикла представлен блоком модификация, в плоскости которого указывается имя параметра цикла, его область изменения и шаг.

1. Определение суммы чисел произвольного ряда

Дан: ряд произвольных чисел .

Определить: сумму этих чисел .

Алгоритм решения этой задачи приведен на рис.1.

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

Дело в том, что при решении какой-либо задачи всем данным, участвующим в операциях вычислительного процесса (исходным, промежуточным, конечным), выделяются ячейки оперативной памяти. После завершения программы данные в используемых ячейках автоматически не удаляются (не обнуляются). Если после этого на компьютере будет решаться другая задача, то для ее переменных могут быть выделены ячейки памяти, которые использовались в предыдущей задаче, с сохранившимися в них данными. В случае, когда решается задача по представленному алгоритму, переменной может быть выделена ячейка с "остатками" от предыдущей задачи (их еще называют "мусор"), и это может исказить результат решения. Во избежание этого ячейку памяти для переменной вначале очищают от "мусора", устанавливая значение 0. Можно вместо нуля устанавливать значение первого слагаемого (первого числа ряда), но тогда параметр цикла i должен изменяться не от единицы, а от 2.

Рис. 1 Блок – схема вычисления суммы ряда чисел

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