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

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

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

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

09.12.2010, 20:59. Просмотров 4309. Ответов 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
lemegeton
2928 / 1357 / 136
Регистрация: 29.11.2010
Сообщений: 2,725
09.12.2010, 21:10 #2
Чтобы понять рекурсию, нужно понять рекурсию.
GNU расшифровывается как "GNU is Not Unix".
1
KOPC1886
27 / 6 / 0
Регистрация: 28.10.2010
Сообщений: 352
09.12.2010, 22:18  [ТС] #3
Так как её понять, если никто ее не объясняет?!
0
Crudelis
Шаровик затейник
676 / 418 / 13
Регистрация: 06.05.2010
Сообщений: 1,109
10.12.2010, 02:14 #4
рекурсия это когда функция вызывает саму себя внутри своего тела функции, взять к примеру функцию вычисляющую факториал:

C++
1
2
3
4
5
int factorial(n){
if(n==0)
return 1;
return n*factorial(n-1);    //----рекурсия
}
1
Kastaneda
Jesus loves me
Эксперт С++
4717 / 2921 / 242
Регистрация: 12.12.2009
Сообщений: 7,434
Записей в блоге: 2
Завершенные тесты: 1
10.12.2010, 12:34 #5
Цитата Сообщение от Crudelis Посмотреть сообщение
рекурсия это когда функция вызывает саму себя внутри своего тела функции,
Так же можно добавить, что ф-ция считается рекурсивной если она вызыватся из ф-ции, вызов которой происходит в теле ф-ции.
Пример:
C++
1
2
3
4
5
6
7
8
9
10
int f1(){
if(some value)
   return value;
//some code
f2();
}
int f2()
//some code
f1();
}
1
st_dent
64 / 64 / 3
Регистрация: 05.07.2010
Сообщений: 219
10.12.2010, 13:14 #6
Рекурсивная функция-функция ,вызывающая сама себя. Каждое выполнение тела функции имеет свою область стека для параметров и локальных переменных.
Достоинство:создание компактного кода.
Недостатки:затраты времени на вызов функции и передачу ей копий параметров, затраты памяти для организации каждого вложенного вызова.
При этом следует избегать(по возможности) использования локальных переменных в рекурсивной функции.
Например, факториал:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int f(int n)
{
  if(n<=1) return 1;
  else
    {
       int x=f(n-1);
       return n*x;
     }
}
int main()
{
  int n=3;
  int res= f(n);
}
стек при n=3
||стековый кадр для n=3
||адрес возврата 1
||3

стек при n=2
||стековый кадр для n=2
||адрес возврата 2
||2
||стековый кадр для n=3
||адрес возврата 1
||3

стек при n=1
||стековый кадр для n=1
||адрес возврата 3
||1
||стековый кадр для n=2
||адрес возврата 2
||2
||стековый кадр для n=3
||адрес возврата 1
||3

Здесь каждый раз под х приходиться отводить память. В данном случае можно обойтись без локальной переменной. Пример в посте Crudelis
1
easybudda
Модератор
Эксперт CЭксперт С++
9913 / 5836 / 975
Регистрация: 25.07.2009
Сообщений: 11,004
10.12.2010, 13:28 #7
Цитата Сообщение от st_dent Посмотреть сообщение
При этом следует избегать(по возможности) использования локальных переменных в рекурсивной функции.
Например, факториал:
C++
1
int f(int n){ return ( n < 2 ) ? 1 : n * f(n-1); }
1
KOPC1886
27 / 6 / 0
Регистрация: 28.10.2010
Сообщений: 352
10.12.2010, 21:41  [ТС] #8
Спасибо! Можно вот на примере кода ханойской башни

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void Towers (int number, int from, int to, int free)
{
  if (number != 0)
  {
    Towers (number-1, from, free, to);
    cout << "Передвигаем " << number << "-й диск с "
         << from << "-его стержня на " << to << "-ий \n";
    Towers (number-1, free, to, from);
  }
}
 
    
int _tmain(int argc, _TCHAR* argv[])
{  setlocale(LC_ALL,"rus");
    int n,s1,s2,s3;
    cin >>n;
    cin >>s1;
    cin >>s2;
    cin >>s3;
    
    Towers ( n,  s1,  s2,  s3);
Вот особенно строки:
Towers (number-1, from, free, to);
cout << "Передвигаем " << number << "-й диск с "<< from << "-его стержня на " << to << "-ий \n";
Towers (number-1, free, to, from);
Как здесь происходит обмен значений между переменными?

 Комментарий модератора 
Используйте теги форматирования кода.
0
asics
Freelance
Эксперт С++
2853 / 1788 / 144
Регистрация: 09.09.2010
Сообщений: 3,841
10.12.2010, 21:53 #9
KOPC1886, Тут чувак обясняет.
1
KOPC1886
27 / 6 / 0
Регистрация: 28.10.2010
Сообщений: 352
11.12.2010, 23:14  [ТС] #10
asics, прослушал спасибо, но там не объясняется!
0
Kastaneda
Jesus loves me
Эксперт С++
4717 / 2921 / 242
Регистрация: 12.12.2009
Сообщений: 7,434
Записей в блоге: 2
Завершенные тесты: 1
12.12.2010, 08:40 #11
KOPC1886, а что может быть еще не понятного? Функция вызывает саму себя. Если на словах не понятно, то практика!!! Написали простеньку рекурсивную ф-цию (или возьмите одну из тех, что здесь предложили) и под отладчиком трассируем, при этом нужно следить за значением переменных. Особый инерес представляет когда ф-ция "скручивается", т.е. возвращается и в каждой ее копии будут разные значения переменных. Должно помочь ))
1
KOPC1886
27 / 6 / 0
Регистрация: 28.10.2010
Сообщений: 352
15.12.2010, 20:46  [ТС] #12
Kastaneda, Я всё равно не понимаю, как происходит обмен значениями между переменными в коде ханойской башни.
0
Kastaneda
Jesus loves me
Эксперт С++
4717 / 2921 / 242
Регистрация: 12.12.2009
Сообщений: 7,434
Записей в блоге: 2
Завершенные тесты: 1
16.12.2010, 09:38 #13
Цитата Сообщение от st_dent Посмотреть сообщение
стек при n=3
||стековый кадр для n=3
||адрес возврата 1
||3
стек при n=2
||стековый кадр для n=2
||адрес возврата 2
||2
||стековый кадр для n=3
||адрес возврата 1
||3
стек при n=1
||стековый кадр для n=1
||адрес возврата 3
||1
||стековый кадр для n=2
||адрес возврата 2
||2
||стековый кадр для n=3
||адрес возврата 1
||3
может не совсем понятно, суть в том, что в стеке создается несоклько копий одной ф-ции и в каждой копии содержатся разные значения переменных. Например:
C++
1
2
3
4
5
6
int f(int n){
   if(n==1)return n;
   return n+f(--n);//рекурсия
}
//вызываем ф-цию так
f(3);
ф-ция посчитает 3+2+1
Вот как это все выгдядет:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int f(n=3){
   if(n==1)return n;
   return n+f(--n);//n не равно 1, поэтому вызываем дальше
}
int f(n=2){
   if(n==1)return n;
   return n+f(--n);//n не равно 1, поэтому вызываем дальше
}
int f(n=1){
   if(n==1)return n;//возвращаем 1
   return n+f(--n);
}
int f(n=2){//значение вернется в копию ф-ции, где n=2
   if(n==1)return n;
   return n+f(--n);//и будет возвращено 2+то, что вернула ф-ция, т.е. 2+1
}
int f(n=3){//в копию, где n=3 возвращено 2+1, т.е. 3
   if(n==1)return n;
   return n+f(--n); будет возвращено 3+3, т.е. 6
}
если после этого не понятно, тогда - практика до посинения )))

Добавлено через 12 часов 39 минут
Есть мысль написать что-то типа FAQ про рекурсию, с очень подробным разъяснением (на низком уровне) и картинками. Если кто-нибудь напишет, что это нужно, вечером напишу.
1
DialeR7
1 / 1 / 0
Регистрация: 13.08.2010
Сообщений: 88
16.12.2010, 10:37 #14
Цитата Сообщение от Kastaneda Посмотреть сообщение
Есть мысль написать что-то типа FAQ про рекурсию, с очень подробным разъяснением (на низком уровне) и картинками. Если кто-нибудь напишет, что это нужно, вечером напишу.
было бы замечательно, если напишете =)
1
silent_1991
Эксперт С++
4997 / 3055 / 149
Регистрация: 11.11.2009
Сообщений: 7,040
Завершенные тесты: 1
16.12.2010, 12:08 #15
KOPC1886, мне кажется, вы не понимаете не рекурсию (хотя, возможно, и её вы тоже не понимаете), а именно рекурсивную реализацию Ханойских башен.
На самом деле в примере ханойских башен ничего никуда не передвигается (да и вообще, как там может что-то передвигаться, мы же в функцию всего лишь числа передаём), а создаётся видимость этого передвижения за счёт вывода на экран тех абстрактных передвижений, которые делает функция.
Так что вы не понимаете Башни не за счёт того, что не понимаете рекурсию, а за счёт того, что вы не понимаете саму логику задачи о Башнях, которая к рекурсии никакого отношения не имеет.
1
16.12.2010, 12:08
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
16.12.2010, 12:08
Привет! Вот еще темы с ответами:

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

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

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

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


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

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

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