Задачка

← →
McSimm © (2002-05-24 12:18) [0]

Кому хочется поразмять мозги?
Напишите алгоритм решения задачи ханойских башен, но для произвольного начального состояния.
Т.е. На трех стержнях расположено N дисков в произвольных местах, но с соблюдением правила "меньший на большем".
Переместить все диски на стержень 3 минимальным количеством ходов.

← →
McSimm © (2002-05-24 14:29) [1]

Формализую условие.

//Количество дисков
const N = 10;
//Массив дисков. Если D[9]= 2, это означает, что диск 9 лежит на втором стержне. 1й диск - наименьший.
var D: array[1..N] of byte;

// Вспомогательная функция. Возвращает номер верхнего диска на стержне Axs или 0, если стержень пуст.
function FindDisk(Axs: byte): Integer; var I: Integer; begin Result := 0; for I := 1 to N do if D[I] = Axs then begin Result := I; Break end; end;

// Процедура перемещения диска со стержня _from на стержень _to:
procedure MoveDisk(_from, _to: Byte); var dF, dT: Integer; begin dF := FindDisk(_from); if dF = 0 then raise Exception.Create("Снятие диска с пустого стержня"); dT := FindDisk(_to); if (dF > dT) and (dT > 0) then raise Exception.Create("Больший диск нельзя ложить на меньший"); D[dF] := _to; // Moved := True; inc(Moves); // Memo1.Lines.Add(Format("Диск %d с %d на %d", [dF, _from, _to])) end;

// Инициализация массива:
// классическая задача
for I := 1 to N do D[I] := 1;
// произвольное расположение
for I := 1 to N do D[I] := 1+Random(3);
--------------------------------------------------
Напишите процедуру для перемещения всех дисков на 3й стержень.
(все D[i] должны стать равны 3)
Используйте дополнительные функции и процедуры, если хотите, но менять значение элементов массива D можно только с помощью процедуры MoveDisk.
--------------------------------------------------

← →
MBo © (2002-05-24 14:33) [2]

Не надо пока только решение приводить ;)
Задача потребует свободного времени.

← →
McSimm © (2002-05-24 14:35) [3]

Строчки
// Moved := True;
inc(Moves);
// Memo1.Lines.Add(Format("Диск %d с %d на %d", [dF, _from, _to]))
не обязательны. Попали случайно.

← →
Igorek © (2002-05-25 09:38) [4]

procedure f(N, S) begin if N = 0 then exit; if D[N]<>S then begin f(N-1, 6-D[N]-S); MoveDisk(D[N], S); end; f(N-1, S); end;

Решение - вызов f(D[10], 3).

Проверял только вручную ;-)

← →
Igorek © (2002-05-25 09:41) [5]

Сорри, вызов - f(10, 3)
;-)

← →
MBo © (2002-05-25 18:51) [6]

сделал наглядную программку, симпатично получилось :)

← →
Igorek © (2002-05-25 19:30) [7]

2 MBo

> сделал наглядную программку, симпатично получилось :)

Скинь проект на мыло если не жалко :)
(А то лень самому рисовать эти Ханойские башни)

в кладовку положил
http://delphi.mastak.ru/cgi-bin/download.pl?get=1022396476&n=1

2 MBo
Слушай, а кто здесь большой любитель задачек?

Мало таких ;(
Но есть

Задачка Найти похожие ветки