С алгоритмом Евклида можно ассоциировать очень интересные по своей структуре блочные системы. Их смысл проще всего разъяснить, если представить алгоритм Евклида в виде некоторой серии операций вычитания, а не деления (следует, однако, отметить, что в случае, когда используются операции вычитания, корректнее было бы говорить об "алгоритме Антанаиресис", а не об алгоритме, который мы привыкли называть "алгоритмом Евклида").

При этом, поскольку мы собираемся применять алгоритм Евклида только к натуральным числам (т. е. к числам 1, 2, 3, 4, ... ), нам нужно будет также учесть ограничения, налагаемые на операцию вычитания в арифметике натуральных чисел. А именно: запрещается производить вычитание из меньшего большего, а также производить вычитание равных между собой чисел (поскольку в результате получился бы нуль, а нуль не является натуральным числом).

С учетом этих ограничений, суть алгоритма Евклида, реализованного через вычитания, можно выразить одним предложением: "Вычти из большего меньшее, а затем попытайся сделать то же самое с получившейся разностью и меньшим из чисел".

Теперь мы выполняем для вновь сформированной "текущей пары чисел" второй шаг алгоритма Евклида: определяем, какой из членов пары больше и вычитаем из него меньший член, формируя тем самым очередную разность (в данном случае, это будет число 3). Затем готовим почву для третьего шага, формируя новую "текущую пару чисел" и т. д.

Действуя подобным образом, мы рано или поздно придем к ситуации (в рассматриваемом примере это произошло после 4-го шага), когда во вновь сформированной "текущей паре чисел" оба члена будут равны, т. е. вычитание одного члена из другого станет невозможным (в силу отмеченного выше ограничения на операцию вычитания в арифметике натуральных чисел). Такая ситуация будет символизировать собой завершение алгоритма. Можно доказать, что члены этой последней "текущей пары чисел" равны наибольшему общему делителю (НОД) исходных натуральных чисел, к которым применялся алгоритм Евклида. Т. е. в контексте рассмотренного примера мы имеем НОД(21, 9) = 3.

Покажем теперь, каким образом с рассмотренным примером работы алгоритма Евклида можно ассоциировать разбиение прямоугольника на квадраты (лично я впервые увидел подобного рода разбиения в книге Н. Н. Воробьева). Допустим, что у нас имеется некоторый исходный прямоугольник шириной 21 и высотой 9 условных единиц (у. е.). Первый шаг работы алгоритма Евклида мы моделируем тем, что вписываем в исходный прямоугольник квадрат размером 9 у. е., как это изображено на рисунке ниже. Отметим при этом, что "остаточный прямоугольник", возникающий после вписывания квадрата, имеет размеры, в точности соответствующие "новой текущей паре чисел", формируемой алгоритмом Евклида после выполнения первого шага.

Следовательно, моделируя второй шаг алгоритма Евклида, вписываем в этот "остаточный прямоугольник" еще один квадрат размером 9 у. е. и получаем новый остаточный прямоугольник, соответствующий по своим размерам "текущей паре чисел", формируемой алгоритмом Евклида после выполнения второго шага.

Продолжая в том же духе, мы достигаем после 4-го шага вписывания квадратов ситуации, когда "остаточным прямоугольником" оказывается квадрат размером 3 у. е. Тем самым, разбиение исходного прямоугольника на квадраты завершено. Вполне очевидно, каким образом этот процесс "моделирует" работу алгоритма Евклида.

Если мы внимательно присмотримся к процессу вписывания квадратов в исходный прямоугольник, то увидим, что каждый акт вписывания предваряется анализом текущего "остаточного прямоугольника" (на самом первом шаге в качестве "остаточного прямоугольника" выступает исходный прямоугольник). А именно: анализируется соотношение длин горизонтальных и вертикальных сторон прямоугольника.

Если длина горизонтальной стороны текущего остаточного прямоугольника больше длины его вертикальной стороны, то квадрат вписывается в этот прямоугольник слева, если меньше — то сверху; если же они равны, то ничто уже больше никуда не вписывается. Таким образом, алгоритм вписывания квадратов в исходный прямоугольник очень прост.

На Странице 5.1.1 представлен программно реализованный "Визуализатор алгоритма Евклида". Для любой выбранной вами пары натуральных чисел он (в зависимости от ваших команд) сделает следующее:

(На Странице 5.1.2 представлен тот же самый визуализатор, но раскрывающийся на весь экран. Чтобы вернуться из него обратно сюда, нажмите на клавиатуре CTRL + W)

Окно визуализатора покрыто сеткой с размером клетки равным одному у. е. (при желании вы можете ее скрыть). Определитесь с исходной парой натуральных чисел, к которой будет применяться алгоритм Евклида, и введите члены этой пары в соответствующие поля вверху окна программы. Затем нажмите кнопку "Визуализировать!". В ответ на это действие будет отображен прямоугольник, ширина которого (в у. е.) равна первому числу выбранной вами пары, а высота — второму, и будет запущен процесс вписывания в него квадратов.

По умолчанию квадраты будут вписываться через промежуток времени в 1 секунду (1000 миллисекунд). Вы можете изменить этот промежуток. Для этого введите нужное вам значение (в миллисекундах) в поле под кнопкой "Скорость" и обязательно нажмите на эту кнопку, чтобы введенное значение установилось.

В качестве "исходной" вы, в принципе, можете ввести абсолютно произвольную пару натуральных чисел (конечно, если ее члены будут слишком велики, то для обозрения получившегося прямоугольника вам придется прибегнуть к услугам полос прокрутки). Вы можете испытать следующие пары чисел, структура прямоугольника для которых получается, на мой взгляд, интересной: 33, 28;  11, 18;  28, 17;  48, 17;  56, 22; 
55, 33;  57, 42;  56, 19.

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