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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 31, средняя оценка - 4.94
KOPC1886
27 / 6 / 0
Регистрация: 28.10.2010
Сообщений: 352
#1

Объяснить рекурсию (на примере ханойской башни) - C++

09.12.2010, 20:59. Просмотров 4229. Ответов 27
Метки нет (Все метки)

Кто может объяснить рекурсию? Можно на примере ханойской башне.Заранее спасибо.
0
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.12.2010, 20:59
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Объяснить рекурсию (на примере ханойской башни) (C++):

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

Написать программу Ханойские башни, используя рекурсию - C++
Имеется три стрежня A, B, C. На стержень A нанизано n дисков радиуса 1, 2,…, n таким образом, что диск радиуса i является i-м сверху....

Объяснить на примере работу оператора ветвления if else - C++
как записать на с++ в ветвлении: если что то истинно ... что вставить сюда? if (finc (a, b, c)); \\ где можно вставить истинность?

Отладить программу в VS 2012 (объяснить ошибку в примере из книжки) - C++
Помогите понять ошибку в примере из книжки. Код набираю на отладку в VS 2012 #include <iostream> int main() { std::cout<<...

Объяснить как работает рекурсивная функция и стек вызовов на моем примере - C++
Объясните пожалуйста как работает рекурсивная функция и стек вызовов на моем примере. Здесь известный алгоритм "Разделяй и властвуй". Но...

Не могли бы вы объяснить простыми словами что делают функции calloc в данном примере - C++
Не могли бы вы объяснить простыми словами что делают функции calloc в данном примере? struct graph_v//структура вершины графа { ...

27
Kastaneda
Jesus loves me
Эксперт С++
4688 / 2892 / 236
Регистрация: 12.12.2009
Сообщений: 7,353
Записей в блоге: 2
Завершенные тесты: 1
16.12.2010, 15:09 #16
Лучший ответ Сообщение было отмечено автором темы, экспертом или модератором как ответ
Итак, для начала разберем несколько моментов, которые необходимо знать, чтобы понять рекурсию.
Во первых – стек.
Само понятие стека рассматривать не будем, т.к. подразумевается, что это знает каждый, если нет – в гугл. Следует отметить, что в каждой программе есть стек (на этапе компиляции под него выделяется память определенного размера, размер стека влияет на размер программы), который программа использует для своих целей. Цели разные, нас же интересует передача параметров для функции, и передача управления в вызываемую ф-цию (читай «возврат из ф-ции»).
Во вторых – собственно передача параметров и возврат из ф-ции.
Есть различные соглашения для вызовов ф-ций, в языке C используется соглашение cdecl (от «c-declaration»), однако для работы с WinAPI используется stdcall, но нас это сейчас не интересует. Соглашение cdecl звучит примерно так: «Аргументы передаются через стек, справа налево. За очистку стека отвечает вызывающая ф-ция.» Очистка стека нас не интересует, а вот передачу параметров, а так же вызов ф-ции и возврат из ф-ции разберем более подробно на примере такой программы.
C++
1
2
3
4
5
6
7
8
9
10
11
int func (int a, int b, int c);
int main(){
int x=5, y=6, z=7;
int summa;
summa = func(x,y,z);
return 0;
}
int func (int a, int b, int c){
int tmp = a+b+c;
return tmp;
}
И так – в ходе выполнения программа дошла до строки summa = func(x,y,z), естественно первым делом будет вызвана ф-ция, потом уже переменной summa будет присвоено значение, которое возвратит ф-ция. Помним, что по соглашению cdecl данные передаются справа налево, поэтому в стек будут «втолкнуты» (от англ. push) сначала переменная z, потом y, потом x. (еще нужно сказать, чего не пишут в сишной лит-ре (по крайней мере я не встречал) в стек так же кладется адрес строки (а каждая строка в коде имеет свой адрес), следующей после строки, где вызывается ф-ция, это делается для того, что бы по команде return вернутся туда, куда нужно, а не куда попало, но нас сей факт не интересует, поэтому опустим этот вопрос.)
Объяснить рекурсию (на примере ханойской башни)
Когда управление будет передано в функцию, то данные будут извлечены «сверху вниз» если смотреть по рисунку.
Вроде здесь все понятно, более подробно объяснять думаю нет смысла. Теперь можно перейти непосредственно к самой рекурсии.
Объяснение на словах, что такое рекурсия и с чем ее едят писалось на форуме выше, да в любой книге можно это найти, поэтому я не буду повторяться, сразу перейдем к примеру.
C++
1
2
3
4
5
6
7
8
9
int func(int n);
int main(){
int a=3;
int summa=func(a);
}
int func(int n){
   if(n==1)return n;
   return n+func(--n);
}
Этот код был рассмотрен выше, сейчас разберем его более подробно.
Итак программа доходит до строки int summa=func(a), первым делом будет вызвана ф-ция. Аргумент у нас один, поэтому он и будет положен в стек.
Объяснить рекурсию (на примере ханойской башни)
Ф-ция принимает аргумент n, поэтому локальной переменной n будет присвоено значение, которое ф-ция вытащит из стека, т.е. число 3. Нужно уточнить, что «локальная» значит не только область видимости, но и то, что переменная создана в стеке (т.е. временная переменная, когда управление перейдет в вызывающую подпрограмму (т.е. в ф-цию main) эта переменная окажется в области стека «МУСОР») Итак мы находимся в программе, вот как выглядет стек:
Объяснить рекурсию (на примере ханойской башни)
Далее выполняется строка if(n==1)return n, поскольку n сейчас не равно 1, то будет выполнена строка return n+ func (--n) (т.е. return 3+ func (2)) Значение переменной n у нас известно, а вот, что вернет func(2) пока нет, поэтому n будет запомнена, а для вызова ф-ции будет выделено дополнительное место в стеке. Вот стек после второго вызова ф-ции:
Объяснить рекурсию (на примере ханойской башни)
Ф-ция начинает свою работу, if(n==1)return n, n опять не равно 1, поэтому вызываем дальше return n+ func (--n); (т.е. 2+ func(1)) И опять значение n запоминается, выделяется новое место в стеке для ф-ции, вот так:
Объяснить рекурсию (на примере ханойской башни)
Ну вот, n=1, поэтому выполнется строка if(n==1)return n. Куда же вернется значение n? Туда, откуда была вызвана ф-ция, т.е. в предыдущую копию ф-ции, в которой n равно 2.
Объяснить рекурсию (на примере ханойской башни)
В этой копии ф-ции мы остановились на строке return n+ func (--n), значение n у нас было известно ( n=2), вот теперь мы получили значение, которое вернула ф-ция (т.е. 1). Только теперь может выполниться эта строка return 2+1; Это значение опять возвращается в предыдущую копию ф-ции:
Объяснить рекурсию (на примере ханойской башни)
Ну и наконец-то в первой копии ф-ции будет выполнена строка return n+ func (--n) (т.е. return 3+3). Таким образом в функцию main будет возвращено число 6, которое и присвоится переменной summa.

Уфф, вроде все)

P.S. когда сам понимаешь материал, кажется, что рассказал все понятно), если что-то не понятно - спрашивайте.
P.P.S. давно я в paint'е не рисовал)))
19
dihlofos
16.12.2010, 15:17
  #17

Не по теме:

Kastaneda, вам прямо учебники нужно писать

1
KOPC1886
27 / 6 / 0
Регистрация: 28.10.2010
Сообщений: 352
16.12.2010, 20:49  [ТС] #18
Kastaneda, спасибо большое, я понял в принципе как работает рекурсия. Но в ханойской башне там то функция ничего не возвращает.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void opel (int n,int s1,int s2,int s3)
    
{if (n==1)
    {cout <<s1<<"-->"<<s3<<endl;}
else
    {   
        opel ( n-1, s1, s3, s2);
        cout <<s1<<"-->"<<s3<<endl;
        opel( n-1, s2, s1, s3);
    
    }       
}
int _tmain(int argc, _TCHAR* argv[])
{  setlocale(LC_ALL,"Russian");
    
    int n=4,s1=1,s2=2,s3=3;
 
    opel ( n, s1, s2, s3);
Когда я смотрел как вызывается функция в режиме отладки, я заметил что в строке
opel ( n-1, s1, s3, s2); происходит обмен значениями между переменными s2 и s3(s1 остается неизменной). А в строке opel( n-1, s2, s1, s3); происходит обмен значениями между переменными s1 и s2. Почему происходит обмен значениями между переменными?
0
silent_1991
Эксперт С++
4986 / 3043 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
16.12.2010, 21:11 #19
Итак, объясняю, какова логика решения задачи про ханойские башни.
Суть в том, что у нас имеется пирамида из n дисков, которая надета на один из штырей, и ещё два штыря - временный и целевой. Суть решения заключается в том, чтобы разбить нашу задачу на подзадачи, а именно - делим нашу пирамиду на две части - на пирамиду из n - 1 дисков (верхний набор) и на один единственный диск. Так вот, мы (абстрактно) берём нашу пирамиду из n - 1 дисков, переносим её на временный штырь, затем переносим наш единственный диск на целевой штырь, а затем переносим всю пирамиду на целевой штырь поверх уже перенесённого последнего диска.
Поскольку мы не можем перенести всю пирамиду целиком, то мы меньшую пирамиду снова делим на две - пирамиду из уже n - 2 дисков и на отдельный диск и к полученной задаче применяем тот же алгоритм. В итоге мы добираемся до элементарной пирамиды из единственного диска, которую просто переносим на целевой штырь. Тут мы начинаем разворачивать рекурсию - вспоминать, что помимо перенесённой части изначальной пирамиды у нас есть ещё один диск - основание пирамиды. Теперь мы переносим это основание на целевой штырь, и всю нашу пирамиду (которая сейчас находится на временном штыре) переносим поверх её основания - диска, теперь находящегося на целевом штыре. Для этого снова применяем тот же алгоритм разбивания пирамиды на части. Перенеся часть пирамиды на основание, вспоминаем, что у полученной пирамиды так же отдельно есть основание, и переносим её на это основание. Так происходит до тех пор, пока вся изначальная пирамида из n дисков не окажется на целевом штыре.
Вся фишка нашей рекурсивной функции не в том, что она физически что-то куда-то переносит, а в том, что она просто-напросто меняет функции штырей, ведь для каждой нашей подзадачи как целевой, как временный, так и исходный штыри могут меняться местами, т.е. перенесли мы пирамиду из, скажем, 4 дисков на временный (для неё) штырь, перенесли последний, пятый диск на целевой штырь, а для перенесённой части пирамиды из 4 дисков изначально временный штырь становится исходным, а в качестве временного будет служить изначально исходный. При этом глобальные функции штырей сохраняются (ведь для нас-то важны не функции штырей в пределах какой-либо из подзадач, а их функции для нашей изначальной задачи - для пирамиды из n дисков, вот эти глобальные назначения штырей функция и выводит на экран). Так вот функция всё то, что я описал, и делает. Сначала проверяется, больше ли n нуля (есть ли ещё диски для переноса), затем вызывает сама себя для n - 1 штыря, и меняет функции штырей (в качестве временного теперь выступает целевой, а в качестве целевого - временный). Затем, внутри этой вызванной функции снова проверяется количество дисков и вызывается ещё одна копия функции уже для ещё меньшей пирамиды из (n - 1) - 1, и снова меняется функция штырей. Так происходит, пока функция не вызовется для пирамиды из одного диска. Тогда будет напечатан мнимый перенос диска с одного штыря на другой и вызвана функция уже для переноса части пирамиды поверх этого перенесённого последнего штыря. Затем снова будет напечатан перенос, и снова какая-то часть пирамиды будет перенесена поверх перенесённого диска. Таким образом наши разрозненные пирамидки будут собираться в одну - изначальную, состоящую из n дисков.
Вообще, главное здесь - понять, что функция и понятия не имеет о том, что нам нельзя класть больший диск поверх меньшего, это заложено в алгоритме, а функция лишь следует ему. Она на каждом шаге всего лишь печатает номера штырей - исходного и целевого, но если мы вспомним, что для каждого экземпляра функции назначения штырей меняются (целевой может стать временным, временный - исходным и т.д.), то становится очевидно, как происходит это мнимый обмен дисков.
2
KOPC1886
27 / 6 / 0
Регистрация: 28.10.2010
Сообщений: 352
17.12.2010, 20:28  [ТС] #20
silent_1991, эм.... а можно не много по подробней о считывании значений в памяти, как все же это происходит?
1
lemegeton
2925 / 1354 / 135
Регистрация: 29.11.2010
Сообщений: 2,725
17.12.2010, 23:47 #21
Цитата Сообщение от Kastaneda Посмотреть сообщение
еще нужно сказать, чего не пишут в сишной лит-ре (по крайней мере я не встречал) в стек так же кладется адрес строки
Это в основном пишут в учебниках по ассемблеру. Там, где учат вызывать подпрограммы. Там же написано, что в стеке еще могут лежать состояния флагов процессора, что, правда, уже совсем бессмысленная в данном контексте информация.
Цитата Сообщение от Kastaneda Посмотреть сообщение
Помним, что по соглашению cdecl данные передаются справа налево, поэтому в стек будут «втолкнуты» (от англ. push) сначала переменная z, потом y, потом x.
Продемонстрируем:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
 
using namespace std;
 
// переменные в стеке оказываются в обратном порядке
void f(int a, int b, int c)
{
        int *p = &c;
        cout << *(p+1) << endl;
        cout << *(p+2) << endl;
}
 
int main(int argc, char *argv[])
{
        f(1, 2, 3);
        return 0;
}
1
silent_1991
Эксперт С++
4986 / 3043 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
18.12.2010, 11:02 #22
KOPC1886,
А что по-подробнее-то? Ничего не считывается. Вот вы когда вызываете функцию, например, sqrt, в функции main, вы передаёте ей параметр - число. Оно копируется в собственную переменную функции sqrt, там с этой переменной происходят какие-то манипуляции и функция возвращает результат. Так вот тут то же самое, при вызове функции HanoiTowers ей передаются какие-то аргументы, они копируются в собственные переменные функции, она в свою очередь вызывает саму себя (теоретически), но фактически это уже другая функция с другими локальными параметрами, в которые и копируются значения тех параметров, которые этой новой функции передала вызывающая функция. Т.н. "обмен" происходит только потому, что сама вызывающая функция передаёт вызываемой свои же параметры, но в другом порядке. Т.е., например, у нас есть функция HanoiTowers(int n, int from, int buf, int to), и мы изначально вызвали HanoiTowers(10, 1, 2, 3), а она вызвала рекурсивно HanoiTowers(9, 1, 3, 2), т.е. в первой функции from был равен 1, buf - 2, to - 3, а в новой функции стало from - 1, buf - 3, to - 2, вот вам и весь "обмен". Я говорю "обмен" в кавычках, потому что обмена никакого нет, ведь вызванная функция просто получает в качестве параметров с теми же именами, что и вызывающая, перемешанные значения.

Не по теме:

Тьфу, спасибо случайно жамкнул)))

1
KOPC1886
27 / 6 / 0
Регистрация: 28.10.2010
Сообщений: 352
18.12.2010, 17:25  [ТС] #23
silent_1991, а вот обратно при втором вызове НanoiTowers(int n, int from, int buf, int to) значения опят встают на свои места (то есть 1, 2, 3). Значения опять возвращаются! Я не совсем понимаю как происходит это "обмен". Как переменные записываются в память и как считываются?
0
silent_1991
Эксперт С++
4986 / 3043 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
18.12.2010, 17:42 #24
Да написал же я, обмена никакого нет! У каждой функции будут свои from, buf, to. И при вызове из первой функции (у неё from1 = 1, buf1 = 2, to1 = 3) второй, у второй будут уже свои from2 = 1, buf2 = 3, to2 = 2. И когда мы выйдем из второй функции (которая вывела свои from2, buf2 и to2), её собственные переменные уничтожатся (мы их уже вывели, они нам больше не нужны), а по возвращении в первую функцию она оперирует снова со своими from1, buf1 и to1.
1
KOPC1886
27 / 6 / 0
Регистрация: 28.10.2010
Сообщений: 352
18.12.2010, 22:41  [ТС] #25
silent_1991, а почему, кстати, первый вызов функции происходит так НanoiTowers(int n, int from, int buf, int to)-НanoiTowers(int n, int from, int buf, int to)-НanoiTowers(int n, int from, int buf, int to)... до тех пор пока n не стане равным 1? А все остальные вызовы идут последовательно?

Добавлено через 2 часа 24 минуты
А как мне тогда преподаватель объяснять, почему и как здесь происходит якобы "обмен" значений?
Как объяснить работу этого кода?
0
silent_1991
Эксперт С++
4986 / 3043 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
19.12.2010, 03:30 #26
Что значит "последовательно"? Здесь такого не будет. Тут будет достаточно обширное дерево вызовов, попробуйте на бумажке нарисовать хотя бы для n = 5
1
KOPC1886
27 / 6 / 0
Регистрация: 28.10.2010
Сообщений: 352
19.12.2010, 15:14  [ТС] #27
Я написал вызов функции для n=4 посмотрите так?
0
Миниатюры
Объяснить рекурсию (на примере ханойской башни)  
silent_1991
Эксперт С++
4986 / 3043 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
20.12.2010, 02:29 #28
KOPC1886, да. Так что вы имели ввиду под "последовательно"?
0
20.12.2010, 02:29
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.12.2010, 02:29
Привет! Вот еще темы с ответами:

Написать рекурсивную и нерекурсивную версию задачи о ханойской башне - C++
Написать рекурсивную и нерекурсивную версию программы для нахождения последовательности перемещений колец в задаче о ханойских башнях. При...

Объяснить что такое "раздельная компиляция", что такое "интерфейс класса" и "реализация класса" на примере - C++
Есть класс, содержащий объекты и конструктор. Конструктор объявляется в одном из cpp файлов(их несколько). Можно ли, как-то, использовать...

итерация Ханойской башни - Turbo Pascal
помогите написать итерацию к задаче о Ханойской башне ! еще с рекурсией разобралась, а вот итерацию на паскале не понимаю

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


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

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

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