Лекция6(2) Типовые алгоритмы

Алгоритмизация и программирование

Типовые алгоритмы решения задач

Лекция 6 по дисциплине «Информатика», часть 2 Автор, доцент кафедры информатика Тимухина В.В.

Содержание лекции

1.Алгоритм с итерационным циклом.

2.Запоминание результатов.

3.Типовые алгоритмы обработки одномерных массивов.

4.Типовые алгоритмы обработки двумерных массивов.

Лекция 6 Информатика, часть 2

2

Задача вычисления значений членов бесконечного ряда

с заданной точностью

Вычислить значения членов бесконечного ряда

õ, x2 ,..., xn ,...

2! n!

с точностью до члена ряда

xn ≤ ε n!

Лекция 6 Информатика, часть 2

3

Решение осуществляется в

итерационном цикле, так как заранее не известно, при каком n выполнится условие.

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

Сравнивая два соседних члена ряда, можно заметить, что уn / yn-1=x/n.

Лекция 6 Информатика, часть 2

4

Члены ряда Уn

õ,

x

2

,

x

3

,...,

x

n

Условие

Ón =

x

n

≤ ε

завершения

2!

3!

n!

n!

цикла

•Для вычисления текущего члена ряда в цикле используется рекуррентная формула Уn = Уn-1 *x/n.

•Для первого члена ряда У1 = У0 *x/1 задается У0 =1.

•Параметр, изменяющийся в этом цикле – номер члена ряда n.

•Формула для вычисления текущего члена ряда У=У* х/n.

Лекция 6 Информатика, часть 2

5

Блок-схема алгоритма вычисления членов ряда

1.Ввести значения Х и ε.

2.Задать n=1 и начальное значение У1 - первого члена ряда.

3.НЦ

3.1. Вычислить следующий член ряда

Уn =Уn *Х/n

3.2.Напечатать n и Уn.

3.3.Вычислить номер следующего члена ряда n=n+1.

3.4.Если Уn >ε то перейти к НЦ.

3.5.КЦ

4. Конец

Начало

Х,ε

Yn=1, n=1

НЦ

Уn= Уn Х/n

n, Уn

n=n+1

Да

Уn >ε

КЦ

Конец

Лекция 6 Информатика, часть 2

6

Запоминание результатов

В приведённых выше примерах результаты вычислений рассматривались как простые переменные. Поэтому после окончания вычислений сохранялись лишь последние их значения.

Новые значения сохраняясь в переменной затирали её старые значения.

Лекция 6 Информатика, часть 2

7

Запоминание результатов

Если требуется сохранить в памяти (запомнить) все значения результатов, то необходимо:

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

2.Вычислять результат как переменную с индексом.

Лекция 6 Информатика, часть 2

8

Массив – это упорядоченная последовательность величин, обозначаемая одним именем.

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

При описании массива в программе указываются его имя и размер, то есть количество элементов в массиве.

Например, Х(N), массив с именем Х, содержит N элементов. Отдельные элементы этого массива запишутся так: Х(0), Х(1), Х(2),…, Х(N), то есть элементы имеют такое же имя как массив и отличаются друг от друга индексом.

Лекция 6 Информатика, часть 2

9

Номер элемента называется Индексом. Индексы в массиве записываются в скобках.

Индексом может быть константа или выражение.

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