Ханой++

Задача.
Даны три стержня ?? 1,2,3. На стержни нанизано некоторое количество (N) дисков разного диаметра, как в детской пирамидке. Все диски расположены на стержнях в порядке уменьшения диаметра снизу вверх.
Необходимо найти последовательность перемещений, в результате которой все диски окажутся на стержне ? 1. За один ход можно снять верхний диск с одного стержня и поместить его на пустой стержень или на диск с большим диаметром.

по рекурсии для того чтобы 10 переложить на 1-й вначале надо первые 9 переложить на 2-й для этого надо первые 8 переложить на 1 и т.п


T(n)=2T(n/2)+1

Сообщение отредактировано: esperanto - 11.09.03, 11:52

Внимательно читаем условие  ;). Откуда переложить?

http://194.87.63.15/incoming/hanoj.zip

Даже если диски беспорядочно разбросаны по всем стержням, принципиально решение етой задачи не отличается от рекурсивного решения "классической" задачи о ханойской башне

Сообщение отредактировано: Visitor - 11.09.03, 17:37

Цитата Visitor, 11.09.03, 21:37:17

Даже если диски беспорядочно разбросаны по всем стержням, принципиально решение етой задачи не отличается от рекурсивного решения "классической" задачи о ханойской башне

это надо доказать
имхо на первый взгляд не правильно

Во, цитирую:

Цитата esperanto, 11.09.03, 15:03:09

по рекурсии для того чтобы 10 переложить на 1-й вначале надо первые 9 переложить на 2-й для этого надо первые 8 переложить на 1 и т.п

Дык примерно такие же соображения будут при решении указанной задачи

Цитата Visitor, 11.09.03, 21:37:17

принципиально решение етой задачи не отличается от рекурсивного решения "классической" задачи о ханойской башне

Помните советский анекдот про магазин "Принцип"?

А в етом алгоритме тоже ничего нет Особенного

http://194.87.63.15/incoming/hanoj.zip

Вроде бы то, что надо. Но вопросы остаются.
1. Как доказать что этот алгоритм дает оптимальный вариант?
2. Нельзя ли найти более простой, подобный известному решению классической задачи?

Не смог разобраться в программе по той ссылке, потому, что устал читать не относящиеся к сути алгоритма навороты с графикой.

Цитата Trurl, 12.09.03, 17:06:04

http://194.87.63.15/incoming/hanoj.zip

Вроде бы то, что надо. Но вопросы остаются.
1. Как доказать что этот алгоритм дает оптимальный вариант?
2. Нельзя ли найти более простой, подобный известному решению классической задачи?

1. Ех.... Ну вы сами просили....
Доказательство для классической задачи:

a, b, c -- номера стержней
э -- "принадлежит"
a->b -- операция "перемещение диска со стержня a на стержень b"
{} -- в фигурных скобках записывается последовательность перемещений дисков, т.е., алгоритм
|A| -- сложность алгоритма A, т.е., длина последовательности или количество перемещений в етом алгоритме
a,b,c э [1,2,3],
a!=b,
a!=c,
b!=c
Оптимальным алгоритмом будем считать алгоритм с минимальной сложностью

Ограничение 0. Все диски имеют разный диаметр.
Ограничение 1. Перемещать можно только диск, занимающий самое верхнее место на стержне.
Ограничение 2. Любой диск может только а) занимать самое нижнее место на стержне или б) лежать на диске большего диаметра. Алгоритм, на каждом шаге которого всегда выполняются ограничения 1 и 2 будем называть корректным.
Ограничение 3. Перед началом выполнения алгоритма An(a, b) на стержне a находятся n дисков, помещенные туда с учетом Ограничения 2 (самый большой диск -- внизу), остальные стержни пустые.

Теорема 1.
Пусть An(a, b), a!=b -- оптимальный корректный алгоритм перемещения n дисков со стержня a на стержень b.
Тогда An+1(a,b) = {An(a,c),a->b,An(c,a)} -- оптимальный корректный алгоритм перемещения n+1 дисков со стержня a на стержень b.

В самом деле, рассмотрим операцию a->b перемещения самого большого n+1го диска. Она может быть выполнена только тогда, когда 1) на стержне b нет ни одного диска, т.к., все другие диски меньшего диаметра, см. Ограничение 2 и 2) самый большой диск является самым верхним диском на стержне a, см. Ограничение 1. Таким образом, перед перемещением a->b самого большого диска необходимо выполнить перемещение всех дисков меньшего диаметра на третий стержень c. По условию, оптимальным алгоритмом перемщения n меньших дисков авляется алгоритм An(a,c).

После перемещения a->b самого большого n+1го диска, необходимо переместить оставшиеся n дисков на стержень b. По условию, оптимальным алгоритмом такого перемещения является алгоритм An(c,b). Т.о., среди алгоритмов, содержащих перемещение a->b самого большого n+1го диска, рассматриваемой алгоритм является оптимальным и имеет сложность |An+1(a,b)| = 2*|An(a,b)|+1 (|An(a,b)| = |An(a,c)| = |An(b,c)| из соображений симметрии).

Легко показать, что алгоритм {...,a->c,...} где имеется перемещение самого большого n+1го диска a->c имеет большую сложность, чем рассмотренный выше. Рассуждая аналогично, получим, что корректный алгоритм, содержащий такое перемещение имеет начало такого вида {An(a,b),a->c}.

Теперь, чтобы переместить n+1й диск на стержень b необходимо выполнить алгоритм не меньшей сложности, чем {An(b,a),c->b}. Т.о. сложность алгоритма Bn+1, содержащего перемещение a->c n+1го диска |Bn+1| >= 2*|An(a,b)|+2 > 2*|An(a,b)|+1 = |An+1(a,b)|.

Других вариантов перемещения n+1го диска со стержня a, очевидно, нет.

Следовательно, An+1(a,b) = {An(a,c),a->b,An(c,a)} таки является оптимальным корректным алгоритмом перемещения n+1 дисков со стержня a на стержень b.

Теперь индукция.

Очевидно, что A1(a,b) = {a->b} является оптимальным алгоритмом перемещения одного диска со стержня a на стержень b.
Ипользуя доказанную Теорему 1 мы можем по индукции строить алгоритмы перемещения 2, 3,... n дисков. Все они будут оптимальными и корректными. (Побочный р-т: |An(a,b)| = 2**n - 1)

Если не лениво, можете построить доказательство для вашей задачи -- оно будет похожим но более длинным (мне -- лениво ).

2. Нет. Оно совпадет с красивым "классическим" только в конце.

Сообщение отредактировано: Visitor - 12.09.03, 18:33

Я не просил доказательства, тем более такого длинного для классического
варианта. Оно очевидно. Меня интересует алгоритм из программы,которую  
предложил Оzzя.

Цитата Trurl, 13.09.03, 15:14:06

предложил Оzzя.

Не я Мой ученик Илья Кудиров. Найду его e-mail - отправлю к автору, разбирайтесь с ним.

http://www.proza.ru:8004/texts/2001/10/22-97.html

Дык дайте сам алгоритм, который без вот етих "procedure SHTRAF"