Поделиться
Задача по программированию Найти наименьшее общее кратное двух натуральных чисел.docx
Формулировка. Даны два натуральных числа. Найти их наименьшее общее кратное.
Примечание: наименьшим общим кратным двух чисел m и n называется наименьшее натуральное число, которое делится на m и n. Обозначение: НОК(m, n)
Решение. Из теории чисел известно, что НОК(m, n) связан с НОД(m, n) следующим образом:
Следовательно, для нахождения ответа нам нужно лишь использовать предыдущую задачу нахождения НОД двух чисел m и n:
while m <> n do begin
if m > n then begin
m := m - n
end
else begin
n := n - m
end
end;
Так как исходные переменные будут испорчены в процессе работы алгоритма Евклида, нам нужно вычислить их произведение до входа в описанный выше цикл и присвоить это произведение переменной prod (от англ. product – «произведение»):
prod := m * n;
После этого нам остается вывести на экран результат арифметического выражения в правой части нашей формулы. В качестве самого НОД будет использоваться переменная m:
writeln(prod div m);
Кстати, деление в формуле будет целочисленным (через div) именно потому, что если два числа делятся на некоторое число, то и их произведение также делится на него.
Код:
|
1. program LeastCommonMult; 2. 3. var 4. m, n, prod: word; 5. 6. begin 7. readln(m, n); 8. prod := m * n; 9. while m <> n do begin 10. if m > n then begin 11. m := m - n 12. end 13. else begin 14. n := n - m 15. end 16. end; 17. writeln(prod div m) 18. end. |
Скачано с www.znanio.ru
Материалы на данной страницы взяты из открытых источников либо размещены пользователем в соответствии с договором-офертой сайта. Вы можете сообщить о нарушении.
