Как найти НОД двух чисел? "Турбо Паскаль" и немного математики

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

Нахождение НОД в математике

Наибольший общий делитель – число, которое считается максимальным при разложении на составляющие. Записывается краткая форма определения как НОД. Например, рассмотрим рисунок. Здесь даны числа 140 и 175. Их наибольшим делителем является 35, то есть НОД (140,175)=35.

Чтобы не возникало дополнительных вопросов о том, как найти НОД двух чисел, следует придерживаться такого алгоритма:

• Найти простейшие делители первого числа.
• Эту же операцию проделать со вторым числом.
• Отыскать в наборе делителей первого и второго чисел общие показатели.
• Обвести их ручкой другого цвета.
• Перемножить общие делители (если их несколько) или выписать единственный (если числа простые, то их НОД будет равен 1).

Рассмотрим следующий рисунок. На нем показано, что даже такие большие числа, как 816 и 455, не имеют НОД, кроме 1.

Существует второй способ нахождения поставленной задачи. Алгоритм Евклида в математике выглядит следующим образом:

• Даны числа.
• Выбрать следует максимальное.
• Его делят на минимальное.
• 
  Теперь второе заданное число нужно разделить на получившийся остаток.
• Первый остаток делится на второй, получившийся от предыдущей операции.
• Вторую остаточную часть делим на третью и т.д.
• Операция деления проводится до тех пор, пока остаток не будет равен 0.
• Последний делитель и отвечают критерию НОД.

Для нахождения НОД более трех натуральных чисел рекомендуется придерживаться схемы работы (возьмем числа 140, 96, 64):

• В первом действии нужно повторить вышеописанный алгоритм для первых двух чисел.
• Найти НОД найденного делителя и заданного третьего числа.
• Отыскать НОД получившегося делителя и четвертого числа и т.д.

Нахождение НОК в математике

Если в программировании возникает вопрос о том, как найти НОД двух чисел, то он обязательно сопряжен со вторым: нахождение НОК. Наименьшим общим кратным двух чисел называют такое минимальное натуральное число, которое может поделиться и на первое, и на второе.

Первый способ:

• Даны два или более чисел.
• Выписать все кратные для каждой позиции.
• Выбрать наименьшее общее кратное.

Второй способ:

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

НОД в "Паскале": алгоритм работы

Как найти НОД двух чисел? "Паскаль" – язык программирования, на котором будет написан код. Сначала необходимо придерживаться алгоритма, указанного выше. И здесь математика приходит на помощь. Алгоритм работы задачи поможет найти НОД двух натуральных чисел. В Turbo Pascal это будет выглядеть следующим образом:

• Вывод на экран приглашения ввести с клавиатуры 2 неотрицательных числа.
• Запуск цикла while, где условием будет число 1 <> число 2 (условно a и b).
• Тело цикла включает такие действия: если a > b, тогда a:= a - b, иначе b:= b - a.
• Вывод на экран результата.

НОД в "Паскале": решение методом Евклида

Как найти НОД двух чисел посредством простого, но действенного метода?

• Ввод положительных чисел.
• Вызов написанной функции, вычисляющей НОД. В самой функции выполняются следующие действия: проверка условия, какое число больше; присвоение другим переменным изначальных данных; в цикле с предусловием (r2 <> 0, т.е. пока переменная не будет равняться 0) находится остаток от деления и переменным присваиваются результаты; присвоение имени функции готового результата.
• Вывод результата на экран.

Многие программисты считают, что оба варианта нахождения НОД очень схожи, поэтому в Интернете первый метод могут выдавать за алгоритм Евклида.

НОК в "Паскале": как устроена программа?

Здесь уже были рассмотрены 2 алгоритма, поясняющие, как найти НОД двух чисел. Теперь осталось усвоить, как выглядит программа поиска НОК в Turbo Pascal. Алгоритм работы при программировании таков:

• Ввод двух чисел.
• Присвоение двум другим переменным заданных значений.
• Нахождение произведения изначальных элементов.
• В цикле с предусловием (while) оформить условие: если первое число больше второго (n > m), тогда можно найти посредством вычитания результат (n:= n - m); иначе выполнить эту операцию, но в обратную сторону (m:= m - n).
• Вывести на экран результат, при котором найденное произведение будет делиться посредством функции div на число m.

Для чего вводятся две переменные a и b? С той целью, чтобы грамотно вывести на экран результат. В цикле с предусловием первоначальные значения переменных потеряются, поэтому вывести в скобках заданные пользователем m, n не представится возможным. Конечно, строку 21 можно значительно упростить, написав только writeln (proizv div m). Но пользователь, который впервые будет знакомиться с программой, не поймет, что выведено на экран.

Ручная трассировка:

Как видно, ничего сложного в поиске решения НОД и НОК нет: ни в "Паскале", ни, собственно, в математике.