Форум программистов, компьютерный форум CyberForum.ru

Пояснение к Ханойским башням - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 17, средняя оценка - 4.76
Михаил Ф.
0 / 0 / 0
Регистрация: 06.08.2009
Сообщений: 3
17.08.2009, 16:08     Пояснение к Ханойским башням #1
Здравствуйте. В программировании новичок, иду пока по книге Дейтелов, там в одной из первых глав наткнулся на задачу о Ханойских башнях. День бился головой об стол, потом посмотрел решение и все равно не смог до конца разобраться в данном коде:

C++
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
#include <stdio.h>
#include <conio.h>
 
char a,b,c;
int num;
 
void hanoy(int num,char a,char b,char c){
 
  if(num>0){
 
    hanoy(num-1,a,c,b);
 
    printf("%c--->%c\n",a,c);
 
    hanoy(num-1,b,a,c);
 
  }
}
void main(){
  clrscr();
  printf("number of rings=");
  scanf("%d",&num);
  a='A';b='B';c='C';
  hanoy(num,a,b,c);
  getch();
}
В частности:
C++
1
2
3
   hanoy(num-1,a,c,b);
 
    hanoy(num-1,b,a,c);
По какому принципу заменяются переменные, как считаются диски, и где return для возвращения промежуточного результата, чтобы посчитать окончательный (хотя тут и void и расчета нет для возврата)? В задаче сказано, что решение элементарное, послушное и строится на рекурсии (перемещение n - 1 диска)... Помогите разобраться: как расшифровать две вышепреведенные строки.
Спасибо.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
17.08.2009, 16:08     Пояснение к Ханойским башням
Посмотрите здесь:

C++ пояснение по length
Граммотное пояснение. C++
Пояснение к коду C++
C++ Пояснение функции
C++ Пояснение к функциям
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Неумейка
 Аватар для Неумейка
12 / 11 / 2
Регистрация: 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/Рекурсия
Monte-Cristo
 Аватар для Monte-Cristo
2805 / 1370 / 30
Регистрация: 07.03.2009
Сообщений: 4,446
17.08.2009, 16:44     Пояснение к Ханойским башням #3
тебе нужно не пояснение к ханойским башням, а пояснения к понятию рекурсии в целом, и в частности рекурсивных функций в Си. Для этого открой учебник в разделе функций, и почитай внимательно о том, что такое рекурсивная функция и как она работает.

p.s: если у тебя в учебники этого нету - значит у тебя плохой учебник. купи другой.
Михаил Ф.
0 / 0 / 0
Регистрация: 06.08.2009
Сообщений: 3
17.08.2009, 17:29  [ТС]     Пояснение к Ханойским башням #4
Monte-Cristo, перечитывал. С рядом Фибоначчи и вычислением факториалов все ясно предельно (там два примера наглядных и очень хорошо изложенных в этой главе по рекурсии). А вот в примере ханойских башен не могу разобраться: ну почему именно (a, c, b), а затем (b, a, c)... почему именно эта последовательность(а не (c,b,a), скажем)? как она была выведена?
В учебнике сказано "должен быть нацел на решение основного (базового) случая" - (перефразировал несколько) - а какой тут базовый случай?
Puporev
Модератор
 Аватар для Puporev
50431 / 38362 / 12300
Регистрация: 18.05.2008
Сообщений: 86,891
17.08.2009, 17:36     Пояснение к Ханойским башням #5
А Вы поиграйте просто в эту игру, найдите оптимальное решение, запишите его в строках на бумаге и тогда поймете.
skvor
640KB мне хватило на всё.
118 / 49 / 2
Регистрация: 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
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
18.08.2009, 16:39     Пояснение к Ханойским башням #7
Есть такая книга "С++. Освой на примерах". Автор М.И.Динман. Там на странице 66 рассматривается как раз задача о Ханойских башнях. Тема раскрыта очень хорошо и доходчиво. Данную книгу можно скачать из интернета бесплатно.
Alexandoros
226 / 64 / 4
Регистрация: 02.06.2009
Сообщений: 280
18.08.2009, 19:05     Пояснение к Ханойским башням #8
Итак задача состоит в том, чтоб перенести блины со стержня а на стержень с не перекладывая за раз больше чем 1 блин и не ложа больший блин на меньший.
Решение:

1) Рассмотрим случай для одного блина
Переложить блин а -> c

2)Рассмотрим случай для n блинов

C++
1
2
3
Переложить n-1  блинов a -> b используя "c"  как воспомагательный   hanoy(num - 1, a, c, b);
Переложить блин а -> c     (см решение №1 :-) )                     printf("%c--->%c\n", a, c);
Переложить  n-1 блинов b -> c используя "a"  как воспомагательный   hanoy(num - 1, b, a, c);
Можеш не понимать как оно работает, просто запомни как это применять, поймеш потом.
zim22
depict1
 Аватар для zim22
276 / 141 / 2
Регистрация: 11.07.2009
Сообщений: 606
18.08.2009, 22:12     Пояснение к Ханойским башням #9
Простой алгоритм решения задачи:
n - количество дисков

Можно смещать стопку дисков на один стержень вправо, до завершения повторяя следующие два шага:
1) Перемещение маленького диска вправо, если n - нечётно (влево - если четно)
2) Выполнение единственого разрешенного перемещения, не затрагивающего маленький диск.
skvor
640KB мне хватило на всё.
118 / 49 / 2
Регистрация: 07.06.2009
Сообщений: 442
18.08.2009, 23:50     Пояснение к Ханойским башням #10
функция Перемещение(ЧислоБлинов,Откуда,Куда,ТретьяБашня)
if (n==1) Переместить_Куда_Надо
else
{ Перемещение(n-1,Откуда, ТретьяБашня, Куда)
Переместить_Куда_Надо
Перемещение(n-1,ТретьяБашня, Куда, Откуда)
}

Может так будет понятно?
И учтите, фактически "работа" будет выполнятся на выходе из рекурсии, и сама рекурсия будет глубокой и тяжелой.
Если на лажанул, затраты что-то типа n^2
zim22
depict1
 Аватар для zim22
276 / 141 / 2
Регистрация: 11.07.2009
Сообщений: 606
19.08.2009, 08:20     Пояснение к Ханойским башням #11
Цитата Сообщение от skvor Посмотреть сообщение
Если на лажанул, затраты что-то типа n^2
(2^N) - 1 перемещений
skvor
640KB мне хватило на всё.
118 / 49 / 2
Регистрация: 07.06.2009
Сообщений: 442
19.08.2009, 16:08     Пояснение к Ханойским башням #12
Цитата Сообщение от zim22 Посмотреть сообщение
(2^N) - 1 перемещений
Тьфу, чёрт - конечно степень
dima__
0 / 0 / 0
Регистрация: 29.03.2014
Сообщений: 20
29.11.2014, 16:34     Пояснение к Ханойским башням #13
Видимо все давно всё поняли, как всегда кроме меня. Механизм решения, в принципе, ясен, остался 1 маленький вопрос

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
using namespace std;
void han (int n, int A,  int B){    
     int C=6-(A+B);
    if (n>1){
     han (n-1, A, C);   
     han (1, A, B );    
     han (n-1, C, B);   
    } 
    else cout<<endl<<A<<" -> "<<B<<endl;    
}
int main ()
{
    int A=1, B=2;
    int n=3;    
    han(n, A, B);
}
"cout<<endl<<A<<" -> "<<B<<endl;"
в "cout" должны выводиться на печать в консоли значения переменных "а" на 1-м месте и "b" на 2-м. каким образом на место 1е и 2е места в консольном окне выводятся значения других переменных, к примеру, на 1м месте может быть значение переменных и "a" и "c" и "b"? Функция " hanoy" просто переставляет местами переменные перед выводом на печать, и каким образом?
skvor
640KB мне хватило на всё.
118 / 49 / 2
Регистрация: 07.06.2009
Сообщений: 442
29.11.2014, 17:25     Пояснение к Ханойским башням #14
Цитата Сообщение от dima__ Посмотреть сообщение
Функция " hanoy" просто переставляет местами переменные перед выводом на печать, и каким образом?
А функция ничего не переставляет. Здесь просто показывается в переменных A и B количество блинов.

Общая идея такая - если надо переставить N-верхнюю часть башни на на место A, то сперва надо перенести N-1-часть на B. N>1
dima__
0 / 0 / 0
Регистрация: 29.03.2014
Сообщений: 20
29.11.2014, 17:32     Пояснение к Ханойским башням #15
Цитата Сообщение от skvor Посмотреть сообщение
Здесь просто показывается в переменных A и B количество блинов.
а разве А И В это не номера начального и конечного столба? Просто каким образом на есте В может вывестись С или А...?
skvor
640KB мне хватило на всё.
118 / 49 / 2
Регистрация: 07.06.2009
Сообщений: 442
29.11.2014, 18:17     Пояснение к Ханойским башням #16
dima__, пардон, поспешил сумничать. Тут шибко хитрая логика с номерами столбцов.

Примерно так: если остался один блин, то перестановка тривиальна - с первой (A) на вторую (B) башни
C++ (Qt)
1
cout<<endl<<A<<" -> "<<B<<endl;
иначе - переставить всё на третью, потом выполнить перестановку для последнего блина и далее вернуть с третьей башни на вторую
C++ (Qt)
1
2
3
han (n-1, A, C);
han (1, A, B );
han (n-1, C, B);
dima__
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-й....как-то не ясно
skvor
640KB мне хватило на всё.
118 / 49 / 2
Регистрация: 07.06.2009
Сообщений: 442
29.11.2014, 19:09     Пояснение к Ханойским башням #18
Я так понял, это показывает, с какого на какой столб надо переложить верхний блин.
Вырежете блины из бумаги и попробуйте выполнить команды выдаваемые программой.
dima__
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-а" в данной программке,
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
29.11.2014, 21:53     Пояснение к Ханойским башням
Еще ссылки по теме:

C++ Пояснение typedef
Пояснение по синтаксису C++
Пояснение структуры ORDER C++

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

Или воспользуйтесь поиском по форуму:
skvor
640KB мне хватило на всё.
118 / 49 / 2
Регистрация: 07.06.2009
Сообщений: 442
29.11.2014, 21:53     Пояснение к Ханойским башням #20
А при чём тут cout? Он вызывается только при n==1, когда решение тривиально - переложить единственный блин на требуемую пирамиду.

А далее решаем пальцем по порядку:
n=1 - перекладываем куда надо и всё
n=2 - перекладываем сперва n-1 на место отличное от целевого
n=3 - аналогично, но фактически получается, что для нечётного числа блинов начинаем с перекладывания верхнего блина на место целевой пирамиды.
Yandex
Объявления
29.11.2014, 21:53     Пояснение к Ханойским башням
Ответ Создать тему
Опции темы

Текущее время: 05:31. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru