Решение

Для решения данной задачи воспользуемся циклом с постусловием:

Program Example_49;

Var x, у: Integer;

Begin

Writeln('Введите два числа');

Readln(х,у);

Repeat {выполнять}

If x>y Then x:=x mod у Else y:=y mod х;

Until (x=0) or (y=0);

{до тех пор, пока одно из чисел не

станет равно нулю}

Writeln('НОД=', х+у); {вывод НОД.

Одно из чисел обязательно равно нулю}

Readln;

End.

Пример 2

Даны натуральные числа х и у, не равные нулю одновременно. Найти d=НОД(х, у) и такие целые qи w, что d=q*x+w*y.

Решение

Введем переменные р, q, r, s, m и n, такие, что m=p*a+q*b, n=r*a+s*b. Первоначально m=a=x, n=b=y.

Program Example_50;

Var x, y: Integer; {исходные данные}

p, q, r, s, m, n: Integer;

{введенные вспомогательные переменные}

к: Integer;

{для изменения значений P, q, r, s}

d: Integer;

{значение наибольшего общего делителя}

Begin

Read(x, у);

m:=x; n:=y; р:=1; q:=0; r:=0; s:=1;

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*p;

s:=s-k*q;

End;

Until (m=0) or (n=0);

If m=0 ThenBegin d:=n; q:=r; w:=s;End

ElseBegin d:=m; q:=p; w:=q;End;

Writeln(d, '=',q,'*',x,'+',w,'*',y);

End.

Значения переменных p, q, r, s изменяются следующим образом:

• как только значение переменной m уменьшается на k*n, значение р уменьшается на k*r, а q уменьшается на k*s;

• аналогично, как только значение n уменьшается на k*m, значения переменных r и s уменьшаются соответственно на k*p и на k*q.

§20. Вложенные циклы

Пример 1

Даны натуральные числа n и k. Составить программу вычисления выражения 1^k+2^k+…+n^k.