Реклама

Наш канал:

Таненбаум Э.- Архитектура компьютера. стр.312

Чтобы переместить п дисков с колышка 1 на колышек 3, нужно сначала перенести 72-1 дисков с колышка 1 на колышек 2, затем перенести один диск с колышка 1 на колышек 3, потом перенести п - 1 диск с колышка 2 на колышек 3. Решение этой задачи для трех дисков иллюстрирует рис. 5.24.

Для решения задачи нам нужна процедура, которая позволяет переместить п дисков с колышка i на колышек j:

towers (n, i, j)

Рис. 5.23. Исходное положение дисков в задаче «Ханойская башня» для пяти дисков

Рис. 5.24. Решение задачи «Ханойская башня» для трех дисков

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

Все решение представлено в листинге 5.6. Рассмотрим такой вызов процедуры:

towers (3, 1, 3)

Этот вызов порождает еще три вызова:

towers (2, 1, 2) towers (1, 1, 3) towers (2, 2, 3)

Первый и третий вызовы производят по три вызова каждый, и всего получится семь.

Листинг 5.6. Процедура для решения задачи «Ханойская башня»

public void towers (int n, int i, int j) { int k; if (n == 1)

System.out.printlnCTlepeMecTMTb диск с " + i + "на" + j); else { k=6-i-j;

towers(n-l, i, k); towers (1, i, j); towers (n-1. k. j);

}

}

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

Помимо указателя стека (Stack Pointer, SP), который указывает на вершину стека, удобно иметь указатель фрейма (Frame Pointer, FP), указывающий на заданное место во фрейме, например, на связующий указатель, как в IJVM, или на первую локальную переменную.

На рис. 5.25 изображен стековый фрейм для машины с 32-разрядным словом. При первом вызове процедуры towers в стек помещаются значения n, i и j, а затем выполняется команда CALL, которая помещает в стек адрес возврата, 1012. Вызванная процедура сохраняет в стеке старое значение FP (1000) в ячейке 1016, а затем передвигает указатель стека для обозначения места хранения локальных переменных.

При наличии только одной 32-разрядной локальной переменной (к), указатель стека увеличивается на 4 — до 1020. На рис. 5.25, а показан результат всех этих действий.

Рис. 5.25. Состояние стека во время выполнения программы из листинга 5.6

Первое, что должна сделать процедура после вызова, — сохранить предыдущее значение FP (так, чтобы его можно было восстановить при выходе из процедуры), скопировать значение SP в FP и, возможно, увеличить SP на одно слово, в зависимости от того, куда указывает FP нового фрейма. В этом примере FP указывает на первую локальную переменную (хотя в IJVM регистр LV указывал на связующий указатель). Разные машины оперируют указателем фрейма немного по-разному, иногда помещая его в самый низ стекового фрейма, иногда — в вершину, а иногда — в середину, как на рис. 5.25. В этом отношении стоит сравнить рис. 5.25 с рис. 4.10, чтобы познакомиться с двумя разными способами обращения со связующим указателем. Возможны и другие способы. Но в любом случае обязательно должна быть возможность выйти из процедуры и восстановить предыдущее состояние стека.