Методы алгоритмизации расчетных задач

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

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

Ui =f (U_i-1)

где: Ui и U_i-1 - значения переменной U, вычисляемые

в i-й и (i -1) - й реализациях цикла.

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

ПРИМЕР 1. Составить блок-схему алгоритма вычисления и вывода на печать 100 первых членов арифметической прогрессии с начальным числом А и разностью D по формуле

Ui = A + iD, i = 1,2,... 100, т. е.

U1=А+D, U2=A+2D, U3=A+3D,..., U100=A+100D.

Два варианта схемы алгоритма приведены на рис.11.

Цикл алгоритма составляют символы 3-6, параметром цикла является переменная i (счетчик числа повторений цикла). В схеме на рис.11.а рекуррентно вычисляются только значения переменной i (символ 5), на рис. 10.б, кроме того, и значения членов арифметической прогрессии по формуле (символ 3), при .

а) б)

Рис.11

Для вычисления членов арифметической прогрессии можно было бы воспользоваться заданной формулой, подставляя в нее значения i = 1,2...100 (рис.11.а), при этом для вычисления каждого значения необходимо было бы выполнить операцию умножения и сложения (символ 3). Более рационально производить вычисления по алгоритму, представленному на рисунке 11.б, поскольку здесь производится только операция сложения (символ 3).

На первый взгляд кажется, что использование рекуррентной формулы дает экономию только в одной операции умножения. Фактическая же экономия выражается в 100 таких операциях, так как вычисление U_i осуществляется в цикле.

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

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

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

Общие формулы вычисления сумм и произведений имеют следующий вид:

, ,

где U(n) - выражение, зависящее от n. Во многих практических задачах начальное значение переменной n равно i (i=1), однако в общем случае переменная n может принимать любые начальные значения. Ее начальное значение может быть 0, -1, и др.

Схемы алгоритмов вычисления значений сумм (S) и произведений (P) приведены на рис.12.

Начальные значения S и P в большинстве случаев можно брать равными 0 и 1 соответственно. Вообще говоря, в качестве начального значения можно брать и U(1), тогда последующие вычисления следует выполнять для n=2,3,...m.

ПРИМЕР 2. Вычислить факториал натурального числа n.

Для вычисления n! используется формула

F=1*2*... *(n-1)*n=

Схема алгоритма приведена на рис.13.

ПРИМЕР 3. Вычислить:

Y= = + +... + +... + .

а) б)

Рис. 12

Рис. 13

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

= = = = .

Откуда рекуррентная зависимость будет иметь вид:

, при .

Схема алгоритма приведена на рис.14.

ПРИМЕР 4. Вычислить

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

Схема алгоритма вычисления значения S представлена на рис.15.

ЭВМ обычно оперирует большими объемами данных. При этом между данными, как правило, существуют определенные структурные отношения. Простейшие структурные отношения устанавливаются между элементами таких совокупностей, как массивы.

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

Всем элементам массива дается одно и то же наименование, а их положение в массиве указывается с помощью индексов. Например, элементы одномерного массива x (вектора, линейного списка), записываются в виде:

,

где 1 и n - начальное и конечное значение индекса соответственно.

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

...

...

...

...

Рис.14 Рис.15

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

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

ПРИМЕР 5. Задан массив чисел X={ }. Требуется составить алгоритм вычисления значений сумм первых 2, 3,...,n чисел этого массива в двух вариантах:

а) с выводом частичных сумм на печать;

а) б)

Рис. 16

б) с запоминанием в памяти ЭВМ частичных сумм в виде массива и последующего вывода этого массива на печать.

Графические схемы алгоритмов решения этой задачи приведены на рис.16, где в обоих вариантах используется одна и та же рекуррентная формула при i=2, 3, 4,..., n и .

Однако предписания, соответствующие этой формуле, в схемах различны. В первом варианте (рис. 16.а) переменная S записана без индекса, ее текущее значение фиксируется при печати.

Во втором варианте (рис. 16.б) переменная S записана с индексами, что показывает на формирование массива . Переменная х в обоих вариантах записывается с индексами, т.к. по условию задачи является элементом массива.

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

ПРИМЕР 6. Вычислить значение функции D, вычисляемой по формуле:

,

где P, G, L, , H - заданные константы, а меняется от 1 до 10 с шагом 0,5. Значения D хранить в виде массива. Схема алгоритма представлена на рис.17.

Рис. 17

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

Константа 12,56 представляет собой произведение 4×p (4*3,14=12,56).

Поиск по сайту: