Оглавление:
Задача — Вычисление наибольших общих делителей
— программирование на Pascal, Си, Кумир, Basic-256, Python
Найти наибольшие общие делители (НОД) для множества пар чисел.
Пусть пользователь будет вводить пары чисел, а на экран будут выводиться наибольшие общие делители этих чисел. В таком случае программу можно организовать следующим образом.
В основной ветке программы будет цикл, в теле которого будут
- запрашиваться два числа,
- вызываться функция для вычисления наибольшего общего делителя,
- возвращаемый функцией результат выводиться на экран.
Условие прекращения работы цикла основной программы — ввод пользователем двух нулей.
НОД будет вычисляться в функции, которая будет получать два числа, а возвращать их НОД. Алгоритм нахождения НОД может быть следующим. Пока оба числа не равны нулю, находить остаток от деления большего числа на меньшее и присваивать его переменной, где хранилось большее число. После цикла сложить значения обоих переменных, — это и есть НОД.
На самом деле НОД содержится только в одной переменной, а вторая имеет нулевое значение (это условие окончания цикла). Однако нам неизвестно какая из двух содержит 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. 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
Язык Си
#include <stdio.h>
int gcd (int, int);
main() {
int a, b;
do {
printf(«Two numbers: «);
scanf(«%d%d», &a, &b);
printf(«GCD: %dn», 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-256
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
