Тема: Программирование задач циклической структуры (оператор Repeat-Until).
Цель: Разобрать структуры повторения (оператор цикла с постусловием - Repeat-Until).
План занятия:
· обсуждение оператора;
· эксперименты с программами определения простоты числа, нахождения наибольшего общего делителя двух чисел с помощью алгоритма Евклида;
· выполнение самостоятельной работы.
Ход работы:
Теоретические сведения:
Оператор Repeat (повторять) - Until (до тех пор, пока) содержит логическое выражение (после Until), которое управляет повторением выполнения последовательности операторов, записанных между Repeat и Until. Повторение продолжается до тех пор, пока логическое выражение не примет значение True -1. Последовательность операторов тела цикла выполняется не менее одного раза.
Repeat
< оператор 1 >;
< оператор 2 >;
. . .
< оператор n >;
Until <логическое выражение>;
При использовании оператора Repeat - Until (цикла с постусловием) необходимо учитывать следующее:
· перед первым выполнением оператора логическое выражение его окончания (или продолжения) должно быть определено;
· последовательность операторов должна содержать хотя бы один оператор, влияющий на значение логического выражения, иначе оператор Repeat-Until работает бесконечно долго;
· логическое выражение в конечном итоге должно принять значение True.
Пример простейшей, бесконечной по времени работы, конструкции: Repeat ... Until False.
Экспериментальный раздел работы:
1. Целое положительное число р называется простым, если оно имеет только два делителя, а именно 1 и р. По соглашению 1 не считают простым числом. Начало последовательности простых чисел имеет вид:
Научимся устанавливать факт: является ли число n простым? Ниже приведен текст решения. Считаем, что делители числа находятся в интервале от 2 до n Div 2, точнее в интервале от 2 до целой части Sqrt(n).
Program Му9_1 ;
Var i , n :LongInt;
Begin
WriteLn ('Введите натуральное число');
ReadLn (n) ;
i : =1 ;
Reреаt
Inc(i) ;
Until (i > n Div 2) Or (n Mod i = 0) ;
If i> n Div 2 Then
Writeln ('Число ' ,п,' простое') Else
WriteLn ('Число ' ,i,' первый делитель числа ', n) ;
ReadLn;
End.
Естественно, что эту задачу можно решить и с использованием оператора While. Сделайте эту небольшую работу дома! А затем измените программу так, чтобы осуществлялся вывод всех делителей числа n. Подсказка: Логическое выражение оператора Repeat - Until упростится, останется только условие i > n Div 2, а в операторах тела цикла появится — If n Mod i=0 Then WriteLn(..., i).
2. Наибольший общий делитель (НОД) двух целых чисел а и b — это наибольшее целое число, которое делит нацело оба числа. Для нахождения НОД чисел а и b можно представить оба числа в виде:
a=p1al p2a2 .... pqq и b=p1bl p2b2.... pqbq, а затем найти HOД (a,b)=p1min(a1b1) p2min(a2P2) ... , некоторые степени простых чисел могут быть и нулевые. Отложим исследование этого метода нахождения НОД, у нас пока не хватает знаний. Обратимся к алгоритму греческого математика Евклида, он открыл его в 330-320 гг. до н. э. Алгоритм основан на следующем свойстве целых чисел. Пусть а и b одновременно не равные нулю целые неотрицательные числа и а > b, тогда если b=0, то НОД(а,b) =а, а если b<>0, то для чисел а, b и г, где г — остаток от деления а на b, выполняется равенство НОД(а,b)=НОД(b,г). Действительно, r=a Mod b=a - (a Div b)*b. Если какое-то число делит нацело и а, и b, то из приведенного равенства следует, что оно делит нацело и числа г и b. Например, пусть а=48, а b=18, найдем их наибольший общий делитель. Таким образом, НОД(48,18)=6.
Программная реализация алгоритма Евклида с использованием оператора Repeat—Until имеет вид
Program Му9_2;
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('HОД=',a+b) ;
ReadLn;
End.
Измените программу так, чтобы вместо оператора Repeat-Until использовался оператор While. Какое ограничение в этом случае мы можем убрать?
Последовательность чисел
ег=1+1=2,
е2=2+1=3,
еэ=2*3+1=7,
е4=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, и т. д.
называют числами Евклида. Первые 4 числа наталкивают на мысль о том, что Евклидовы числа простые. Однако уже е5является составным — 1807=13*139. Известно, что Евклидовы числа взаимно простые — H0Д(ei,ej)=l при i j. Проверьте этот факт с помощью программы Му10_2 для первых 6 чисел Евклида. Для работы с остальными числами Евклида типа Longlnt недостаточно, необходимо, по крайней мере, изучить основы «длинной» арифметики. Используя программу Му10_1, покажите, что число е6 простое.
Задания для самостоятельной работы:
1. Числа вида 2P-1, где р — простое число, называются числа ми М. Мерсенна (1588-1648 гг.). Являются ли числа Мерсенна при значениях р 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 простыми? Написать программу. Почему мы ограничились только этими простыми числами. Ваша программа должна состоять из двух частей: в первой — вычисляется число Мерсенна для значения р (вводится с клавиатуры) , во второй — проверяется является ли оно простым.
2. Линейные уравнения от двух переменных (линейные диофантовые уравнения), т. е. уравнения вида: а*х+b*у=с, в котоpом а и b не равны нулю одновременно, имеют целые решения тогда и только тогда, когда d (d=НОД(а,b)) делит нацело значение с. Причем, если х0, у0 — частное решение, то все решения имеют вид: x=x0-n*(b Div d), y=y0+n*(a Div d) для всех n. Пример: 12*х-30*у=84, НОД(12, -30)=6, 84 делится нацело на 6. Уравнение разрешимо. Одним из его решений является (х,у)=(2,-2). Все остальные решения имеют вид: х=2+5*n, у=-2+2*n.
Даны целые числа а, Ь, с. Написать программу определения разрешимости соответствующего диофантового уравнения и, если оно разрешимо, поиска частного решения.
3. Пусть а и b — ненулевые целые числа. Целое число m>0 называется наименьшим общим кратным (НОК) чисел а и b, если m делится и на а, и на b нацело, а также для любого с, которое делится нацело и на а и на b, верно, что оно делится нацело и на m.
Если а и b — ненулевые числа, то их наименьшее общее кратное существует и справедливо равенство HOK(a,b)=Abs(a*b) Div НОД(а,b). Написать программу нахождения НОК двух ненулевых чисел.
Контрольные вопросы:
1. Сколько операторов можно записать между ключевыми словами repeat и until?
2. Когда проверяется истинность выражения в операторе цикла с постусловием?
3. Почему в цикле repeatоператор тела цикла всегда будет выполнен хотя бы один раз?
4. Верно ли, что истинность выражения в циклеrepeatявляется условием окончания цикла?
5. Можно ли войти в тело цикла repeat, минуя заголовок?
j. Проверьте этот факт с помощью программы Му10_2 для первых 6 чисел Евклида. Для работы с остальными числами Евклида типа Longlnt недостаточно, необходимо, по крайней мере, изучить основы «длинной» арифметики. Используя программу Му10_1, покажите, что число е6 простое.