Нахождение нод (наибольшего общего делителя) с помощью рекурсивной функции
Алгоритм решения задачи:
Наибольший общий делитель (НОД) чисел 3430 и 1365 – это 35. Другими словами, 35 – наибольшее число, на которое и 3430 и 1365 делятся без остатка. Чтобы убедиться в этом, разложим оба числа на простые сомножители:
3430 = 2 * 5 * 7 * 7 * 7
1365 = 3 * 5 * 7 * 13
и выделим пары общих сомножителей. В данном случае это пары 5 и 7. Наибольший общий делитель – это произведение совпадающих сомножителей; в данном случае это 5 * 7 = 35.
Более изящный метод поиска НОД – алгоритм Евклида. Найдем остаток от деления 3430 на 1365:
3430 mod 1365 = 700
Так как этот остаток не равен нулю, повторим то же действие, подставив вместо первого числа второе, а вместо второго – остаток:
1365 mod 700 = 665
Этот остаток также не нуль, поэтому еще одно деление:
700 mod 665 = 35
И еще одно:
665 mod 35 = 0
Теперь остаток – нуль, следовательно, НОД равен 35. Вот и отлично.
Следующая программа на Паскале использует метод Эвклида и рекурсию:
Программа на языке Паскаль:
var a, b, answer: integer;
function gcd(m, n: integer): integer;
var modulo: integer;
begin
modulo := m mod n;
if modulo = 0 then
gcd := n
else
gcd := gcd (n, modulo)
end;
begin
write('Enter two numbers: ');
readln(a, b);
answer := gcd(a, b);
writeln('Greatest common divisor: ', answer);
readln
end.
Примечания:
Если представить, что в функцию сразу подставляются числа 665 и 35, то сразу ясно, как вычисляется gcd(665, 35): остаток modulo будет равен нулю и функция возвратит число 35 (ветка if). А вот при обращении gcd(3430, 1365) modulo будет равен 700, и, следовательно, функция вызовет себя еще раз в виде gcd(1365, 700). Таким образом, при каждом обращении Паскаль как бы создает новую копию функцииgcd:
Функция, вычисляющая наибольший общий делитель
Алгоритм решения задачи:
Оформление алгоритмов вычисления наибольшего общего делителя в виде функций удобно, если в задаче требуется несколько или множество раз использовать данный алгоритм, по отношению к различным исходным данным.
Программа на языке Паскаль:
var
k, l, n: integer;
function nod (var a,b: integer): integer;
var c: integer;
begin
repeat
if a > b then
a := a mod b
else
b := b mod a;
until (a = 0) or (b = 0);
nod := a + b;
end;
begin
writeln ('Введите два числа: ');
readln (k, l);
n := nod (k, l);
writeln ('НОД = ', n);
readln
end.
Обмен значений переменных
Алгоритм решения задачи:
От пользователя требуется ввод двух чисел. Эти значения должны быть присвоены двум переменным, причем значение первой должно быть меньше второй. Конечно, можно предупредить об этом пользователя, но возможно ему удобней будет и не знать о требованиях программы. В коде программы можно реализовать процедуру, производящую обмен значений двух переменных, и вызывать ее после каждого очередного ввода пользователя.
Программа на языке Паскаль:
var
k, l: integer;
procedure exchange (var a,b: integer);
var c: integer;
begin
if a > b then begin
c := a;
a := b;
b := c;
end;
end;
begin
writeln ('Введите два числа: ');
readln (k, l);
exchange (k, l);
writeln ('k = ', k,'; l = ', l);
readln
end.