Вычисление НОД. Рассмотреть три способа построения НОД

1. Вычисление НОД чисел m и n при помощи алгоритма Евклида

Шаг 1 Если n = 0, вернуть m в качестве ответа и закончить работу; иначе nерейти к шагу 2.
Шаг 2 Поделить нацело m на n и присвоить значение остатка переменной г.
Шаг 3 Присвоить значение n переменной m, а значение г — переменной n.
Перейти к шагу 1.

Запишем этот же алгоритм в виде псевдокода.
Алгоритм Euclid (m, n)
//Алгоритм Евклида вычисляет значение функции gcd (m, n)
// Входные данные: два неотрицательных целых числа m и n,
// которые не могут одновременно быть равны нулю
// Выходные данные: наибольший общий делитель чисел m и n
while n ≠0 do
г ← m mod n
т ← n
n ← г
return m

2. Вычисление НОД чисел m и n методом последовательного перебора

Шаг 1 Присвоить значение функции min {m, n} переменной t.
Шаг 2 Разделить m на t. Если остаток равен нулю, перейти к шагу 3; иначе
перейти к шагу 4.
Шаг 3 Разделить n на t. Если остаток равен нулю, вернуть t в качестве ответа
и закончить работу; иначе перейти к шагу 4.
Шаг 4 Вычесть 1 из t. Перейти к шагу 2.

Обратите внимание, что в отличие от алгоритма Евклида, рассматриваемый нами алгоритм поиска НОД в описанной выше форме не будет корректно работать, если хотя бы один из его входных параметров равен нулю. Таким образом, этот пример позволяет показать, почему так важно явно определять диапазоны допустимых значений входных параметров алгоритма.

3. Вычисление НОД чисел m и n "школьным" методом (разложение на простые множители)

Шаг 1 Разложить на простые множители число m.
Шаг 2 Разложить на простые множители число n.
Шаг 3 Для простых множителей чисел m и n, найденных на шаге 1 и 2, выделить их общие делители. (Если р является общим делителем чисел m и n и встречается в их разложении на простые множители, соответственно, рm и рn раз, то при выделении нужно повторить это min { рm, рn } раз-)
Шаг 4 Вычислить произведение всех выделенных общих делителей и вернуть его в качестве результата поиска НОД двух указанных чисел.

Таким образом, для рассмотренной выше пары чисел (60,24), получим:
60 = 2 • 2 • 3 • 5
24 = 2 • 2 • 2 • 3
gcd(60,24)=-- 2• 2• 3 = 12.

Задание
1. Реализовать алгоритмы средствами С++.
2. Сравнить работу алгоритмов для различных исходных данных.
а) Найдите значение функции gcd (31415,14142) при помощи алгоритма Евклида.
б) Оцените, во сколько раз быстрее вычисляется значение функции gcd (31415,14142) при помощи алгоритма Евклида по сравнению с алгоритмом последовательного перебора чисел сверху вниз от значения min {m, n} до значения gcd (m, n).
в) Найдите нод(1 801 768 290, 1 294 654 057).
3. Докажите, что для любых двух положительных чисел m, n выполняется равенство gcd (m, n) = gcd (n, m mod n).
4. Что произойдет, если при использовании алгоритма Евклида первое из чисел будет меньше второго? Каково будет максимальное время выполнения алгоритма при подстановке таких входных данных?
5. а) При каких значениях входных параметров m, n в алгоритме Евклида выполняется минимальное количество операций деления, при условии, что 1 <=m, n<= 10?
б) При каких значениях входных параметров m, n в алгоритме Евклида выполняется максимальное количество операций деления, при условии, что 1 <=m, n<= 10?
6. а) В своем трактате Евклид описал алгоритм поиска НОД, в котором вместо операций целочисленного деления используются операции вычитания. Запишите этот вариант алгоритма Евклида на псевдокоде.

0