Главная страница
    Top.Mail.Ru    Яндекс.Метрика
Форум: "Потрепаться";
Текущий архив: 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.006 c
1-88925
Коля
2002-06-15 05:05
2002.06.27
добавить документ в меню


8-88966
Tpv
2002-02-15 21:55
2002.06.27
Уровень звукого сигнала.


8-88963
Pete
2002-02-18 15:34
2002.06.27
Помогите реализовать...


3-88701
unreger
2002-05-27 05:54
2002.06.27
VB+MSSQL - > Delphi6+MSSQL, переход


3-88728
kay
2002-06-01 14:14
2002.06.27
Связи





Afrikaans Albanian Arabic Armenian Azerbaijani Basque Belarusian Bulgarian Catalan Chinese (Simplified) Chinese (Traditional) Croatian Czech Danish Dutch English Estonian Filipino Finnish French
Galician Georgian German Greek Haitian Creole Hebrew Hindi Hungarian Icelandic Indonesian Irish Italian Japanese Korean Latvian Lithuanian Macedonian Malay Maltese Norwegian
Persian Polish Portuguese Romanian Russian Serbian Slovak Slovenian Spanish Swahili Swedish Thai Turkish Ukrainian Urdu Vietnamese Welsh Yiddish Bengali Bosnian
Cebuano Esperanto Gujarati Hausa Hmong Igbo Javanese Kannada Khmer Lao Latin Maori Marathi Mongolian Nepali Punjabi Somali Tamil Telugu Yoruba
Zulu
Английский Французский Немецкий Итальянский Португальский Русский Испанский