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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 17, средняя оценка - 4.76
Михаил Ф.
0 / 0 / 0
Регистрация: 06.08.2009
Сообщений: 3
#1

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

17.08.2009, 16:08. Просмотров 2141. Ответов 20
Метки нет (Все метки)

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

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 диска)... Помогите разобраться: как расшифровать две вышепреведенные строки.
Спасибо.
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
17.08.2009, 16:08
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Пояснение к Ханойским башням (C++):

Пояснение typedef - C++
typedef bool (*comparator)(void* fisrt, void* second); что делает *comparator, и что это вобще ?

Пояснение к коду - C++
Добрый день! Вопрос в следующем, есть конструктор объявленный в хелпе: virtual __fastcall TGIS_LayerSHP(); Я не понимаю...

Небольшое пояснение - C++
Здравствуйте,хотел бы поинтересоваться.Вот я,планирую начать изучать с++,хотелось бы иметь примерное представление о том что такое...

Пояснение к функциям - C++
Есть 2 функции. Не могли бы вы прокомментировать их. Или подробно описать что они делают. Заранее спасибо.bool MEqualsSth(void* first,...

Пояснение функции - C++
Пожалуйста объясните что делает функция, если можно с пояснением знака -&gt;, про указатели я знаю. void List::addElem2(int qt, int...

Пояснение по синтаксису - C++
только не надо гнать в гугл, я не могу там найти, т.к. не могу правильно сформировать запрос... Код: //======================== ...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
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);
0
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-й....как-то не ясно
0
skvor
640KB мне хватило на всё.
118 / 49 / 2
Регистрация: 07.06.2009
Сообщений: 442
29.11.2014, 19:09 #18
Я так понял, это показывает, с какого на какой столб надо переложить верхний блин.
Вырежете блины из бумаги и попробуйте выполнить команды выдаваемые программой.
0
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-а" в данной программке,
0
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 - аналогично, но фактически получается, что для нечётного числа блинов начинаем с перекладывания верхнего блина на место целевой пирамиды.
0
dima__
0 / 0 / 0
Регистрация: 29.03.2014
Сообщений: 20
30.11.2014, 19:44 #21
с алгоритмом всё ясно. Не ясно, почему в 1й строчке консоли печатает "1 -> 2", а во второй "1 -> 3", потом "2 -> 3" несмотря на
C++
1
2
3
6 han (n-1, A, C); // где А==1, С==3
7 han (1, A, B );   // где А==1, В==2
8 han (n-1, C, B); // С==3, В==2
и ожидается, вроде бы,
сначала
"1 -> 3",
потом "1 -> 2"
и "3->2" а на самом деле выводится
Цитата Сообщение от dima__ Посмотреть сообщение
1 -> 2
1 -> 3
2 -> 3
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
30.11.2014, 19:44
Привет! Вот еще темы с ответами:

Граммотное пояснение. - C++
Здравствуйте форумчане! Помогите пожалуйста грамотно (!) объяснить действия выполняющиеся в этом куске программы. { int max = 1;...

Пояснение к готовой программе - C++
Ребзи, не могли бы вы помочь, написав мне пояснение к каждой строке программного кода?:) #include &quot;stdafx.h&quot; #include &quot;iostream&quot; ...

Пояснение структуры ORDER - C++
Народ помогите разобраться, код мне помогли накалякать с этого форума вот и некоторые непонятные строки есть, и выдает ваще какую то фигню,...

Нужно пояснение кода - C++
Не могу понять 2 части кода. Разъясните , пожалуйста). 1) cube ( nums , 10 ) . Для чего 10? Откуда она? Для чего nums там? 2) Не...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
30.11.2014, 19:44
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru