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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 44, средняя оценка - 4.80
kkk008009kkk
46 / 46 / 1
Регистрация: 24.03.2011
Сообщений: 315
#1

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

05.04.2012, 01:25. Просмотров 7092. Ответов 25
Метки нет (Все метки)

Добрый день. Подскажите, пожалуйста, алгоритм рекурсивной процедуры вычисления n-го числа Фибоначчи.

Только начал изучать процедуры и рекурсии, поэтому задача вызвала затруднения.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.04.2012, 01:25
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Рекурсивная процедура вычисления n-го числа Фибоначчи (C++):

Рекурсивная процедура вычисления факториала - C++
Обязательно все через рекурсии надо сделать!! Помогите студенту сдать зачет

Рекурсивная процедура вычисления биномиальных коэффициентов - C++
Помогите, пожалуйста! Нужно сдать сегодня. А в рекурсии Си не бум-бум Написать рекурсивную процедуру вычисления биномиальных ...

Рекурсивная процедура перевода числа из десятичной системы счисления в двоичную - C++
3) Написать рекурсивную процедуру перевода нату¬рального числа из десятичной системы счисления в двоич¬ную.

Рекурсивная функция: вычисление суммы чисел Фибоначчи, пока они меньше введенного числа - C++
Вроде примитивная задача, но реализовать не смог, да и нигде такого не обсуждалось, так что вот: Требуется реализовать рекурсивную функцию,...

Рекурсивная процедура для вывода на экран цифр натурального числа в обратном порядке! - C++
Написать рекурсивную процедуру для вывода на экран цифр натурального числа в обратном порядке!

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

25
FesS92
48 / 48 / 6
Регистрация: 22.02.2012
Сообщений: 137
05.04.2012, 08:23 #16
Цитата Сообщение от alexey31415 Посмотреть сообщение
C++
1
2
3
4
5
6
7
8
// рекурсивный метод вычисления чисел Фибоначчи 
unsigned long fibonacci( unsigned long number ) 
{ 
if ( ( number == 0 ) || ( number == 1 ) ) // основные случаи 
return number; 
else // рекурсивный шаг 
return fibonacci( number - 1 ) + fibonacci( number - 2 ) ; 
}
и не нужно функций с 3-4 параметрами
Зато идет ветвистая рекурсия))
1
alexey31415
59 / 59 / 3
Регистрация: 16.05.2010
Сообщений: 632
05.04.2012, 09:46 #17
Цитата Сообщение от FesS92 Посмотреть сообщение
Зато идет ветвистая рекурсия
не бывает так,чтоб было всё хорошо,согласен в этом случае нагрузка на процессор больше,но писать меньше надо
1
diagon
Higher
1930 / 1196 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
05.04.2012, 10:01 #18
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
#include <iostream>
 
void fibb( int n, int &res )
{   
    static int arr[1000] = { };
    
    if ( n == 1 || n == 2 )
    {
        res = 1;
        return;
    }   
    
    if ( !arr[n - 1] )
        fibb(n - 1, arr[n - 1]);
    
    if ( !arr[n - 2] )
        fibb(n - 2, arr[n - 2]);
        
    res = arr[n - 1] + arr[n - 2];
}
 
int main()
{
    int x;
    fibb(7, x);
    std::cout << x;
}
1
alexey31415
59 / 59 / 3
Регистрация: 16.05.2010
Сообщений: 632
05.04.2012, 13:45 #19
давайте уже проведём конкурс на самую изобретательную реализацию вычисления чисел Фибоначчи
1
diagon
Higher
1930 / 1196 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
05.04.2012, 14:17 #20
Цитата Сообщение от alexey31415 Посмотреть сообщение
давайте уже проведём конкурс на самую изобретательную реализацию вычисления чисел Фибоначчи
C
1
2
3
4
5
6
#include <stdio.h>
 
main(int n, int x, int r)
{       
    return x ? scanf("%d", &n) : 0, r = n < 2 ? n : main(n - 1, 0, 0) + main(n - 2, 0, 0), x ? printf("%d\n", r) : 0, r;
}
Компилировать только как С, С++ компиляторы на такое ругаться будут.
Вводим номер числа - получаем число.
1
System16v
3 / 3 / 0
Регистрация: 19.02.2014
Сообщений: 115
20.03.2015, 12:17 #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 и выдает ответ,но просто значения предыдущих не выводит?Просто если не так,то тогда вообще не врубаюсь откуда она берет тогда предыдущие значения для вычислений.
0
FesS92
48 / 48 / 6
Регистрация: 22.02.2012
Сообщений: 137
20.03.2015, 13:20 #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), значения которых мы знаем без дополнительных подсчетов. И потом наверх "вытаскиваем" значения снизу и уже используем.

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

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

А - это спуск по рекурсии,
Б - возврат из рекурсии.
1
System16v
3 / 3 / 0
Регистрация: 19.02.2014
Сообщений: 115
20.03.2015, 15:56 #25
FesS92, спасибо,врубился , это я и хотел услышать
1
FesS92
48 / 48 / 6
Регистрация: 22.02.2012
Сообщений: 137
20.03.2015, 16:00 #26
Для спасибо тут есть специальная кнопка)
И Вам не сложно, и мне приятно)

п.с.: если чем могу помочь - обращайтесь
0
20.03.2015, 16:00
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.03.2015, 16:00
Привет! Вот еще темы с ответами:

Рекурсивная функция вычисления разрядности числа в двоичном виде - C++
Есть неработающий код: #include &lt;iostream&gt; using namespace std; unsigned char capacity (unsigned char number) { ...

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

Напишите функцию для вычисления и-го числа Фибоначчи - C++
Напишите функцию для вычисления и-го числа Фибоначчи. Реализуйте функцию итеративно и рекурсивно. Скорость рекурсивной версии не должна...

Написать программу для вычисления n-го числа Фибоначчи - C++
Написать программу для вычисления n-го числа Фибоначчи, используя рекурсию: F(n) = F(n -1) + F(n - 2); F(1) = F(2) = 1.


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

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

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