Поиск
 
 

Результаты :
 


Rechercher Расширенный поиск

Кто сейчас на форуме
Сейчас посетителей на форуме: 2, из них зарегистрированных: 0, скрытых: 0 и гостей: 2

Нет

[ Посмотреть весь список ]


Больше всего посетителей (9) здесь было Вс Фев 11, 2018 12:54 pm
Самые активные пользователи за неделю
Ярослав
 


Ханойские башни

Перейти вниз

Ханойские башни

Сообщение автор Ярослав в Вт Июн 13, 2017 7:31 pm

Как решить Ханойские башни и при чём здесь рекурсия?

Проектировать рекурсивные функции можно по принципу математической индукции:

• Сначала надо сформулироавть задачу, чтобы она зависела от некоторого целого числа N.
• Рассмотрим минимальное N, при котором задача ещё имеет смысл. Обычно её можно решить для N = 1 напрямую. Запишем решение нашей задачи в виде функции f (n), и в этой функции опишем рассмотренный случай n = 1.
• Если мы умеем решать нашу задачу для некоторого числа N, сможем ли мы решить задачу для N + 1? Если мы разработаем алгоритм сведения задачи для N+1 к уже решённой для N, то мы автоматически решим её для всех N:

Решение задачи при N=4 сводится к решению задачи при N=3, N=3 в свою очередь сводится к N=2, N=2 сводится к N=1, а N=1 уже решена.
4->3->2->1
И такое рассуждение будет работать для любого N.

В терминах нашей проектируемой рекурсивной функции f(n), в ней нужно придумать переход, как решить проблему f(n), причём разрешается пользоваться f с меньшими n, как уже решёнными.
avatar
Ярослав
Admin

Posts : 548
Join date : 2016-12-21
Location : Москва

Посмотреть профиль http://itstep.forum2x2.ru

Вернуться к началу Перейти вниз

Re: Ханойские башни

Сообщение автор Ярослав в Вт Июн 13, 2017 7:45 pm

Это был общий принцип. Теперь конкретнее, о Ханойских башнях.

Я формулирую задачу в терминах N:
• Необходимо научиться перемещать башенку высоты N с первого стержня на третий, используя второй как вспомогательный. В процессе можно использовать только перемещения по одному диску, соблюдая правило размеров. Зато шагов может быть много — столько, сколько нужно.

Что произойдёт при N=1?
• Необходимо научиться перемещать 1 диск с первого стержня на третий, используя второй как промежуточный. Ясно, что один диск переместить можно всегда — это базовая операция в нашей задаче. Так что f(1) будет состоять в следующем:

Проверка, что n == 1. Если это так, просто перемещаем диск.

• Теперь рассмотрим произвольное N+1. Его нужно свести к более простой задаче, например, достаточно свести её к N.

https://i58.servimg.com/u/f58/19/66/40/03/hanoi11.png


Следуя этой картинке, рекурсивная функция f(n) должна:
1) проверить и исключить случай n == 1, потому что он особый и решается просто. (Это дно рекурсии).
2) раз n != 1, значит оно больше. Мы будем сводить задачу к n-1.
3) согласно картинке, первым шагом мы должны сделать рекурсивный вызов f(n-1)
4) затем сделать простое перемещение
5) затем сделать ещё один рекурсивный вызов f(n-1)

При написании шагов 3) и 5) выясняется, что у нашей функции больше параметров, чем только высота башни n. Нам ещё нужно уметь указывать, перемещать с какого стержня на какой. Наконец, полезной была бы информация о том, какой стержень использовать как промежуточный.

Итак, заголовок функции будет выглядеть так:
Код:
void solveHanoi (int n, int from, int to, int assist)
avatar
Ярослав
Admin

Posts : 548
Join date : 2016-12-21
Location : Москва

Посмотреть профиль http://itstep.forum2x2.ru

Вернуться к началу Перейти вниз

Вернуться к началу


 
Права доступа к этому форуму:
Вы не можете отвечать на сообщения