Ханойские башни, 4 стержня

@mike_marchuk · Регистрация: 06.10.2009

Студворк — интернет-сервис помощи студентам

Привет. Нужна помощь в написании программ: ханойские башни
Условия.
Ханойские башни. Задача похожа на всем известную, но нужно перекласть диски с помощью 4 стержней, а не 3.

Комментарий модератора

вторая задача в отдельную тему

@mike_marchuk · 07.10.2009, 15:24 **[ТС]**

Сообщение от mike_marchuk

Привет. Нужна помощь в написании программ: ханойские башни и про 15 монет.
Условия.
Ханойские башни. Задача похожа на всем известную, но нужно перекласть диски с помощью 4 стержней, а не 3.

15 монет. 15 монет разложены в ряд. Их нужно расскласть на 5 стопок по 3 в каждой. Условия: за один ход можно переставить одну монету и при каждом ходе монета должна перепрыгивать 3 монеты (если в одной стопке есть 3 монеты - значит монету можно переложить только через нее).

Если можно, то решение лучше приводить в виде списков.

Причем монету можно ложить междку кучек.

@Грымзик · 07.10.2009, 17:43

А если у меня например ...1 3 1... то можно сходить ...2 3... или ...1 1 3... или и так и так?

@mike_marchuk · 07.10.2009, 19:57 **[ТС]**

Сообщение от Грымзик

А если у меня например ...1 3 1... то можно сходить ...2 3... или ...1 1 3... или и так и так?

и так, и так

@Грымзик · 12.10.2009, 18:28

Вопрос еще актуален?

@mike_marchuk · 12.10.2009, 20:28 **[ТС]**

Сообщение от Грымзик

Вопрос еще актуален?

Да

@Грымзик · 13.10.2009, 21:40

Если в ханойских башнях надо найти решение за минимальное количество шагов,
то по-моему надо использовать поиск в ширину, но он очень медленно работает,
из-за большого выбора ходов, больше 3х дисков не советую задавать. Поиск в глубину
более быстрый, но в нем ну очень не оптимальное решение, поэтому лучше максимум 4 диска.

Prolog
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
?- searchWidth([[1,2,3],[],[],[]],[[],[],[],[1,2,3]]),nl,nl,nl,searchDepth([[1,2,3],[],[],[]],[[],[],[],[1,2,3]]).
 
append([], B, B).
append([A|ATail], B, [A|NewTail]) :- append(ATail, B, NewTail).
 
member(X,[X|_]).
member(X,[_|Tail]):-member(X,Tail).
 
element([H|_],1,H).
element([_|Tail],N,E):- integer(N), N>1, N1 is N-1, element(Tail,N1,E).
 
change([_|Tail],1,Y,[Y|Tail]).
change([H|Tail],N,Y,[H|NewTail]):- N1 is N-1, change(Tail,N1,Y,NewTail).
 
 
step(List,NewList):- for(I, 1, 4), for(J, 1, 4), element(List,I,[A|ATail]),((element(List,J,[B|BTail]), 
                A<B,change(List, I, ATail, TempList), change(TempList,J,[A,B|BTail],NewList));
                (element(List,J,[]),    change(List, I, ATail, TempList), change(TempList,J,[A],NewList))).
 
showAnswer([]).
showAnswer([A|B]) :- write(A),nl,showAnswer(B). 
 
reverse([ ], [ ]).
reverse([X|Xs],Zs) :- reverse(Xs, Ys), append(Ys, [X],Zs).
 
searchDepth(A, B) :- depth([A], B),!.
depth([Head|Tail], Head) :-  reverse(Tail, RTail), write("Search in depth"),nl, showAnswer(RTail), write(Head).
depth([Head|Tail], End ) :- step(Head,Next),not(member(Next,[Head|Tail])), append([Next],[Head|Tail],NewWay),depth(NewWay,End).
 
 
next([Head|Tail], Next):- step(Head,Next), not(member(Next,Tail)).
 
searchWidth(Begin, End) :-  width([[Begin]], End),!.
width([[Head|Tail]|_],Head) :-  reverse(Tail, Answer),write("Search in width"),nl, showAnswer(Answer),write(Head).
width([[Head|Tail] | End], Result) :-  findall( [Next, Head |Tail], next([Head|Tail],Next), List),
append(End, List, NewList), !, width(NewList, Result);width(End, Result).

@mike_marchuk · 14.10.2009, 00:26 **[ТС]**

Огромное спасибо.

@Грымзик · 14.10.2009, 02:23

Со второй задачей еще хуже, тут для 9 монет поиск в глубину уже
огромный ответ дает, а результата поиска в ширину так и не дождалась,
так что убрала его совсем.

Prolog
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
?- searchDepth([1,1,1,1,1,1,1,1,1]).
 
append([], B, B).
append([A|ATail], B, [A|NewTail]) :- append(ATail, B, NewTail).
 
append3(A,B,C,D):-append(A,Temp,D), append(B,C,Temp).
 
member(X,[X|_]).
member(X,[_|Tail]):-member(X,Tail).
 
summa([],0).
summa([H|Tail],S):- summa(Tail,S1), S is S1+H.
 
step(List,NewList):- append3(Begin,[X|Middle],[Y|End],List),summa(Middle,3),
        ((X>0, Y<3, X1 is X-1, Y1 is Y+1); (X<3, Y>0,X1 is X+1, Y1 is Y-1)),
        append(Begin,[X1|Middle],T), append(T,[Y1|End],NewList).
 
check([]).
check([H|Tail]):- (H==0; H==3), check(Tail).
 
showAnswer([]).
showAnswer([A|B]) :- write(A),nl,showAnswer(B). 
 
reverse([ ], [ ]).
reverse([X|Xs],Zs) :- reverse(Xs, Ys), append(Ys, [X],Zs).
 
searchDepth(A) :- depth([A]),!.
depth([Head|Tail]) :-  check(Head), reverse(Tail, RTail),showAnswer(RTail), write(Head).
depth([Head|Tail]) :- step(Head,Next),not(member(Next,[Head|Tail])),append([Next],[Head|Tail],NewWay),depth(NewWay).

@mike_marchuk · 14.10.2009, 16:47 **[ТС]**

Сообщение от Грымзик

Со второй задачей еще хуже, тут для 9 монет поиск в глубину уже
огромный ответ дает, а результата поиска в ширину так и не дождалась,
так что убрала его совсем.

Prolog
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
?- searchDepth([1,1,1,1,1,1,1,1,1]).
 
append([], B, B).
append([A|ATail], B, [A|NewTail]) :- append(ATail, B, NewTail).
 
append3(A,B,C,D):-append(A,Temp,D), append(B,C,Temp).
 
member(X,[X|_]).
member(X,[_|Tail]):-member(X,Tail).
 
summa([],0).
summa([H|Tail],S):- summa(Tail,S1), S is S1+H.
 
step(List,NewList):- append3(Begin,[X|Middle],[Y|End],List),summa(Middle,3),
        ((X>0, Y<3, X1 is X-1, Y1 is Y+1); (X<3, Y>0,X1 is X+1, Y1 is Y-1)),
        append(Begin,[X1|Middle],T), append(T,[Y1|End],NewList).
 
check([]).
check([H|Tail]):- (H==0; H==3), check(Tail).
 
showAnswer([]).
showAnswer([A|B]) :- write(A),nl,showAnswer(B). 
 
reverse([ ], [ ]).
reverse([X|Xs],Zs) :- reverse(Xs, Ys), append(Ys, [X],Zs).
 
searchDepth(A) :- depth([A]),!.
depth([Head|Tail]) :-  check(Head), reverse(Tail, RTail),showAnswer(RTail), write(Head).
depth([Head|Tail]) :- step(Head,Next),not(member(Next,[Head|Tail])),append([Next],[Head|Tail],NewWay),depth(NewWay).

И за это огромное спасибо.

Новые блоги и статьи Все статьи Все блоги /
Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .	Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .
Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .	Фото: Daniel Greenwood kumehtar 13.11.2025	Расскажи мне о Мире, бродяга kumehtar 12.11.2025 — Расскажи мне о Мире, бродяга, Ты же видел моря и метели. Как сменялись короны и стяги, Как эпохи стрелою летели. - Этот мир — это крылья и горы, Снег и пламя, любовь и тревоги, И бескрайние. . .

@Грымзик 2507 / 1483 / 37 Регистрация: 14.09.2009 Сообщений: 2,740
	07.10.2009, 17:43
	А если у меня например ...1 3 1... то можно сходить ...2 3... или ...1 1 3... или и так и так? 1

@Грымзик 2507 / 1483 / 37 Регистрация: 14.09.2009 Сообщений: 2,740
	12.10.2009, 18:28
	Вопрос еще актуален? 0

@mike_marchuk 0 / 0 / 1 Регистрация: 06.10.2009 Сообщений: 27
	14.10.2009, 00:26 [ТС]
	Огромное спасибо. 0