Вычисление наибольших общих делителей

Задача

Найти наибольшие общие делители (НОД) для множества пар чисел.

Пояснение к задаче и алгоритм решения

Пусть пользователь будет вводить пары чисел, а на экран будут выводиться наибольшие общие делители этих чисел. В таком случае программу можно организовать следующим образом.

В основной ветке программы будет цикл, в теле которого будут

  1. запрашиваться два числа,
  2. вызываться функция для вычисления наибольшего общего делителя,
  3. возвращаемый функцией результат выводиться на экран.

Условие прекращения работы цикла основной программы - ввод пользователем двух нулей.

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

На самом деле НОД содержится только в одной переменной, а вторая имеет нулевое значение (это условие окончания цикла). Однако нам неизвестно какая из двух содержит 0, поэтому проще их сложить, чем это выяснять.

Почему НОД можно определить таким способом (следует знать, что он не единственный)? Представим, что у нас два числа: 18 и 12. Остаток от деления 18 на 12 будет 6. Далее имеется два числа 12 и 6. Остаток от деления первого на второе равен 0. Он записывается на место числа 12. Получаем 0 и 6. Таким образом 12 делится нацело на 6, а вот как пояснить логически, что и 18 на него должно делиться?

Исходный код на языке программирования Pascal

var a, b: word;
 
function gcd(c, d: word): word;
    begin
        while (c <> 0) and (d <> 0) do
            if c > d then
                c := c mod d
            else
                d := d mod c;
        gcd := c + d;
    end;
 
begin
    repeat
        write('Two numbers: ');
        readln(a,b);
        writeln('GCD: ', gcd(a,b));
    until (a = 0) and (b = 0);
end.

Пример(ы) выполнения программы на языке Pascal

Two numbers: 56 18
GCD: 2
Two numbers: 196 144
GCD: 4
Two numbers: 305 809
GCD: 1
Two numbers: 810 3220
GCD: 10
Two numbers: 15000 10500
GCD: 1500
Two numbers: 0 200
GCD: 200
Two numbers: 0 0
GCD: 0

Исходный код на языке программирования C

#include <stdio.h>
int gcd (int, int);
 
main() {
    int a, b;
    do {
        printf("Two numbers: ");
        scanf("%d%d", &a, &b);
        printf("GCD: %d\n", gcd(a,b));
    } while (a != 0 || b != 0);
}
 
int gcd(int c, int d) {
    while (c != 0 && d != 0) {
        if (c > d) c = c % d;
        else d = d % c;
    }
    return c + d;
}

Исходный код на языке программирования Python

def gcd(c,d):
    while c != 0 and d != 0:
        if c > d:
            c %= d
        else:
            d %= c
    return c + d
 
a = b = 1
while a != 0 or b != 0:
    a = input("Two numbers: ")
    a = a.split()
    b = int(a[1])
    a = int(a[0])
    print("GCD:", gcd(a,b))

Исходный код на языке программирования КуМир

алг
нач
  цел а, б
  нц
    вывод "Введите два целых числа: "
    ввод а, б
    вывод "НОД = ", НОД(а,б), нс
  кц_при а = 0 и б = 0
кон
 
алг цел НОД (цел а, цел б)
нач
  цел в, г
  в := а
  г := б
  нц пока в <> 0 и г <> 0
    если в > г то в := mod(в,г)
     иначе г := mod(г,в)
    все
  кц
  знач := в + г
кон

Исходный код на языке программирования Basic

do
        print "Введите два числа:"
        input a
        input b
        gosub gcd
until a = 0 and b = 0
end
 
gcd:
        c = a
        d = b
        while c<>0 and d<>0
                if c>d then
                        c = c % d
                else
                        d = d % c
                endif
        endwhile
        print "НОД = " + (c+d)
return

Тема

Функции

Уровень сложности

Средний

Дата публикации