§ 2.2. Алгоритм деления

Проанализируем алгоритм деления в соответствии со схемой, предложенной в предыдущем параграфе. Нас интересует деление целых чисел, поэтому задача состоит в том, чтобы найти неполное частное и остаток от деления двух положительных целых чисел. При словах «частное» и «остаток» большинству из нас приходит на ум картинка вроде следующей:

В этом примере мы делим 1234 на 54; неполное частное оказалось равным 22, а остаток равен 46. В терминах первого параграфа вводом алгоритма служат делимое и делитель; в приведенном примере они равны соответственно 1234 и 54. Вывод состоит из частного и остатка, значения которых в примере 22 и 46.

В общем случае ввод алгоритма деления состоит из двух положительных чисел Деля a на b, мы получаем при выводе числа которые связаны с следующим образом:

Разумеется, это неполное частное, остаток от деления. У этого определения есть простая интерпретация, которую стоит иметь в виду. Допустим, мы хотим разломать полоску шоколада длины а на куски длины Алгоритм говорит, что в результате мы получим кусков длины и кусочек

меньшей длины Эту модель полезно помнить даже при применении теоремы в чисто математическом контексте.

На самом деле шоколадная полоска наводит на простейший алгоритм получения по заданным

Алгоритм деления Ввод: натуральные числа

Вывод: неотрицательные целые числа для которых выполнено равенство:

Шаг 1. Положить

Шаг 2. Если то сообщить: «частное равно а остаток равен , и остановиться; в противном случае перейти к шагу 3.

Шаг 3. Если то вычесть b из увеличить на 1 и возвратиться к шагу 2.

Такую форму записи алгоритмов мы будем использовать на протяжении всей книги. Для правильного прочтения алгоритмов нужно придерживаться следующих простых соглашений. Заметим, что алгоритм использует две переменные Имена переменных выбраны такими потому, что по завершении работы алгоритма их значения будут равны неполному частному и остатку от деления а на Для вычисления результата шаги 2 и 3 будут повторены несколько раз. Значит они образуют цикл. Значения переменных будут меняться от цикла к циклу. Именно поэтому они и называются переменными! Изменение значений переменных происходит на шаге 3. Инструкция «вычесть из означает, что переменной должно быть присвоено новое значение, равное ее значению после окончания предыдущего цикла, уменьшенному на Аналогично, инструкция «увеличить на означает,

что значение после окончания предыдущего цикла следует увеличить на 1.

Предположим, например, что Тогда после первого прохода через шаг 3 мы получим Если то, согласно алгоритму, мы должны выполнить шаг 3 еще раз. Проделав это, мы получаем и т.д. Почему такой процесс не может повторяться бесконечно? Другими словами, почему алгоритм прекращает свою работу? Заметим, что в результате последовательного применения шага 3 мы получаем следующую последовательность значений переменной

(см. скан)

Это убывающая последовательность целых чисел. Поскольку количество чисел между конечно, последовательность с необходимостью попадает в число, меньшее b. Тогда на шаге 2 работа останавливается, и алгоритм выводит значения переменных Вот почему алгоритм всегда завершает работу.