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

Напишите функцию для вычисления и-го числа Фибоначчи - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 14, средняя оценка - 4.71
hokoko
0 / 0 / 0
Регистрация: 02.02.2013
Сообщений: 13
02.02.2013, 20:43     Напишите функцию для вычисления и-го числа Фибоначчи #1
Напишите функцию для вычисления и-го числа Фибоначчи. Реализуйте функцию итеративно и
рекурсивно. Скорость рекурсивной версии не должна быть заметно хуже быстродействие итеративной версии.

long fib(int i) { ... }

Определение:
fib(0) = 1
fib(1) = 1
fib(n) = fib(n1)
+ fib(n2)

Помогите написать пожалуйста))
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.02.2013, 20:43     Напишите функцию для вычисления и-го числа Фибоначчи
Посмотрите здесь:

C++ Напишите программу, которая использует функцию для вычисления среднего геометрического трех чисел типа int, что вводит пользователь.
C++ Реализовать рекурсивную функцию вычисления n-ого числа из последовательности Фибоначчи по формуле: Fib(0)=1, Fib(1)=1, Fib(n)= Fib(n-1)+ Fib(n-2).
Напишите рекурсивную функцию для вычисления функции Эйлера C++
C++ Напишите программу вычисления суммы: 1! + 2! + 3! + … + n!, используя функцию вычисления факториала числа k.
C++ Рекурсивная процедура вычисления n-го числа Фибоначчи
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
АлександрБелоус
0 / 0 / 0
Регистрация: 02.02.2013
Сообщений: 15
02.02.2013, 20:49     Напишите функцию для вычисления и-го числа Фибоначчи #2
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
#include <iostream>
unsigned long fibonacci (unsigned long);
 
using namespace std;
 
 
int main()
{
    unsigned long result, number;
    setlocale(LC_ALL, "RUS");
        cout << "Введите целое число" << endl;
        cin >> number;
    result = fibonacci(number);
        cout << "Число Фибоначчи(" << number << ") = " << result << endl;
    return 0;
}
 
unsigned long fibonacci ( unsigned long n)
{
    if( n==0 || n==1)
        return n;
    
        return fibonacci( n - 1) + fibonacci ( n - 2 );
}
hokoko
0 / 0 / 0
Регистрация: 02.02.2013
Сообщений: 13
02.02.2013, 21:01  [ТС]     Напишите функцию для вычисления и-го числа Фибоначчи #3
Спасибо а как сделать чтобы рекурсивно?
GggDrej
 Аватар для GggDrej
71 / 71 / 8
Регистрация: 21.01.2013
Сообщений: 147
02.02.2013, 21:13     Напишите функцию для вычисления и-го числа Фибоначчи #4
Цитата Сообщение от hokoko Посмотреть сообщение
Спасибо а как сделать чтобы рекурсивно?
C++
1
2
3
4
5
6
7
unsigned long fibonacci ( unsigned long n)
{
if( n==0 || n==1)
return n;
 
return fibonacci( n - 1) + fibonacci ( n - 2 );
}
это и есть рекурсивная функция
hokoko
0 / 0 / 0
Регистрация: 02.02.2013
Сообщений: 13
02.02.2013, 21:17  [ТС]     Напишите функцию для вычисления и-го числа Фибоначчи #5
Извините)) Большое спасибо! А как тогда сделать в итеративной версии?
GggDrej
 Аватар для GggDrej
71 / 71 / 8
Регистрация: 21.01.2013
Сообщений: 147
02.02.2013, 22:07     Напишите функцию для вычисления и-го числа Фибоначчи #6
C++
1
2
3
4
5
6
7
8
9
#include <iostream>
int n,a,b=1;
main()
{
      std::cin>>n;      
      for (;n--;b+=a)a=b-a;
      std::cout << a;
      system("PAUSE");
}
m1Rr0r
 Аватар для m1Rr0r
247 / 230 / 15
Регистрация: 05.02.2010
Сообщений: 3,213
Завершенные тесты: 2
02.02.2013, 22:25     Напишите функцию для вычисления и-го числа Фибоначчи #7
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
 
using namespace std;
 
int main()  {
    int n;
    cout << "N = ";
    cin >> n;
    long int *a = new long int[n];
    a[0] = 1;
    a[1] = 1;
    for(int i = 2; i < n; i++)
        a[i] = a[i - 1] + a[i - 2];
    cout << "Fibon[" << n << "] == " << a[n - 1] << endl;
    delete []a;
 
    return 0;
}
hokoko
0 / 0 / 0
Регистрация: 02.02.2013
Сообщений: 13
02.02.2013, 23:35  [ТС]     Напишите функцию для вычисления и-го числа Фибоначчи #8
Большое спасибо. Насколько я понял пример который привел m1Rr0r также итеративный. (Извините мою некомпетентность в даном вопросе, я только начал изучать С++) В задаче также указано "Скорость рекурсивной версии не должна быть заметно хуже быстродействие итеративной версии." но когда задать например число 45 в рекурсивной версии то оно считает намного дольше итеративной (последний и предпоследний пример). В чем может быть проблема? Помогите решить проблему чайнику)))
GggDrej
 Аватар для GggDrej
71 / 71 / 8
Регистрация: 21.01.2013
Сообщений: 147
02.02.2013, 23:48     Напишите функцию для вычисления и-го числа Фибоначчи #9
Можно оптимизировать рекурсивный вариант - но этого делать я не буду.
Если ты только начал изучать с++ - зачем лезть в рекурсию, числа Фибоначчи и прочее. Начни с простого
m1Rr0r
 Аватар для m1Rr0r
247 / 230 / 15
Регистрация: 05.02.2010
Сообщений: 3,213
Завершенные тесты: 2
03.02.2013, 00:20     Напишите функцию для вычисления и-го числа Фибоначчи #10
Цитата Сообщение от hokoko Посмотреть сообщение
Насколько я понял пример который привел m1Rr0r также итеративный.
Все верно, итеративный.
Цитата Сообщение от hokoko Посмотреть сообщение
"Скорость рекурсивной версии не должна быть заметно хуже быстродействие итеративной версии."
Для небольших n так и будет. Для больших, тут уже извините, рекурсия кушает много ресурсов, так что времени занимает многовато.
hokoko
0 / 0 / 0
Регистрация: 02.02.2013
Сообщений: 13
03.02.2013, 00:41  [ТС]     Напишите функцию для вычисления и-го числа Фибоначчи #11
Большое спасибо за помощь. насчет оптимизации рекурсивной функции как писал уважаемый GggDrej, где можно о том почитать? может есть хорошие книги по оптимизации кода? СПАСИБО!
GggDrej
 Аватар для GggDrej
71 / 71 / 8
Регистрация: 21.01.2013
Сообщений: 147
03.02.2013, 01:36     Напишите функцию для вычисления и-го числа Фибоначчи #12
Цитата Сообщение от m1Rr0r Посмотреть сообщение
Для больших, тут уже извините, рекурсия кушает много ресурсов, так что времени занимает многовато.
Вышеописанную рекурсивную функцию можно оптимизировать чтобы она работала намного быстрее.
Дело в том что когда пишем
C++
1
return fibonacci( n - 1) + fibonacci ( n - 2 );
функция считает
fibonacci( n - 1) которое в свою очередь = fibonacci( n - 2) + fibonacci( n - 3), а потом еще раз считаем
fibonacci( n - 2) которое мы уже посчитали в fibonacci( n - 1). Этот момент можно устранить.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.02.2013, 02:12     Напишите функцию для вычисления и-го числа Фибоначчи
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
hokoko
0 / 0 / 0
Регистрация: 02.02.2013
Сообщений: 13
03.02.2013, 02:12  [ТС]     Напишите функцию для вычисления и-го числа Фибоначчи #13
Всем спасибо за помощь!
Yandex
Объявления
03.02.2013, 02:12     Напишите функцию для вычисления и-го числа Фибоначчи
Ответ Создать тему
Опции темы

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