Задача № 23. Найти наименьшее общее кратное двух натуральных чисел

Формулировка. Даны два натуральных числа. Найти их наименьшее общее кратное.

Примечание: наименьшим общим кратным двух чисел 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) именно потому, что если два числа делятся на некоторое число, то и их произведение также делится на него.

Код:

Задача № 24. Вычислить xⁿ

Формулировка. Даны натуральные числа x и n (которое также может быть равно 0). Вычислить xⁿ.

Решение. Для того чтобы решить эту задачу, вспомним определение степени с натуральным показателем: запись xⁿ означает, что число x умножено само на себя n раз.

Сразу из определения видно, что здесь заранее известно количество повторений при вычислении результата, так что задача легко решается через цикл for. Выходит, мы копируем исходное число x в некоторую переменную res (от англ. result – «результат»), а затем просто умножаем его на x n раз? Не стоит торопиться с ответом.

Рассмотрим пример: 3⁴ = 3 * 3 * 3 * 3 = 81. Если посмотреть на эту запись, то мы видим, что возведение в четвертую степень как выражение содержит четыре слагаемых, но только три операции, так как мы с первого шага домножаем число 3 на три тройки. Тогда реализация идеи из абзаца выше будет давать число в степени на 1 больше, чем требуется.

Какой можно придумать выход? Например, можно сократить цикл на одну операцию, но что тогда будет при вычислении нулевой степени? Как известно, любое число в нулевой степени дает 1, а здесь при вводе в качестве n нуля приведет к тому, что не будет осуществлен вход в цикл (так как не существует целочисленного отрезка от 1 до 0) и в итоге на выход так и пойдет исходное число x.

А что, если изменить схему умножения так: 3⁴ = 1 * 3 * 3 * 3 * 3 = 81? Так мы можем сравнять показатель степени и число требуемых операций, да и с нулевой степенью все становится просто, так как при вводе в качестве n нуля не будет осуществляться вход в цикл и на выход в программе пойдет число 1!

Теперь алгоритм на естественном языке:

1) Ввод x и n;

2) Присваивание переменной res числа 1;

3) Запуск цикла, при котором i изменяется от 1до n. В цикле:

1. Присваиваем переменной res значение res * x;

4) Вывод переменной res.

Код:

Кстати, стоит понимать, что объявление переменной res при использовании типа word достаточно условно, так как этот тип принимает значения от 0 до 65535, что на единицу меньше числа 256²_, хотя вводить в программу можно числа, предполагающие возведение в более высокую степень. Так как в условии задачи не сказано ничего о том, в каком числовом промежутке по x и n она должна выдавать корректный ответ, оставим это в таком виде, достаточном для проверки приложения на работоспособность.