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

Рекурсивная процедура вычисления n-го числа Фибоначчи - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 44, средняя оценка - 4.80
kkk008009kkk
46 / 46 / 1
Регистрация: 24.03.2011
Сообщений: 315
05.04.2012, 01:25     Рекурсивная процедура вычисления n-го числа Фибоначчи #1
Добрый день. Подскажите, пожалуйста, алгоритм рекурсивной процедуры вычисления n-го числа Фибоначчи.

Только начал изучать процедуры и рекурсии, поэтому задача вызвала затруднения.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
System16v
 Аватар для System16v
3 / 3 / 0
Регистрация: 19.02.2014
Сообщений: 115
20.03.2015, 12:17     Рекурсивная процедура вычисления n-го числа Фибоначчи #21
А может кто объяснить принцип вычисления рекурсивной функции?Пример тоже взял из книги,но не могу понять принципа ,а именно вот код
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
//---------------------------------------------------------------------------
 
#include <vcl.h>
#include <iostream>
#include <cstdlib>
#include <iomanip>
 
using namespace std;
 
unsigned long fibonacci(unsigned long);
 
int main()
{
        for(int counter=0;counter<=10;counter++)
        cout << "fibonacci(" <<counter << ") = " << fibonacci(counter) << endl;
 
        cout << "fibonacci(20) = " << fibonacci(20) << endl;
        cout << "fibonacci(30) = " << fibonacci(30) << endl;
        cout << "fibonacci(35) = " << fibonacci(35) << endl;
 
        system("pause");
        return 0;
}
unsigned long fibonacci(unsigned long number)
{
        if((number==1)||(number==0))
                return number;
        else
                return fibonacci(number-1)+fibonacci(number-2);
}
Интересует как функция считает?Я понимаю так,что для единицы и нуля она присваивает 0=0,1=1,а потом для 2 присваивает уже подставленные значения из return(если не так поправьте) значение 0 и 1,т.е. 2=0+1=1,3=1+1=2 и т.д. И интересует как функция посчитала просто значение 20,30,35? Ведь у нее нет же предыдущих значений 18,19,28,29,34,35? Или функция чтоб выдать правильный ответ сама считает по порядку дальше от 10ти до 20 и выдает ответ,потом от 20 до 30 и выдает ответ,и от 30 до 35 и выдает ответ,но просто значения предыдущих не выводит?Просто если не так,то тогда вообще не врубаюсь откуда она берет тогда предыдущие значения для вычислений.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
FesS92
48 / 48 / 6
Регистрация: 22.02.2012
Сообщений: 137
20.03.2015, 13:20     Рекурсивная процедура вычисления n-го числа Фибоначчи #22
И интересует как функция посчитала просто значение 20,30,35?

Функция является рекурсивной. Т.е. она вызывает саму себя.

C++
1
return fibonacci(number-1)+fibonacci(number-2);
Стоят точки для выхода из рекурсии - какой-то ответ без вызова самой себя.

C++
1
2
if((number==1)||(number==0))
                return number;
для fibonacci(0) и fibonacci(1) - функции отрабатывают без вызова рекурсии.

Для fibonacci(2) вызывается подсчет: fibonacci(0) и fibonacci(1).

fibonacci(3)= fibonacci(2) (=fibonacci(0)+fibonacci(1)) + fibonacci(1).

И так далее.

Это можно представить, как спуск по лестнице от какого-то большого числа вниз до fibonacci(0) и fibonacci(1), значения которых мы знаем без дополнительных подсчетов. И потом наверх "вытаскиваем" значения снизу и уже используем.

Если непонятно объяснил - пишите в личку или тут
System16v
 Аватар для System16v
3 / 3 / 0
Регистрация: 19.02.2014
Сообщений: 115
20.03.2015, 13:28     Рекурсивная процедура вычисления n-го числа Фибоначчи #23
FesS92, ну немного все равно не понял , просто объясни каким образом функция высчитала для 20? Она постепенно вычисляла значение(т.к. не известны ближайшие 18 и 19)? Т.е. функции нужен ответ для 20ти,но так как его не вычислить сразу(т.к. не известны ближайшие 18 и 19) функции приходится высчитывать с известных значений т.е. с 10 до 19 чтоб найти 20?
FesS92
48 / 48 / 6
Регистрация: 22.02.2012
Сообщений: 137
20.03.2015, 15:25     Рекурсивная процедура вычисления n-го числа Фибоначчи #24
А)
Чтобы досчитать до 20, она сначала досчитала до 19.
Чтобы досчитать до 19, она досчитала до 18.
...
...
Чтобы досчитать до 2, она берет значения.

Б)
А теперь, так как посчитала для 2 - она считает для 3х (предыдущие значения известны)
Считает до 4х, т.к. для 3х известно...
...
и так до 20..

А - это спуск по рекурсии,
Б - возврат из рекурсии.
System16v
 Аватар для System16v
3 / 3 / 0
Регистрация: 19.02.2014
Сообщений: 115
20.03.2015, 15:56     Рекурсивная процедура вычисления n-го числа Фибоначчи #25
FesS92, спасибо,врубился , это я и хотел услышать
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.03.2015, 16:00     Рекурсивная процедура вычисления n-го числа Фибоначчи
Еще ссылки по теме:

Проведите программу вычисления числа Фибоначчи с заданным номером C++
C++ Рекурсивная процедура перевода числа из десятичной системы счисления в двоичную
C++ С помощью цикла написать программу вычисления числа Фибоначчи

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

Или воспользуйтесь поиском по форуму:
FesS92
48 / 48 / 6
Регистрация: 22.02.2012
Сообщений: 137
20.03.2015, 16:00     Рекурсивная процедура вычисления n-го числа Фибоначчи #26
Для спасибо тут есть специальная кнопка)
И Вам не сложно, и мне приятно)

п.с.: если чем могу помочь - обращайтесь
Yandex
Объявления
20.03.2015, 16:00     Рекурсивная процедура вычисления n-го числа Фибоначчи
Ответ Создать тему
Опции темы

Текущее время: 14:27. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru