0 / 0 / 0
Регистрация: 06.08.2009
Сообщений: 3
|
|||||||||||
1 | |||||||||||
Пояснение к Ханойским башням17.08.2009, 16:08. Показов 3058. Ответов 20
Метки нет (Все метки)
Здравствуйте. В программировании новичок, иду пока по книге Дейтелов, там в одной из первых глав наткнулся на задачу о Ханойских башнях. День бился головой об стол, потом посмотрел решение и все равно не смог до конца разобраться в данном коде:
Спасибо.
0
|
17.08.2009, 16:08 | |
Ответы с готовыми решениями:
20
Небольшое пояснение Пояснение к коду Пояснение к функциям Пояснение typedef |
12 / 11 / 4
Регистрация: 14.02.2009
Сообщений: 89
|
|
17.08.2009, 16:42 | 2 |
Прочитайте внимательно про рекурсивные функции и все поймете.
Рекурсивная функция это функция которая вызывает сама себя Строки: hanoy(num-1,a,c,b); hanoy(num-1,b,a,c); это и есть вызов функции в нутрии самой себя. Параметры передаются при вызове, причем счетчик вызовов уменьшается в параметре функции num-1. Переменные заменяются при каждом повторном вызове функции. return здесь нет и быть не может поскольку функция не возвращает значений, она объявлена как void. Я не знаю что такое” задача о Ханойских башнях” на судя по всему просто перестановка местами букв a='A';b='B';c='C'; num-раз. вот еще: http://ru.wikipedia.org/wiki/Рекурсия
0
|
2816 / 1407 / 107
Регистрация: 07.03.2009
Сообщений: 4,446
|
|
17.08.2009, 16:44 | 3 |
тебе нужно не пояснение к ханойским башням, а пояснения к понятию рекурсии в целом, и в частности рекурсивных функций в Си. Для этого открой учебник в разделе функций, и почитай внимательно о том, что такое рекурсивная функция и как она работает.
p.s: если у тебя в учебники этого нету - значит у тебя плохой учебник. купи другой.
0
|
0 / 0 / 0
Регистрация: 06.08.2009
Сообщений: 3
|
|
17.08.2009, 17:29 [ТС] | 4 |
Monte-Cristo, перечитывал. С рядом Фибоначчи и вычислением факториалов все ясно предельно (там два примера наглядных и очень хорошо изложенных в этой главе по рекурсии). А вот в примере ханойских башен не могу разобраться: ну почему именно (a, c, b), а затем (b, a, c)... почему именно эта последовательность(а не (c,b,a), скажем)? как она была выведена?
В учебнике сказано "должен быть нацел на решение основного (базового) случая" - (перефразировал несколько) - а какой тут базовый случай?
0
|
Почетный модератор
64300 / 47595 / 32743
Регистрация: 18.05.2008
Сообщений: 115,181
|
|
17.08.2009, 17:36 | 5 |
А Вы поиграйте просто в эту игру, найдите оптимальное решение, запишите его в строках на бумаге и тогда поймете.
0
|
640KB мне хватило на всё.
119 / 50 / 3
Регистрация: 07.06.2009
Сообщений: 442
|
|
17.08.2009, 17:51 | 6 |
На каждом этапе, не зависимо от степени решенности задачи, у вас есть два штыря, на один из которых вы и пытаетесь перенести пирамиду.
Если в исходной задаче - 10 элементов на месте "a", то представьте, что их не 10, а 9, и перенести нужно не на "b", а на "c". После решения этой задачи, вы свободно можете переместить 10-ый на "b", а содержимое "c" переносите на "b". Но, чтобы перенести 9 шт. с "c" на "b", нужно сперва перенести 8 шт. с "c" на "a". Только я думаю, не погорячился ли я предложив для начала число 10
0
|
4727 / 2548 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
|
18.08.2009, 16:39 | 7 |
Есть такая книга "С++. Освой на примерах". Автор М.И.Динман. Там на странице 66 рассматривается как раз задача о Ханойских башнях. Тема раскрыта очень хорошо и доходчиво. Данную книгу можно скачать из интернета бесплатно.
1
|
229 / 67 / 11
Регистрация: 02.06.2009
Сообщений: 280
|
||||||
18.08.2009, 19:05 | 8 | |||||
Итак задача состоит в том, чтоб перенести блины со стержня а на стержень с не перекладывая за раз больше чем 1 блин и не ложа больший блин на меньший.
Решение: 1) Рассмотрим случай для одного блина Переложить блин а -> c 2)Рассмотрим случай для n блинов
0
|
depict1
281 / 146 / 4
Регистрация: 11.07.2009
Сообщений: 606
|
|
18.08.2009, 22:12 | 9 |
Простой алгоритм решения задачи:
n - количество дисков Можно смещать стопку дисков на один стержень вправо, до завершения повторяя следующие два шага: 1) Перемещение маленького диска вправо, если n - нечётно (влево - если четно) 2) Выполнение единственого разрешенного перемещения, не затрагивающего маленький диск.
0
|
640KB мне хватило на всё.
119 / 50 / 3
Регистрация: 07.06.2009
Сообщений: 442
|
|
18.08.2009, 23:50 | 10 |
функция Перемещение(ЧислоБлинов,Откуда,Куда,ТретьяБашня)
if (n==1) Переместить_Куда_Надо else { Перемещение(n-1,Откуда, ТретьяБашня, Куда) Переместить_Куда_Надо Перемещение(n-1,ТретьяБашня, Куда, Откуда) } Может так будет понятно? И учтите, фактически "работа" будет выполнятся на выходе из рекурсии, и сама рекурсия будет глубокой и тяжелой. Если на лажанул, затраты что-то типа n^2
0
|
depict1
281 / 146 / 4
Регистрация: 11.07.2009
Сообщений: 606
|
|
19.08.2009, 08:20 | 11 |
0
|
640KB мне хватило на всё.
119 / 50 / 3
Регистрация: 07.06.2009
Сообщений: 442
|
|
19.08.2009, 16:08 | 12 |
0
|
0 / 0 / 0
Регистрация: 29.03.2014
Сообщений: 20
|
||||||
29.11.2014, 16:34 | 13 | |||||
Видимо все давно всё поняли, как всегда кроме меня. Механизм решения, в принципе, ясен, остался 1 маленький вопрос
в "cout" должны выводиться на печать в консоли значения переменных "а" на 1-м месте и "b" на 2-м. каким образом на место 1е и 2е места в консольном окне выводятся значения других переменных, к примеру, на 1м месте может быть значение переменных и "a" и "c" и "b"? Функция " hanoy" просто переставляет местами переменные перед выводом на печать, и каким образом?
0
|
640KB мне хватило на всё.
119 / 50 / 3
Регистрация: 07.06.2009
Сообщений: 442
|
|
29.11.2014, 17:25 | 14 |
А функция ничего не переставляет. Здесь просто показывается в переменных A и B количество блинов.
Общая идея такая - если надо переставить N-верхнюю часть башни на на место A, то сперва надо перенести N-1-часть на B. N>1
0
|
0 / 0 / 0
Регистрация: 29.03.2014
Сообщений: 20
|
|
29.11.2014, 17:32 | 15 |
а разве А И В это не номера начального и конечного столба? Просто каким образом на есте В может вывестись С или А...?
0
|
640KB мне хватило на всё.
119 / 50 / 3
Регистрация: 07.06.2009
Сообщений: 442
|
|||||||||||
29.11.2014, 18:17 | 16 | ||||||||||
dima__, пардон, поспешил сумничать. Тут шибко хитрая логика с номерами столбцов.
Примерно так: если остался один блин, то перестановка тривиальна - с первой (A) на вторую (B) башни
0
|
0 / 0 / 0
Регистрация: 29.03.2014
Сообщений: 20
|
|
29.11.2014, 18:31 | 17 |
в консоли ж выдаёт:
1 -> 2 1 -> 3 2 -> 3 1 -> 2 3 -> 1 3 -> 2 1 -> 2 т.е 1 перестановка с 1-го на 2-й столб, потом со 1-го на 3-й....как-то не ясно
0
|
640KB мне хватило на всё.
119 / 50 / 3
Регистрация: 07.06.2009
Сообщений: 442
|
|
29.11.2014, 19:09 | 18 |
Я так понял, это показывает, с какого на какой столб надо переложить верхний блин.
Вырежете блины из бумаги и попробуйте выполнить команды выдаваемые программой.
0
|
0 / 0 / 0
Регистрация: 29.03.2014
Сообщений: 20
|
|
29.11.2014, 20:25 | 19 |
согласен, но у меня вопрос, каким образом в 1-й строке в консоли выдаётся "1 -> 2", во второй "1 -> 3", если согласно строке 6 кода, "han (n-1, A, C);" вывелось бы (как мне кажется) сначала "1->3", т.к А==1, а С==3. а потом, согласно строке 7 (han (1, A, B ) вывелось бы "1 -> 2", т.к А==1, а В==2. а на самом деле выводится "1 -> 2" а потом "1 -> 3". Вот что мне не ясно
Добавлено через 2 минуты т. е. вопрос скорее о порядке работы "соut-а" в данной программке,
0
|
640KB мне хватило на всё.
119 / 50 / 3
Регистрация: 07.06.2009
Сообщений: 442
|
|
29.11.2014, 21:53 | 20 |
А при чём тут cout? Он вызывается только при n==1, когда решение тривиально - переложить единственный блин на требуемую пирамиду.
А далее решаем пальцем по порядку: n=1 - перекладываем куда надо и всё n=2 - перекладываем сперва n-1 на место отличное от целевого n=3 - аналогично, но фактически получается, что для нечётного числа блинов начинаем с перекладывания верхнего блина на место целевой пирамиды.
0
|
29.11.2014, 21:53 | |
29.11.2014, 21:53 | |
Помогаю со студенческими работами здесь
20
Пояснение функции Пояснение по шаблонам2 Пояснение по синтаксису Пояснение по коду Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |