Для любознательных

Ханойские башни. Задача о разрезании прямоугольника

Ханойские башни - это древняя игра. Заключается она в следующем. Имеются три стержня, на одном из них (например, на правом) насажены диски разных размеров, причем диски располагаются так, чтобы стержень с дисками напоминал башню, т.е. внизу располагаются самые большие диски, а вверху - маленькие. Цель игры - перенести башню с правого стержня на левый, причем за один раз можно переносить только один диск и при этом можно насаживать только диск с меньшим диаметром на диск с большим диаметром. Средний стержень является вспомогательным для временного хранения дисков.

В программе применяются вложенность подпрограмм и рекурсивный вызов подпрограмм.

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

Program Tower;
Type
Position = (Left, Centre, Right);
Var
N: integer;
{ - - - - - - - - - - - - - - - - - - - -}
Procedure MoveDisk (From, Tol: Position);
Procedure writePos (P: Position);
Begin
case P of
Left: write ('1');
Centre: write ('2');
Right: write ('3');
end;
End;
Begin
writePos (From);
write('->');
writePos (Tol);
writeln
End;
{ - - - - - - - - - - - - - - - - - - - -}
Procedure MoveTower(Hight: integer; From, Tol, Work: Position);
Begin
if Hight>0
then
begin
MoveTower(Hight-1, From, Work, Tol);
MoveDisk (From, Tol);
MoveTower(Hight-1, Work, Tol, From);
end;
End;
{ - - - - - - - - - - - - - - - - - - - -}
Begin
writeln('Введите количество колец ');
readln(N);
MoveTower(N, Right, Left, Centre);
End.

Задание. Изучите текст программы. Введите текст программы, запишите файл на диск и откомпилируйте его. после того, как компиляция выполнится успешно, задайте для просмотра в окне отладчика переменные Hight, From, Tol, Work. Установите видимыми одновременно окно редактора с текстом программы и окно просмотра. Исполните программу в пошаговом режиме с заходом в процедуры и пронаблюдайте за рекурсивным вызовом процедуры MoveTower. Дополните программу операторами графического режима, чтобы наглядно можно было представить перенос дисков со стержня на стержень. Дополните текст программы комментариями.

Рассмотрим задачу о разрезании прямоугольника.

Задача. Дан прямоугольник со сторонами А и В, где А, В - натуральные числа. Начинаем отсекать от него квадраты. Сколько таких квадратов можно отсечь, если каждый раз отсекается самый большой квадрат?

Для решения этой задачи нам нужны будут функции Max и Min для переопределения длины и ширины прямоугольника. А также введем вспомогательные переменные Х и У (У>=Х), соответствующие уменьшающимся сторонам прямоугольника, и вспомогательную переменную D, которая определяет уменьшение размеров прямоугольника после очередного отсечения наибольшего квадрата, сторона которого находится как Х:=Min(D, X) и продолжаем цикл.

В программе нам нужно организовать цикл, в котором сторона У уменьшается каждый раз на Min(D, X) до тех пор, пока не останется последний квадрат или У не станет меньше Х. В последнем случае переименовываем стороны оставшегося прямоугольника как Y:= Max(D, X) и X:= Min(D, Х) и продолжаем цикл.

Program OtsehKvadr;
Var
A, B, D, K, X, Y: integer;
{ - - - - - - - - - - - - - - - - - - - -}
Function Min(I,J: integer): integer;
Begin
If I<J
Then
Min:= I
Else
Min:= J;
End;
{ - - - - - - - - - - - - - - - - - - - -}
Function Max(I,J: integer): integer;
Begin
if I>J
then
Max:= I
else
Max:= J;
End;
{ - - - - - - - - - - - - - - - - - - - -}
Begin
repeat
writeln ('Введите два натуральных числа ');
readln(A,B);
until (A>0) and (B>0);
K:= 1;
X:= Min(A, B);
Y:= Max(A, B);
while X<>Y do
begin
K:= K+1;
D:= Y-X;
Y:= Max(D, X);
X:= Min(D, X);
end;
writeln('Искомое число квадратов: ',K);
End.

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