Новый ум короля: О компьютерах, мышлении и законах физики | страница 46

Нужно заметить, что на схеме эта процедура не до конца разбита на простейшие составляющие, поскольку мы неявным образом предположили, что нам уже «известно», как выполнять необходимую базовую операцию получения остатка от деления двух произвольных натуральных чисел А и В. Эта операция, в свою очередь, также алгоритмична и выполняется при помощи хорошо знакомой нам со школы процедуры деления. Эта процедура, на самом деле, сложнее, чем все остальные части алгоритма Евклида, но и она может быть представлена в виде блок-схемы. Основное затруднение здесь возникает из-за использования привычной «десятичной» записи натуральных чисел, что вынуждает нас выписывать все таблицы умножения, учитывать перенос и т. п. Если бы для представления некоторого числа n мы использовали последовательность из n каких-нибудь одинаковых знаков, например, пяти звездочек (*****) для обозначения пятерки, то определение остатка свелось бы к совершенно элементарной алгоритмической операции. Для того чтобы получить остаток от деления А на В, достаточно просто убирать из записи числа А последовательность знаков, представляющих В, до тех пор, пока на некотором этапе оставшееся число знаков в записи А не станет недостаточным для выполнения следующего шага. Эта последовательность знаков и даст требуемый ответ. Например, желая получить остаток от деления 17 на 5, мы просто будем последовательно удалять ***** из *****************, как это показано ниже:

*****************

************

*******

* *,

и в результате получим, очевидно, 2, так как следующее удаление уже станет невозможно. Блок-схема изложенного выше процесса нахождения остатка от деления путем последовательных вычитаний приведена на рис. 2.2.

Чтобы придать блок-схеме алгоритма Евклида завершенный вид, мы должны подставить схему отыскания остатка в соответствующий блок справа в центре предыдущей схемы. Такая подстановка одного алгоритма в другой — распространенная в компьютерном программировании процедура. Алгоритм вычисления остатка, изображенный на рис. 2.2, служит примером подпрограммы, иначе говоря, это алгоритм (как правило, уже известный), вызываемый и используемый по мере надобности в ходе выполнения основного алгоритма.

Безусловно, обозначение числа