Способы решения циклического алгоритма

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

Циклические алгоритмы бывают двух типов:
Циклы со счетчиком, в которых какие-то действия выполняются определенное число раз;
Циклы с условием, в которых тело цикла выполняется, в зависимости от какого-либо условия.

В общем случае схема циклического алгоритма со счетчиком будет выглядеть так:

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

Например, в субботу вечером вы смотрите телевизор. Время от времени поглядываете на часы и если время меньше полуночи, то продолжаете смотреть телевизор, если это не так, то вы прекращаете просмотр телепередач.

В общем случае схема циклического алгоритма с условием будет выглядеть так:

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

Источник

Циклические алгоритмы

Презентация к уроку

Загрузить презентацию (329 кБ)

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

Ход урока

I. Актуализация знаний

Повторить понятие алгоритма, основные конструкции алгоритмического языка.
Уметь разрабатывать математическую модель, алгоритм и блок схему решения задачи.
Иметь понятие о языках программирования и их назначении.
Уметь работать в среде программирования.
Знать структуры программы.
Уметь записывать выражения, содержащие числовые и символьные величины.
Знать структуры операторов и особенности их работы.
Уметь применять операторы при написании программ с линейными и ветвящимися структурами.
Уметь на компьютере создавать и запускать программы на отладку.

II. Теоретический материал урока

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

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

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

Циклом называется многократно исполняемый участок алгоритма (программы). Соответственно циклический алгоритм — это алгоритм, содержащий циклы.

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

Существует 3 типа циклических структур:

Цикл с предусловием;
Цикл с послеусловием;
Цикл с параметром;

Иначе данные структуры называют циклами типа «Пока», «До», «Для».

Графическая форма записи данных алгоритмических структур:

Цикл с предусловием (иначе цикл пока) имеет вид:

Форматы записи операторов алгоритма	Блок-схема	Форматы записи операторов на Паскале
Пока (условие) нц серия команд кц		while условие do begin серия команд; end;

условие – выражение логического типа.

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

Серия команд, находящихся между begin и end, выполняются до тех пор, пока условие истинно.

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

Цикл с постусловием (иначе цикл до) имеет вид:

Форматы записи операторов алгоритма	Блок-схема	Форматы записи операторов на Паскале
В алгоритмическом языке нет команды которая могла бы описать данную структуру, но ее можно выразить с помощью других команд (Например, ветвления).		*repeat* серия команд *until* условие

условие – выражение логического типа.

Последовательность инструкций между repeat и until всегда будет выполнено хотя бы один раз;

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

Инструкция repeat, как и инструкция while, используется в программе, если надо провести некоторые повторяющиеся вычисления (цикл), однако число повторов заранее не известно и определяется самим ходом вычисления.

Цикл с параметром (иначе цикл для) имеет вид:

Форматы записи операторов алгоритма	Блок-схема	Форматы записи операторов на Паскале
Для i от а до b шаг h делай Нц Серия команд кц		h = +1 for i:= a to b do begin серия команд end; h = -1 for i:= b downto a do begin Cерия команд; end;

i – параметр цикла;
a – начальное значение цикла;
b – конечное значение цикла;
h – шаг изменения параметра.

Структура данного цикла иначе называют циклом i раз.

Эта команда выполняется таким образом: параметру i присваивается начальное значение а, сравнивается с конечным значением b и, если оно меньше или равно конечному значению b, выполняется серия команд. Параметру присваивается значение предыдущего, увеличенного на величину h – шага изменения параметра и вновь сравнивается с конечным значением b.

На языке программирования Паскаль шаг изменения параметра может быть равным одному или минус одному.

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

Рассмотрим пример решения задач с использованием данных структур

Пример.

Вычислить произведение чисел от 1 до 5 используя различные варианты цикла

Составим алгоритм в виде блок-схемы.

Для проверки правильности алгоритма заполним трассировочную таблицу.

Источник

Способы решения циклического алгоритма

называется конечной суммой

Для некоторых последовательностей известны формулы расчета конечных сумм, например: при a_n = a_n-1 + d; S_n = (a₁ + a_n)*n/2; — арифметическая прогрессия, при a_n = a_n-1 * q; S_n= (a₁ — a_n*q)/(1-q); — геометрическая прогрессия, где d и q — постоянные числа. Здесь N-ый член последовательности выражается через (N-1)-ый член. Такие зависимости называются реккурентными. Конечная сумма последовательности может быть неизвестна, тогда для ее расчета применяется алгоритм суммирования членов последовательности в цикле от 1 до N. Приведем пример расчета конечной суммы последовательности: 12 + 32 + 52 +. . . + (2*N-1)₂; S_n = N*(4*N₂-1)/3; В некоторых случаях «N»-ый член последовательности определяется через сумму предыдущих членов, например,

и конечную сумму можно рассчитать по формуле:

где «S₀» — начальная сумма. Рассмотрим программу вычисления конечной суммы денежного вклада в банк через N месяцев при ежемесячной процентной ставке «pr» (5% cоответствует pr=5). Часто применяются вложенные операторы цикла. Например, если необходимо провести все варианты расчета при изменении нескольких параметров в заданных диапазонах. Составим программу расчета функции y = A*sin(x) — cos(x)/A; при изменении аргумента «x» в диапазоне от 0 до Pi с шагом Pi/100 и при изменении параметра «A» в диапазоне от 1 до 3 с шагом 0.5.

Операторы цикла с условием

Схема выполнения операторов имеет вид:

Цикл WHILE	Цикл REPEAT

В цикле While «оператор» выполняется если условие верно (True), если условие ложно (False), то цикл заканчивается, т. е. цикл While повторяется пока выполняется условие. Цикл While начинается проверкой условия, поэтому, если начальное условие ложно, то «оператор» не выполняется ни разу. Для включения в тело цикла нескольких операторов применяется составной оператор: Begin «операторы» end. Цикл Repeat повторяется, если условие ложно (False), и заканчивается, если условие верно (True), т. е. цикл Repeat повторяется до выполнения условия. Цикл Repeat заканчивается проверкой условия, поэтому «операторы» выполняются не менее одного раза. В теле цикла может записываться более одного оператора. Циклы с условием обычно используются в тех случаях, если количество повторений блока операторов заранее не известно, например, при расчете суммы членов бесконечного ряда с заданной погрешностью. Сумма членов бесконечной последовательности

называется бесконечным рядом и записывается в виде:

Здесь a_n — общий член ряда. Сумма конечного числа членов ряда называется частичной суммой и обозначается «S_n«. Если сумма членов бесконечного ряда имеет конечный предел «S», то ряд называется сходящимся. Для некоторых рядов получены формулы расчета суммы членов ряда. Например, сумма членов числового ряда:

1 + 1/32 + 1/52 + . . . + 1/(2*N-1) + .

имеет предел S = Pi 2 /8 и общий член a_n = images/(2*N-1) 2 , где N = 1, 2, 3, . Для сходящегося ряда вычисляется последовательность частичных сумм с заданной погрешностью. Абсолютная погрешность расчетов определяется по формуле Eps=abs(S-S_n), либо Eps=abs(a_n), если значение S неизвестно. Относительная погрешность расчетов определяется по формуле Eps_o=abs((S-S_n)/S), либо Eps_o=abs(a_n/S_n). Частичные суммы вычисляются по формуле: S_n = S_n-1 + a_n Для знакопеременного ряда следует добавить k1=-1, а в цикле: k1:=-k1, a_n=k1*a_n. В некоторых случаях «N»-ый член ряда выражается через «N-1»-ый, например, для ряда:

1 + 1/2! + 1/4! + 1/6! + . + 1/(2*N)! + . ; N = 0, 1, 2, .

общий член ряда вычисляется по формуле: a_n = a_n-1*k; Параметр k = a_n/a_n-1 — коэффициент роста вычисляется предварительно (до написания программы). Для данного ряда

Здесь N! = 1*2*3*. *N; — вычисление факториала числа «N», причем 0! = 1. Расчет частичных сумм производится в цикле с условием, например, для данного ряда операторами:

Операторы ограничения и прерывания цикла

Примеры

Пример1: На промежутке от 1 до M найти все числа Армстронга. Натуральное число из n цифр называется числом Армстронга, если сумма его цифр, возведенных в n-ю степень, равна самому числу.

Этапы решения задачи:

Математическая модель: xО[1;M], x=
Составим блок схему программы:

Распишем составные части блока»Находим все числа Армстронга на заданном промежутке и печатаем их»
Опишем блок «Подсчитываем сколько цифр в числе i»
Опишем блок «Проверяем, является ли i числом Армстронга»
Дальнейшая детализация не требуется, запишем блок-схему целиком:
Дальнейшей детализации не требуется, переведем программу на язык Паскаль.

Контрольные вопросы

Как записывается и как работает оператор FOR?
Для организации каких циклов применим оператор FOR?
В чем отличие оператора WHILE от оператора REPEAT?
Как программируются циклические алгоритмы с явно заданным числом повторений цикла?
Как программируются циклические алгоритмы с заранее неизвестным числом повторений цикла?
Напишите оператор цикла, который не выполняется ни разу.
Напишите оператор цикла, который выполняется неограниченное число раз.
Замените оператор «Repeat A Until B» равносильным фрагментом программы с оператором While.

Задачи

Найти все двузначные числа, сумма цифр которых не меняется при умножении числа на 2,3,4,5,6,7,8,9.
Найти все трехзначные числа, сумма цифр которых равна данному целому числу.
Найти все трехзначные числа, средняя цифра которых равна сумме первой и третьей цифр.
Найти все трехзначные числа, которые можно представить разностью между квадратом числа, образованного первыми двумя цифрами и квадратом третьей цифры.
Найти все двузначные числа, сумма квадратов цифр которых делится на 17.
Найти все трехзначные числа, представимые в виде сумм факториалов своих цифр.
Найти двузначное число, обладающее тем свойством, что куб суммы его цифр равен квадрату самого числа.
Найти двузначное число, равное утроенному произведению его цифр.
В каких двузначных числах удвоенная сумма цифр равна их произведению?
Можно ли заданное натуральное число М представить в виде суммы квадратов двух натуральных чисел? Написать программу решения этой задачи.
Вычисление выражений:
Дано натуральное n. Вычислить:
;
;

Дано действительное число х, натуральное число n. Вычислить:

x ( x — n )( x — 2 n )( x — 3 n )…( x — n2 );

;

;
Дано натуральное n. Вычиcлить:

;

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

;

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

Даны два целых числа A и B (A 0). Вывести A в степени N: AN = A·A·. ·A (числа A перемножаются N раз).

Дано вещественное число A и целое число N (> 0). Вывести все целые степени числа A от 1 до N.

Дано вещественное число A и целое число N (> 0). Вывести 1 + A + A2 + A3 + . + AN.

Дано вещественное число A и целое число N (> 0). Вывести 1 — A + A2 — A3 + . + (-1)NAN.

Дано целое число N (> 1). Вывести наименьшее целое K, при котором выполняется неравенство 3K > N, и само значение 3K.

Дано целое число N (> 1). Вывести наибольшее целое K, при котором выполняется неравенство 3K 1). Вывести наименьшее из целых чисел N, для которых сумма 1 + 1/2 + . + 1/N будет больше A, и саму эту сумму.

Дано вещественное число A (> 1). Вывести наибольшее из целых чисел N, для которых сумма 1 + 1/2 + . + 1/N будет меньше A, и саму эту сумму.

Дано целое число N (> 0). Вывести произведение 1·2·. ·N. Чтобы избежать целочисленного переполнения, вычислять это произведение с помощью вещественной переменной и выводить его как вещественное число.

Дано целое число N (> 0). Если N — нечетное, то вывести произведение 1·3·. ·N; если N — четное, то вывести произведение 2·4·. ·N. Чтобы избежать целочисленного переполнения, вычислять это произведение с помощью вещественной переменной и выводить его как вещественное число.

Дано целое число N (> 2) и две вещественные точки на числовой оси: A, B (A 2) и две вещественные точки на числовой оси: A, B (A 0). Последовательность чисел AN определяется следующим образом: A1 = 2, AN = 2 + 1/AN-1, N = 2, 3, . Найти первый из номеров K, для которых выполняется условие |AK — AK-1| 0). Последовательность чисел AN определяется следующим образом: A1 = 1, A2 = 2, AN = (AN-2+ AN-1)/2, N = 3, 4, . Найти первый из номеров K, для которых выполняется условие |AK AK-1| Задачи повышенной сложности

Определить, является ли заданное число совершенным , т.е. равным сумме всех своих (положительных) делителей, кроме самого этого числа (например, число 6 совершенно: 6=1+2+3).
Дано натуральное k. Напечатать k-ю цифру последовательности 1234567891011121314. в которой выписаны подряд все натуральные числа.
Дано натуральное k. Напечатать k-ю цифру последовательности 149162536. в которой выписаны подряд квадраты всех натуральных чисел.
Дано натуральное k. Напечатать k-ю цифру последовательности 1123581321. в которой выписаны подряд все числа Фибоначчи.

Источник