Паскаль. Основы программирования


Задание 3 - часть 3


По алгоритму составим программу:

Program

Problem2a; 

     uses WinCrt;

     var

        a, b, n, k : integer;

     begin

        write('Введите первое число '); readln(a);

        write('Введите второе число '); readln(b);

          if a > b then k := b else

k := a;

             n := k + 1;

             repeat

                n := n - 1

             until (a mod n = 0) and (b mod

n = 0) ;

        writeln('НОД чисел ', a, ' и ', b, ' равен ', n)

     end.

При такой конструкции программы уже не надо проверять деление одного числа на другое (подумайте почему?).

Конечно, эти программы можно усовершенствовать, сделать менее трудоемкими для компьютера (попробуйте это сделать сами), и все-таки нам придется обратиться к алгоритмам Евклида, которые до сих пор являются совершенством в математике.

Они отличаются не только математической оригинальностью, но и простотой. Все гениальное просто!

Итак, первый

из алгоритмов Евклида нахождения НОД состоит в следующем.

Например, надо найти НОД чисел 36 и 45.

Вычитаем из большего числа меньшее: 45 - 36 = 9,

заменяем большее из данных чисел на разность, получаем два других числа:

9 и 36;

снова, из большего вычитаем меньшее: 36 - 9 = 27,

заменяем большее на разность, получаем 9 и 27; из большего вычитаем меньшее:

27 - 9 = 18,

заменяем большее на разность, получаем 9 и 18; из большего вычитаем меньшее:

18 - 9 = 9,

заменяем большее на разность, получаем 9 и 9.

Получены два равных числа, значит НОД чисел 45 и 36 равно 9.

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

Этот алгоритм Евклида имеет строгое математическое обоснование и не может вызывать никаких сомнений.


Программа

Program Problem2b;

     uses WinCrt;

     var

        a, b, c, a1, b1 : integer;

     begin

        write('Введите первое число '); readln(a);




Начало  Назад  Вперед