Пример 2. Алгоритм Евклида.Алгоритм Евклида используется при подсчете НОД (наибольшего общего делителя) двух натуральных чисел. Этот алгоритм основан на утверждении о том, что:
НОД(А, В) = НОД(А, В-А), если А < В НОД(А, В) = НОД(А - В, В), если А > В Программа подсчета НОД сводится к повторению одной и той же последовательности действий: 1) проверка равенства чисел; 2) если они равны, то НОД найден; 3) если они не равны, то среди чисел находится максимальное и из него вычитается другое число. Алгоритм повторяется до тех пор, пока числа не сравняются между собой. REM Алгоритм Евклида INPUT "'Введите числа a и b "; a, b WHILE a <> b IF a > b THEN a = a - b ELSE b = b - a END IF WEND PRINT "НОД чисел равен "; a
|
НОД(А, В) = А, если А = В
