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


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


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

        a1 := a; b1 := b;

           while a <> b do

               begin

                  if a > b then a := a - b else

b := b - a

               end;

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

     end.

В этой программе использован цикл "пока", а не цикл "до". Как вы думаете почему? Для ответа на этот вопрос, замените цикл " пока" на цикл " до ...", т. е. операторы while ... do на repeat ... until ... Цикл станет таким:

                                    repeat

if a > b then a := a - b else b := b - a

                                    until a = b;

Как вам уже известно, цикл repeat обязательно выполняется хотя бы один раз. Если вы введете два равных числа, то программа "зациклится". В самом деле, условие a > b не выполняется, значит будет выполнен оператор b := b - a. b получит значение 0, цикл повторится, условие a > b выполняется, тогда a получит значение: a := a - 0, т.е. значение a не изменится, равенство a=b никогда не выполнится и цикл будет продолжаться "бесконечно", как говорят, "программа зациклится".

Если же применяется цикл while a <> b do ..., то даже при вводе равных чисел a и b (a = b), цикл не выполнится ни одного раза и НОД получит значение одного из равных чисел - a.

Существует и второй

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

Пусть a и b - натуральные числа, b <> 0 и r - остаток от деления a на b. Тогда НОД(a, b) = НОД(r, b).

Для доказательства используется очевидное свойство наибольшего общего делителя: натуральное число d тогда и только тогда является наибольшим общим делителем a и b, когда это число:

1) делит a и b, т.е. является общим делителем a и b;

2) делится на любой общий делитель a и b.

Пусть a

 b
 0 и a > 0. Тогда применение алгоритма Евклида происходит так: если b = 0, то НОД(a, b) = a. Иначе вычисляем r, равное остатку от деления a на b, и сводим задачу отыскания НОД(a, b) к задаче отыскания НОД(r, b).


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



Книжный магазин