Форум: "Потрепаться";
Текущий архив: 2002.06.27;
Скачать: [xml.tar.bz2];
Вниз
Задачка Найти похожие ветки
← →
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
> сделал наглядную программку, симпатично получилось :)
Скинь проект на мыло если не жалко :)
(А то лень самому рисовать эти Ханойские башни)
← →
MBo (2002-05-26 11:04) [8]в кладовку положил
http://delphi.mastak.ru/cgi-bin/download.pl?get=1022396476&n=1
← →
Igorek (2002-05-26 11:10) [9]2 MBo
Слушай, а кто здесь большой любитель задачек?
← →
MBo (2002-05-26 11:31) [10]Мало таких ;(
Но есть
Страницы: 1 вся ветка
Форум: "Потрепаться";
Текущий архив: 2002.06.27;
Скачать: [xml.tar.bz2];
Память: 0.46 MB
Время: 0.007 c
