Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 12.03.2015, 22:19   #1
Алексей_2012
t45t
Участник клуба
 
Аватар для Алексей_2012
 
Регистрация: 20.03.2012
Сообщений: 1,849
По умолчанию Рекурсия, Си

Ребят, здравствуйте, много проболел, теперь не могу разобраться как работает рекурсия, вот код из лекции, если ввожу 8, то выводится, 21, проанализировав код получилось 13, почему именно 21?

Код:
#include <QCoreApplication>


int rabbits (int mounth)
{
    if (mounth<3) return 1; else
        return
                rabbits(mounth-1)+
                rabbits(mounth-2);
    
}

int main(int argc, char *argv[])
{  QCoreApplication a(argc, argv);
    
    int i;
    scanf("%d",&i);
    printf("\n%d",rabbits(i));
    
    return a.exec();
}
from dark to light)
Алексей_2012 вне форума Ответить с цитированием
Старый 12.03.2015, 23:19   #2
Poma][a
Новичок
Джуниор
 
Регистрация: 11.10.2011
Сообщений: 3,882
По умолчанию

Ибо это число Фибоначчи..
Код:
1  2  3  4  5  6  7  8
1  1  2  3  5  8 13 21
Poma][a вне форума Ответить с цитированием
Старый 13.03.2015, 01:37   #3
Алексей_2012
t45t
Участник клуба
 
Аватар для Алексей_2012
 
Регистрация: 20.03.2012
Сообщений: 1,849
По умолчанию

сам принцип работы не понятен, ведь получается 8-1=7
8-2=6;
7+6=13, судя по коду
from dark to light)
Алексей_2012 вне форума Ответить с цитированием
Старый 13.03.2015, 02:33   #4
BDA
МегаМодератор
СуперМодератор
 
Аватар для BDA
 
Регистрация: 09.11.2010
Сообщений: 7,285
По умолчанию

rabbits(8) равно rabbits(7) + rabbits(6), а не 7 + 6.
Пишите язык программирования - это форум программистов, а не экстрасенсов. (<= это подпись )
BDA вне форума Ответить с цитированием
Старый 13.03.2015, 21:44   #5
Алексей_2012
t45t
Участник клуба
 
Аватар для Алексей_2012
 
Регистрация: 20.03.2012
Сообщений: 1,849
По умолчанию

Не подумайте что стеб, но сколько раз эта функция вызовет сама себя? Ничего в рекурсии непонятно
from dark to light)
Алексей_2012 вне форума Ответить с цитированием
Старый 13.03.2015, 22:15   #6
BDA
МегаМодератор
СуперМодератор
 
Аватар для BDA
 
Регистрация: 09.11.2010
Сообщений: 7,285
По умолчанию

rabbits(8) = rabbits(7) + rabbits(6) = 13 + 8 = 21 (2 + 24 + 14 = 40 вызовов)
rabbits(7) = rabbits(6) + rabbits(5) = 8 + 5 = 13 (2 + 14 + 8 = 24 вызова)
rabbits(6) = rabbits(5) + rabbits(4) = 5 + 3 = 8 (2 + 8 + 4 = 14 вызовов)
rabbits(5) = rabbits(4) + rabbits(3) = 3 + 2 = 5 (2 + 4 + 2 = 8 вызовов)
rabbits(4) = rabbits(3) + rabbits(2) = 2 + 1 = 3 (2 + 2 + 0 = 4 вызова)
rabbits(3) = rabbits(2) + rabbits(1) = 1 + 1 = 2 (2 + 0 + 0 = 2 вызова)
rabbits(2) = 1 (0 вызовов)
rabbits(1) = 1 (0 вызовов)

В скобках складываются два указанных вызова функции rabbits и сколько вызовов было сделано в этих вызовах.
В rabbits(8) 40 вызовов, всего в программе 41 вызов функции rabbits (при i = 8).
Пишите язык программирования - это форум программистов, а не экстрасенсов. (<= это подпись )
BDA вне форума Ответить с цитированием
Старый 14.03.2015, 05:59   #7
rrrFer
Санитар
Старожил
 
Аватар для rrrFer
 
Регистрация: 04.10.2008
Сообщений: 2,618
По умолчанию

Это не Фибоначчи, т.к. должно быть рекуррентное соотношение:
Цитата:
F(0)=0,F(1)=1,Fn=F(n−1)+F(n−2),n>2.
Но тут:
Цитата:
F(0)=1,F(1)=1,Fn=F(n−1)+F(n−2),n>2.
ЗЫ. Это на лекциях препод так ужасно код форматирует, или самодеятельность?
rrrFer вне форума Ответить с цитированием
Старый 15.03.2015, 16:49   #8
Алексей_2012
t45t
Участник клуба
 
Аватар для Алексей_2012
 
Регистрация: 20.03.2012
Сообщений: 1,849
По умолчанию

Какие нужно сделать поправки в коде, чтоб отследить что именно происходит на очередном вызове функции? (так, как написал BDA), пробовал так:

Код:
#include <QCoreApplication>


int rabbits (int mounth)
{
    if (mounth<3) return 1; else
        return
                rabbits(mounth-1)+
                rabbits(mounth-2);

}

int main(int argc, char *argv[])
{
    QCoreApplication a(argc, argv);

   for  (int i=1;i<=8;i++)
    printf("\n%d",rabbits(i));
    return a.exec();
}

rrrFer
Чем Вам форматирование моей самодеятельности не понравилось?) Препод дает лекции, мы записываем в тетрадку х)
from dark to light)
Алексей_2012 вне форума Ответить с цитированием
Старый 15.03.2015, 17:01   #9
rrrFer
Санитар
Старожил
 
Аватар для rrrFer
 
Регистрация: 04.10.2008
Сообщений: 2,618
По умолчанию

Цитата:
чтоб отследить что именно происходит на очередном вызове функции?
ты вызвал для этого функцию 8 раз - это, конечно поможет тебе отследить все что хочешь ...

Код:
int rabbits (int mounth) {
  printf("%d", mounth); // так что-ли?
  if (mounth < 3) 
    return 1;
  return rabbits(mounth - 1) + rabbits(mounth - 2);
}
Цитата:
Препод дает лекции, мы записываем в тетрадку х)
Либо лекции хреновые, либо записываете так.

Код:
int rabbits (int mounth) {
  if (mounth < 3) {
    printf("%d -> %d", mounth, 1); // так что-ли?
    return 1;
  }
  const int 
    r1 = rabbits(mounth - 1),
    r2 = rabbits(mounth - 2),
    result = r1 + r2;
  printf("%d -> %d + %d = %d", mounth, r1, r2, result);
  return result;
}
Или так? - только зачем все эти свистопляски?

Последний раз редактировалось Stilet; 15.03.2015 в 17:28.
rrrFer вне форума Ответить с цитированием
Старый 15.03.2015, 17:24   #10
Aleksander550
Форумчанин
 
Регистрация: 07.01.2014
Сообщений: 124
По умолчанию

попробуйте так:
Код:
#include <iostream>

using namespace std;
int action = 0;

int rabbits (int mounth) {
 if (mounth<3){
 	cout << "\nAction " << ++action 
	 	 << "\tmounth = " << mounth 
		 << "\tReturn 1"; 
	return 1;
 }

 else{
 	cout << "\nAction " << ++action 
	 	 << "\tmounth = " << mounth
	 	 << "\tReturn rabbits(" << mounth 
	 	 << "-1)+rabbits(" << mounth << "-2)  =  " 
		 << rabbits(mounth-1)+rabbits(mounth-2);
    return rabbits(mounth-1)+rabbits(mounth-2);
 }
}

int main() {
 int x;
 char end;
 do{
 	cout << "\nIntput x: ";
 	cin >> x;
 	printf("\n\n%d",rabbits(x));
 	cout << "\n\nRestart programm (y\\n)? ";
 	cin >> end;
 	action = 0;
 }while (end == 'y');
 return 0;
}
и не вводите большие числа > 8
#define TRUE FALSE //счастливой отладки
Aleksander550 вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
рекурсия Ника-Вероника Паскаль, Turbo Pascal, PascalABC.NET 6 23.03.2012 21:43
Рекурсия unbanned Паскаль, Turbo Pascal, PascalABC.NET 7 19.01.2012 11:25
Рекурсия dusya9992 Паскаль, Turbo Pascal, PascalABC.NET 4 29.08.2010 14:14
Рекурсия Solnze2 Паскаль, Turbo Pascal, PascalABC.NET 0 09.06.2010 09:28
Рекурсия Shadows_Behind Помощь студентам 6 26.05.2010 15:07