Программа по формированию навыков безопасного поведения на дорогах и улицах «Добрая дорога детства» 2
Скачать 29.95 Kb.
|
 Криворотова Л.Н. ТР 7.0. Основы программированияТема: «Циклические алгоритмы. Алгоритм Евклида». Повторение
Алгоритм Евклида — это алгоритм нахождения наибольшего общего делителя (НОД) двух целых неотрицательных чисел. Пусть х и у одновременно не равные нулю целые неотрицательные числа и пусть х ≥ у. Если у=0, то НОД(х,у)=х, а если у≠0, то для чисел х, у и r, где r -остаток от деления х на у, выполняется равенство НОД(х,у)= НОД(y, r). Например, пусть х=48, а у=18. НОД(48,18) = НОД(18,12) = НОД(12,6) = НОД(6,0). Пример Написать программу нахождения наибольшего общего делителя двух неотрицательных чисел. Решение Для решения данной задачи воспользуемся циклом с постусловием: Program Example 11; Var x, у: Integer; Begin Writeln ('Введите два числа'); Readln(x, у); Repeat {выполнять} If x>y Then x:=x mod у Else y:=y mod x; Until (x=0) or (у=0); {до тех пор, пока одно из чисел не станет равно нулю} Writeln('HOД=', (х+у)); {вывод НОД. Одно из чисел обязательно равно нулю} Readln; End. Пример Даны натуральные числа х и у, не равные нулю одновременно. Найти d=НОД(х, у) и такие целые q и w, что d=q*x+w*y. Решение Введем переменные р, q, r, s, т и n, такие, что m=p*a+q*b, n=r*a+s*b. Первоначально т=а=х, п=b=у. Program Example_12; Var x, у: Integer; {исходные данные} р, q, r, s, m, n: Integer; {вспомогательные переменные} k: Integer; {для изменения значений р, q, r, s} d: Integer; {значение НОД} Begin Readln(x, у); m:=x; n:=y; p:=l; q:=0; r:=0; s:=l; Repeat If m>n Then Begin k:=m div n; m:=m mod n; p:= p-k*r; q:=q-k*s End Else Begin k:=n div m; n:=n mod m; r:=r-k*р; s:=s-k*q End; Until (m=0) or (n=0); If m=0 Then Begin d:=n; q:=r; w:=s; End Else Begin d:=m; q:=p; w:=q; End; Writeln(d, '=', q, '*', x,'+', w, '*', y); End. Значения переменных p, q, r, s изменяются следующим образом:
Решение задач 1. Найти НОД трех чисел. Примечание. НОД(а, b, с)=НОД (НОД (а,b), с).
НОД(2а, 2b)=2НОД(а, b); НОД(2а, b)=НОД(а, b) при нечетном b. В программе не должно использоваться деление с остатком. Можно лишь делить на 2 и проверять числа на четность. 7. Даны натуральные числа т и п. Найти такие натуральные взаимно простые p и q, что  |
Добавить документ в свой блог или на сайт
