Особенностью итерационного цикла является то, что число повторений операторов тела цикла заранее неизвестно. Для его организации используется цикл типа пока. Выход из итерационного цикла осуществляется в случае выполнения заданного условия.
На каждом шаге вычислений происходит последовательное приближение и проверка условия достижения искомого результата.
Пример. Составить алгоритм вычисления суммы ряда
с заданной точностью 
(для данного
знакочередующегося степенного ряда требуемая точность будет достигнута, когда
очередное слагаемое станет по абсолютной величине меньше).
Вычисление сумм — типичная циклическая задача. Особенностью же нашей конкретной задачи является то, что число слагаемых (а, следовательно, и число повторений тела цикла) заранее неизвестно. Поэтому выполнение цикла должно завершиться в момент достижения требуемой точности.
При составлении алгоритма нужно учесть, что знаки слагаемых чередуются и степень числа х в числителях слагаемых возрастает.
Решая эту задачу "в лоб" путем вычисления на каждом i-ом шаге частичной суммы
S:=S+(-1)**(i-1)*x**i/i ,
мы получим очень неэффективный алгоритм, требующий выполнения большого числа операций. Гораздо лучше организовать вычисления следующим образом: если обозначить числитель какого-либо слагаемого буквой р, то у следующего слагаемого числитель будет равен -р*х (знак минус обеспечивает чередование знаков слагаемых), а само слагаемое m будет равно p/i, где i - номер слагаемого.
Сравните эти два подхода по числу операций.
|
Блок-схема алгоритма |
|
алг Сумма (арг вещ x, Eps, рез вещ S)
дано | 0 < x < 1
надо | S = x - x**2/2 + x**3/3 - ...
нач цел i, вещ m, p
ввод x, Eps
S:=0; i:=1 | начальные значения
m:=1; p:=-1
нц пока abs(m) > Eps
p:=-p*x | p - числитель
| очередного слагаемого
m:=p/i | m - очередное слагаемое
S:=S+m | S - частичная сумма
i:=i+1 | i - номер
| очередного слагаемого
кц
вывод S
кон
|
|
Алгоритм, в состав которого входит итерационный цикл, называется итерационным алгоритмом. Итерационные алгоритмы используются при реализации итерационных численных методов.
В итерационных алгоритмах необходимо обеспечить обязательное достижение условия выхода из цикла (сходимость итерационного процесса). В противном случае произойдет зацикливание алгоритма, т.е. не будет выполняться основное свойство алгоритма — результативность.
Оператор цикла Repeat...Until (делать пока)
Оператор Repeat (повторять)...Until (до тех пор, пока) содержит логическое выражение (после Until), которое управляет повторением последовательности операторов, записанных между Repeat и Until. Повторение продолжается до тех пор, пока логическое выражение не примет значение True. Последовательность операторов выполняется по меньшей мере один раз, ибо логическое выражение вычисляется после выполнения данной последовательности (поэтому данный цикл называют цикл с постусловием). Последовательность операторов тела цикла выполняется не менее одного раза.
Repeat
<оператор 1>;
<оператор 2>;
………..
<оператор п>;
Until <логическое выражение>;
При использовании оператора Repeat...Until необходимо учитывать следующее:
· последовательность операторов должна содержать хотя бы один оператор, влияющий на значение логического выражения;
· для того чтобы цикл завершился, логическое выражение рано или поздно должно принять значение True.
Приведем простейший пример бесконечного цикла:
Repeat ... Until False;
1. Натуральное число р называется простым, если оно делится только на 1 и на себя. По соглашению 1 не считают простым числом. Начало последовательности простых чисел имеет вид:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, ...
В программе Zad1 определяется, является ли данное число простым. Мы ищем делители числа п в интервале от 2 до a Div 2, хотя можно было бы ограничиться интервалом от 2 до целой части -jn (почему?).
Program Zad1;
Var i,n:Longlnt;
Begin
WriteLn ('Введите натуральное число');
ReadLn(n);
i:=l;
Repeat
Inc(i);
Until (i> n Div 2) Or (n Mod i = 0) ;
If i> n Div 2
Then Writeln('Число ', n,' простое')
Else
WriteLn('Число ',i,' первый делитель числа ',п);
ReadLn
End.
Эту задачу можно решить и с использованием оператора While (см. предыдущее занятие). Сделайте это. Затем измените программу так, чтобы осуществлялся вывод всех делителей числа га.
Подсказка
Логическое выражение оператора Repeat...Until упростится, в нем останется только условие i > n Div 2, а в теле цикла появится
If n Mod i = 0 Then WriteLn (..., i) .
Основная теорема арифметики. Всякое натуральное число п > 1 разлагается на произведения простых чисел. Это разложение однозначно с точностью до порядка записи простых чисел в произведении.
Выберите интервал чисел (не очень большой, например от 101 до 120) и, используя модифицированную программу, найдите разложения этих чисел на произведения простых чисел. Ваши записи должны иметь вид:
,
где (аi=0),
pi
– простые числа,
например 168-23*31*50*71.
2. Наибольший общий делитель (НОД) двух целых чисел а и b — это наибольшее целое число, которое делит нацело оба числа. Далее мы будем рассматривать лишь неотрицательные числа, но это не влияет на общность рассуждений. Для нахождения НОД чисел а и b можно представить оба числа в виде:
и
,
затем найти НОД (a,b) в виде
Здесь т = min(g, r).
Отложим исследование этого метода нахождения НОД и рассмотрим другой способ, который называется алгоритмом Евклида. Пусть а и b одновременно не равные нулю целые неотрицательные числа и а > b Если b = 0, то НОД(а, b) = а, а если b<> 0, то для чисел а, Ь и г, где г — остаток от деления а на Ь, выполняется равенство НОД(а, b) -= НОД(b, г). Действительно, r := a Mod b, r := а - (a Div b) • b. Если какое-то число делит нацело и а, и b, то из приведенного равенства следует, что оно делит нацело и число г.
Например, пусть а = 48, а Ь = 18. Приведем ручную трассировку алгоритма Евклида
|
a |
b |
Результаты |
|
48 |
18 |
|
|
48 Mod 18=12 |
18 |
НОД(48, 18)=НОД(12, 18) |
|
12 |
18 Mod 12=6 |
НОД(12, 18)=НОД(12, 6) |
|
12 Mod 6=0 |
6 |
НОД(12, 6)=НОД(0, 6) |
|
0 |
6 |
НОД(0, 6)=6 |
Таким образом, НОД(48, 18) = 6.
Программная реализация алгоритма Евклида с использованием оператора Repeat...Until имеет вид:
Program Zad2;
Var a, b: Longlnt;
Begin
WriteLn('Введите два числа О 0' );
ReadLn(a,b)
Repeat
If a>b Then a:=a Mod b Else b:=b Mod a;
Until (a=0) Or (b=0);
WriteLn('НОД=',a+b) );
ReadLn;
End.
Измените программу так, чтобы вместо оператора Repeat... Until использовался оператор While. Какое ограничение в этом случае мы можем убрать?
Элементы еi последовательности
e1=1 + 1 = 2,
е2=2 + 1 = 3,
е3=2-3+ 1 = 7,
e4 = 2*3*7 + 1 = 43,
е5 = 2*3*7*43+1 = 1807,
е6 = 2*3*7 * 43*1807 +1 = 3263443,
e7 = 2 *3*7*43*1807*3263443 +1 = 547*607*1033*31051
и т. д.
называют числами Евклида. По первым четырем числам кажется, что числа Евклида простые. Однако это не так, уже е5 является составным — 1807 = 13 *139.
Известно, что евклидовы числа взаимно простые — НОД(ei;, еj) = 1 при i<> j. Проверьте этот факт с помощью программы для первых 6 чисел Евклида. Используя программу , покажите, что число е6 простое.
Задания для самостоятельной работы
1. Числа вида 2Р - 1, где р — простое число, называются числами Мерсенна. Являются ли числа Мерсенна при значениях р = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 простыми? Для ответ на этот вопрос напишите соответствующую программу. Программа должна состоять из двух частей: в первой вычисляется число Мерсенна для значения р (р вводится с клавиатуры), во второй проверяется, является ли оно простым.
2. Линейные уравнения от двух переменных (линейные диофактовые уравнения), т. е. уравнения вида: ах + Ьу = с,в которых а и b не равны нулю одновременно, имеют целые решения тогда и только тогда, когда b= НОД(а, Ь) делит нацелочисло с. Причем, если х0, у0 — некоторое (частное) решение, то все решения имеют вид:
х = х0 - п * (b Div d),
у = у0 + п * (a Div d) для всех п.
Пример: 12 х - 30 * у = 84, НОД(12, -30) = 6, 84 делится нацело на 6. Уравнение разрешимо. Одним из его решений является (х, у) = (2, -2). Все остальные решения имеют вид:
х = 2 + 5 *n, у = -2+ 2*п.
Даны целые числа а, b, с. Напишите программу определения разрешимости соответствующего диофантового уравнения i если оно разрешимо, поиска частного решения.
3. Пусть а и b — ненулевые целые числа. Целое число т>o называется наименьшим общим кратным (НОК) чисел а и b, если т делится и на а, и на b нацело, а также для любого c, которое делится нацело и на а и на b, делится нацело и на т.
Если а и b — ненулевые числа, то их наименьшее общее краг ное существует и справедливо равенство:
НОК(а, b) = | а *b \ Div НОД(а, b).
Напишите программу нахождения НОК двух ненулевых чисе.л.
4. Числа Фибоначчи (fn) определяются формулами: f0 = f1 = 1; fn =fn-1 + fn-2 при п > 2. Начало последовательности Фибоначчи имеет вид: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89. Напишите программу:
· определения номера последнего числа Фибоначчи, которое входит в диапазон типа Integer (Longlnt);
· вычисления s — суммы первых чисел Фибоначчи, таких, что значение s не превышает диапазона типа Integer (Longlnt).
5. Совершенным называется число, равное сумме всех своих делителей, меньших, чем оно само. Например: 6 = 1 + 2 + 3, 28 =1 + 2 + 4 + 7 + 14. Напишите программу, проверяющую, является ли заданное натуральное число совершенным.
Примечание
Евклидом доказано, что каждое число вида 2'p-1 * (2Р - 1) является совершенным числом, если 2Р - 1 — простое число. Л. Эйлер доказал, что все четные совершенные числа находятся по формуле Евклида, а относительно нечетных совершенных чисел ничего неизвестно до сих пор.
6. Автоморфным называется такое число, которое равно последним цифрам своего квадрата. Например: 52 = 25, 252 = 625.Очевидно, что автоморфные числа должны оканчиваться либо на 1, либо на 5, либо на 6. Напишите программу нахождения автоморфных чисел (с учетом приведенного факта), не превышающих значения 999.
Примечание
Не забывайте о диапазонах переменных целого типа,
9992 = 998001.
7. Кубические автоморфные числа равны последним цифрам своих кубов. Например: б3 = 216. Верно ли, что и такие числа должны оканчиваться либо на 1, либо на 5, либо на 6? Напишите программу нахождения двузначных, трехзначных кубических автоморфных чисел.
8. Определите результат действия программы
