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

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

Войти
Регистрация
Восстановить пароль
 
 
kalonord
28 / 28 / 4
Регистрация: 27.01.2014
Сообщений: 785
#1

Ханойская башня и "любимая" рекурсия - C++

04.11.2015, 14:34. Просмотров 1730. Ответов 28
Метки нет (Все метки)

Здравствуйте.

Нашёл здесь на форуме код, для решения данной задачи, но самому мало понятно, что и как, может кто подробно разъяснить?
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
27
28
29
30
31
32
33
34
35
void Hanoi(int r, int b, int e)
{
    int c; // как я понял, колышек для временного размещения колец.
 
    // Находим колышек, на котором будут временно расположены кольца.
    if ((b == 1 && e == 2) || (b == 2 && e == 1)) c = 3;
    else
        if ((b == 1 && e == 3) || (b == 3 && e == 1)) c = 2;
        else
            if ((b == 2 && e == 3) || (b == 3 && e == 2)) c = 1;
 
    // пока r > 1 идёт рекурсия.
    if (r > 1)
    {
        // а вот этот блок я вообще не могу понять...
        Hanoi(r - 1, b, c);
        std::cout << b << " -> " << e << std::endl;
        Hanoi(r - 1, c, e);
    }
    // основной случай, рекурсии кердык.
    else
        std::cout << b << " -> " << e << std::endl;
}
 
int main()
{
    int _rings;
 
    std::cout << "Type number of rings: ";
    std::cin >> _rings;
 
    Hanoi(_rings, 1, 3);
 
    system("pause");
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
04.11.2015, 14:34
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Ханойская башня и "любимая" рекурсия (C++):

Рекурсия (нужны комментарии) "Ханойская башня" - C++
Помогите пожалуйста, обьясните написание программы, какие переменные и зачем используются, буду очень благодарна)) #include &lt;iostream&gt;...

Нужна рабочая программа "Ханойская башня" в консоли - C++
Нужна рабочая программа &quot;Ханойская башня&quot; в консоле: Вводишь количество колец, и выводит все ходы перемещения колец. Если таковой...

Ханойская башня - C++
23. Написать программу, которая печатает последовательность действий (в виде «перенести диск с q на r», где q и r – это А,В или С),...

Ханойская башня - C++
Ханойская башня является одной из популярных головоломок XIX века. Даны три стержня, на один из которых нанизаны восемь колец, причем...

Ханойская башня - C++
Здравтвуйте! Нужно решить задачу где на вход дано Н стержней и К дисков и еще известны начальная и конечная конфигурации(где какие диски...

Ханойская башня - C++
Использование переборных методов (разработка программ решения задачи «Ханойская башня»). на С++

28
zer0mail
2374 / 2004 / 199
Регистрация: 03.07.2012
Сообщений: 7,198
Записей в блоге: 1
04.11.2015, 17:52 #16
Разберись без программирования, как перенести 2,3 (может, 4) кольца. Улови, как зная алгоритм для 2, получить для 3х.
1
kalonord
28 / 28 / 4
Регистрация: 27.01.2014
Сообщений: 785
04.11.2015, 17:55  [ТС] #17
Цитата Сообщение от zer0mail Посмотреть сообщение
Разберись без программирования, как перенести 2,3 (может, 4) кольца. Улови, как зная алгоритм для 2, получить для 3х.
Окей, чуть позже постараюсь.
0
_Ivana
3186 / 1802 / 153
Регистрация: 01.03.2013
Сообщений: 5,030
Записей в блоге: 3
04.11.2015, 17:59 #18
zer0mail, ну вот в таких терминах у меня уже нет никакого повода оппонировать И сравнение рекурсия/итерация как Си с ассемблером в точку. Комбинирование и абстракции.

kalonord, начните детально с факториала, потом с Фибоначчей, как все.
0
kalonord
28 / 28 / 4
Регистрация: 27.01.2014
Сообщений: 785
04.11.2015, 18:01  [ТС] #19
Цитата Сообщение от _Ivana Посмотреть сообщение
начните детально с факториала, потом с Фибоначчей, как все.
Я проделывал всё это, к своему удивлению, даже понял. А вот с этим выводом и этой башней тупняк.
0
_Ivana
3186 / 1802 / 153
Регистрация: 01.03.2013
Сообщений: 5,030
Записей в блоге: 3
04.11.2015, 18:15 #20
kalonord, значит не понял. Сделай 3 рекурсивных факториала - классический, хвостовой с аккумулятором и с передачей аргумента по ссылку, может что-то прояснится.

Добавлено через 1 минуту
ЗЫ и в каждую влепи вывод промежуточных значений до и после рекурсивного вызова - это точно прояснит ситуацию больше, если поймешь.

Добавлено через 7 минут
Давай, пока горячо - лепи сюда рекурсивный факториал, раз ты его разобрал. И подкрути вывод аргумента.
1
kalonord
28 / 28 / 4
Регистрация: 27.01.2014
Сообщений: 785
04.11.2015, 18:32  [ТС] #21
Цитата Сообщение от _Ivana Посмотреть сообщение
Давай, пока горячо - лепи сюда рекурсивный факториал, раз ты его разобрал. И подкрути вывод аргумента.
Ну разобрать то разобрал, правда давненько это было
Чуть позже отпишу.

Добавлено через 10 минут
_Ivana, оно?
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int fact(int n)
{
    if (n <= 1)
        return 1;
    else
        cout << n << endl;
        return n * fact(n - 1);
        
}
 
int main()
{
    int number = 5;
 
    cout << fact(number) << endl;
 
    system("pause");
}
0
_Ivana
3186 / 1802 / 153
Регистрация: 01.03.2013
Сообщений: 5,030
Записей в блоге: 3
04.11.2015, 18:33 #22
Оно. Видишь что выводит? А теперь сделай в ветке иначе сначала расчет результата в переменную, потом вывод аргумента, а потом возврат результата.
0
kalonord
28 / 28 / 4
Регистрация: 27.01.2014
Сообщений: 785
04.11.2015, 18:36  [ТС] #23
Я просто помню, как это делается, даже в тетради схемку делал, но вот так, с ходу в уме представить в уме, что там происходит не получается.

Добавлено через 1 минуту
Забыл скобки поставить, а вывод вроде нормальный..
0
_Ivana
3186 / 1802 / 153
Регистрация: 01.03.2013
Сообщений: 5,030
Записей в блоге: 3
04.11.2015, 18:38 #24
А теперь сделай свой факториал void и ничего не возвращай, а вывод аргумента оставь. И с Фибоначчами так тоже попробуй - будет еще интереснее. И до ханойских башен останется полшага.
0
kalonord
28 / 28 / 4
Регистрация: 27.01.2014
Сообщений: 785
04.11.2015, 18:51  [ТС] #25
Цитата Сообщение от _Ivana Посмотреть сообщение
А теперь сделай в ветке иначе сначала расчет результата в переменную, потом вывод аргумента, а потом возврат результата.
C++
1
2
3
4
5
6
7
8
9
10
11
int fact(int n)
{
    if (n <= 1)
        return 1;
    else
    {
        x = n * fact(n - 1);
        cout << "Arg: " << n << endl;
        return n * fact(n - 1);
    }
}
Где-то накосячил или не так Вас понял. Вывод кривой.
0
_Ivana
3186 / 1802 / 153
Регистрация: 01.03.2013
Сообщений: 5,030
Записей в блоге: 3
04.11.2015, 18:53 #26
Ну почему же кривой - ровно как и заказывал. И это кстати очень похоже на твои башни - вызов / вывод / вызов. Хотя я имел в виду конечно один вызов до вывода.
0
kalonord
28 / 28 / 4
Регистрация: 27.01.2014
Сообщений: 785
04.11.2015, 18:59  [ТС] #27
Вообще бред какой-то написал...

Добавлено через 20 секунд
Сейчас подробнее разберу вывод..

Добавлено через 4 минуты
Цитата Сообщение от _Ivana Посмотреть сообщение
Хотя я имел в виду конечно один вызов до вывода.
А не подскажете как реализуется только лишь один вызов?
0
_Ivana
3186 / 1802 / 153
Регистрация: 01.03.2013
Сообщений: 5,030
Записей в блоге: 3
04.11.2015, 19:02 #28
Ну ты х зачем считал? Причем как глобальную переменную, которая уже объявлена и типизирована выше, но это детали. Локальной ее сделай и возвращай после цаута.
0
kalonord
28 / 28 / 4
Регистрация: 27.01.2014
Сообщений: 785
04.11.2015, 19:11  [ТС] #29
Цитата Сообщение от _Ivana Посмотреть сообщение
Локальной ее сделай и возвращай после цаута.
C++
1
2
3
4
5
6
7
8
 else
    {
        cout << "Arg: " << n << endl;
 
        int x = n * fact(n - 1);
 
        return n * fact(n - 1);
    }
Правильно? Если нет, извините, я просто таким родился
0
04.11.2015, 19:11
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
04.11.2015, 19:11
Привет! Вот еще темы с ответами:

Ханойская башня - C++
Легенда гласит, что, в Великом храме города Бенарас, под собором, отмечающим середину мира, находится бронзовый диск, на котором укреплены...

Ханойская башня- тесты - C++
Переместить m дисков с одного из трех стержней на другой, соблюдая: 1) диски можно перемещать с одного стержня на другой только по...

Ханойская башня еще раз - C++
Ну ни как не могу понять.Объясните как тут рекурсия работает. #include &lt;iostream&gt; using namespace std; void...

В зависимости от времени года "весна", "лето", "осень", "зима" определить погоду "тепло", "жарко", "холодно", "очень холодно" - C++
В зависимости от времени года &quot;весна&quot;, &quot;лето&quot;, &quot;осень&quot;, &quot;зима&quot; определить погоду &quot;тепло&quot;, &quot;жарко&quot;, &quot;холодно&quot;, &quot;очень холодно&quot;. Я так...


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

Или воспользуйтесь поиском по форуму:
29
Ответ Создать тему
Опции темы

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