Форум программистов, компьютерный форум, киберфорум
Pascal (Паскаль)
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.71/21: Рейтинг темы: голосов - 21, средняя оценка - 4.71
2 / 2 / 0
Регистрация: 15.10.2013
Сообщений: 87
1

Построить алгоритм и граф решения задачи "Ханойские башни" при числе шпилей 4

28.10.2014, 21:28. Показов 3978. Ответов 4
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Добрый вечер! Помогите, пожалуйста, написать алгоритм программы.

Необходимо построить алгоритм и граф решения задачи "Ханойские башни" при числе шпилей 4, реализовать алгоритм на любом языке программирования.
Алгоритм прилагается.Doc1.doc

Буду очень благодарна!(оплата за задание)
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
28.10.2014, 21:28
Ответы с готовыми решениями:

Алгоритм решения задачи “Ханойские Башни”
Кто может, напишите хотя бы один алгоритм, пожалуйста. Алгоритм решения задачи “Ханойские...

Алгоритм решения задачи “Ханойские Башни”.
Помогите хоть один написать. Алгоритм решения задачи “Ханойские Башни”.

Реализовать алгоритм решения задачи «Ханойские башни»
задание: Реализовать алгоритм для решения задачи «Ханойские башни». Выписать последовательность...

Создать программу визуального отображения решения задачи "Ханойские башни"
Помогите создать программу визуального отображения решения задачи "Ханойские башни" .

Ханойские башни: демонстрация решения
Добрый день! Требуется решить такую задачу Для начала, хотелось бы попросить помочь с...

4
Почетный модератор
64305 / 47600 / 32743
Регистрация: 18.05.2008
Сообщений: 115,181
29.10.2014, 10:20 2
Цитата Сообщение от Tatajna Посмотреть сообщение
на любом языке программирования.
А все таки? Эти картинки нужно просто нарисовать?
0
2 / 2 / 0
Регистрация: 15.10.2013
Сообщений: 87
29.10.2014, 10:26  [ТС] 3
В задании написано: "построить алгоритм и граф решения задачи "Ханойские башни" при числе шпилей 4, реализовать алгоритм на любом языке программирования".
Как бы алгоритм разложения я в Wordе нарисовала. А в программе думаю чтоб показан этот алгоритм был.
0
Почетный модератор
64305 / 47600 / 32743
Регистрация: 18.05.2008
Сообщений: 115,181
29.10.2014, 10:56 4
А задача совсем непростая ибо сказано в Википедии
С четырьмя и более стержнями

Хотя вариант с тремя стержнями имеет простое рекурсивное решение,
оптимальное решение Ханойской башни с четырьмя стержнями является нерешённой проблемой.
Из этого не следует, что в случае четырёх и более стержней не существует алгоритма
для нахождения оптимальных решений.
Достаточно представить головоломку в виде неориентированного графа,
сопоставив размещениям дисков вершины, а ходам — рёбра, и использовать любой алгоритм поиска
(например, поиск в ширину) для нахождения оптимального решения.
Однако эффективной стратегии определения оптимального решения для большого числа дисков нет:
количество ходов, необходимое для решения головоломки с 10 стержнями и 1000 дисками,
остаётся неизвестным.
Существует предположительно оптимальный алгоритм Фрейма — Стюарта, разработанный в 1941 году.
Связанная гипотеза Фрейма — Стюарта утверждает, что алгоритм Фрейма — Стюарта всегда
находит оптимальное решение.
Оптимальность алгоритма Фрейма — Стюарта была экспериментально проверена вплоть
до 30 дисков на 4 стержнях[5].

Алгоритм Фрейма — Стюарта, дающий предположительно оптимальное решение
для четырёх (или более) стержней, описывается следующим образом:
Пусть n — количество дисков.
Пусть r — число стержней.
Определим T(n,r) как наименьшее число ходов, необходимое для переноса n дисков
с использованием r стержней.
Алгоритм может быть описан рекурсивно:
Для некоторого k, 1<=k<n, перенести верхние k на стержень i,
не являющийся ни начальным, ни конечным стержнем, затратив на это T(k,r) ходов.
Не используя стержень i, содержащий теперь верхние k дисков,
перенести оставшиеся n-k дисков на конечный стержень, используя только
оставшиеся r-1 стержней и затратив на это T(n-k,r-1) ходов.
Наконец, переместить верхние k дисков на конечный стержень, затратив на это T(k,r) ходов.
На весь процесс требуется 2T(k,r)+T(n-k,r-1) ходов.
Значение k выбирается таким образом, чтобы значение этого выражения было минимальным.
Кстати у Вас не указано количество дисков.
0
2 / 2 / 0
Регистрация: 15.10.2013
Сообщений: 87
29.10.2014, 11:05  [ТС] 5
4 диска, 4 стержня
0
29.10.2014, 11:05
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
29.10.2014, 11:05
Помогаю со студенческими работами здесь

Ханойские башни, вывод решения по шагам
Помогите мне пожалуйста!У меня есть готовый исходник решения этого алгоритма!Необходимо сделать...

Автоматизация задачи "Ханойские башни"
#include &lt;iostream&gt; #include &lt;vector&gt; #include &lt;cmath&gt; #include &lt;windows.h&gt; using namespace...

Алгоритм программы "Ханойские башни"
Добрый вечер. Нужна ваша помощь, товарищи. Нужно разработать программу &quot;Ханойские башни&quot;. Если у...

Разработать алгоритм и программу решения задачи, в которой построить бинарное дерево
Разработать алгоритм и программу решения задачи, в которой построить бинарное дерево и реализовать...

Алгоритм для задачи о построении башни
Добрый день. Готовлюсь к соревнованиям по спортивном программированию. Никак не могу придумать...

Ханойские башни
Легенда гласит,что где-то в Ханое находится храм,в котором размещеа следущая конструкция:на...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
5
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru