Задача: Составьте программу для нахождения наименьшего общего кратного двух чисел.
Наименьшее кратное двух чисел M и N следует понимать как минимальное число делящееся без остатка одновременно на M и на N.
Для решения задачи нам помогут следующие закономерности:
1. Произведение двух чисел M и N будет кратно обоим числам.
2. Если одно из чисел равно нулю, то наименьшее общее кратное найти нельзя, т.к. на ноль делить нельзя.
Решим задачу следующим образом:
1. Проверим не равно ли одно из чисел нулю. Если равно, то решения нет.
2. Примем произведение чисел за наименьшее общее кратное.
3. В цикле от произведения чисел до 1 проверяем равенство остатка от деления ключа цикла на первое число и на второе. Если остатки равны нулю – принимаем данный ключ цикла за наименьшее кратное и продолжаем цикл.
Реализация на Turbo Pascal 7:
program naimenshee_obshee_kratnoe; var n,m:integer; i,k:integer; delitsya:boolean; begin write('Vvedite N: '); readln(n); write('Vvedite M: '); readln(m); if (m<>0) and (n<>0) then begin k:=n*m; i:=k; while i>0 do begin if (i mod n=0) and (i mod m=0) then k:=i; i:=i-1; end; writeln('NOK ',m,' i ',n,' raven ',k) end else writeln('Na nol delit nelzya'); readln; end.
Блок-схема решения:
Блоксхема создана с помощью редактора http://www.gliffy.com
Метки: алгоритм