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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 14, средняя оценка - 4.71
hokoko
0 / 0 / 0
Регистрация: 02.02.2013
Сообщений: 13
#1

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

02.02.2013, 20:43. Просмотров 2200. Ответов 12
Метки нет (Все метки)

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

long fib(int i) { ... }

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

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

Напишите программу вычисления суммы: 1! + 2! + 3! + … + n!, используя функцию вычисления факториала числа k. - C++
Напишите программу вычисления суммы: 1! + 2! + 3! + … + n!, используя функцию вычисления факториала числа k. И вновь заранее благодарю,...

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

Написать рекурсивную функцию для вычисления k-го члена последовательности Фибоначчи - C++
Написать рекурсивную функцию для вычисления k-го члена последовательности Фибоначчи. Она образуется по закону f1=1, f2=1, fk=fi-1+fi-2...

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

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

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

12
АлександрБелоус
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 );
}
0
hokoko
0 / 0 / 0
Регистрация: 02.02.2013
Сообщений: 13
02.02.2013, 21:01  [ТС] #3
Спасибо а как сделать чтобы рекурсивно?
0
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 );
}
это и есть рекурсивная функция
2
hokoko
0 / 0 / 0
Регистрация: 02.02.2013
Сообщений: 13
02.02.2013, 21:17  [ТС] #5
Извините)) Большое спасибо! А как тогда сделать в итеративной версии?
0
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");
}
2
m1Rr0r
247 / 230 / 15
Регистрация: 05.02.2010
Сообщений: 3,262
Завершенные тесты: 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;
}
1
hokoko
0 / 0 / 0
Регистрация: 02.02.2013
Сообщений: 13
02.02.2013, 23:35  [ТС] #8
Большое спасибо. Насколько я понял пример который привел m1Rr0r также итеративный. (Извините мою некомпетентность в даном вопросе, я только начал изучать С++) В задаче также указано "Скорость рекурсивной версии не должна быть заметно хуже быстродействие итеративной версии." но когда задать например число 45 в рекурсивной версии то оно считает намного дольше итеративной (последний и предпоследний пример). В чем может быть проблема? Помогите решить проблему чайнику)))
0
GggDrej
71 / 71 / 8
Регистрация: 21.01.2013
Сообщений: 147
02.02.2013, 23:48 #9
Можно оптимизировать рекурсивный вариант - но этого делать я не буду.
Если ты только начал изучать с++ - зачем лезть в рекурсию, числа Фибоначчи и прочее. Начни с простого
1
m1Rr0r
247 / 230 / 15
Регистрация: 05.02.2010
Сообщений: 3,262
Завершенные тесты: 2
03.02.2013, 00:20 #10
Цитата Сообщение от hokoko Посмотреть сообщение
Насколько я понял пример который привел m1Rr0r также итеративный.
Все верно, итеративный.
Цитата Сообщение от hokoko Посмотреть сообщение
"Скорость рекурсивной версии не должна быть заметно хуже быстродействие итеративной версии."
Для небольших n так и будет. Для больших, тут уже извините, рекурсия кушает много ресурсов, так что времени занимает многовато.
1
hokoko
0 / 0 / 0
Регистрация: 02.02.2013
Сообщений: 13
03.02.2013, 00:41  [ТС] #11
Большое спасибо за помощь. насчет оптимизации рекурсивной функции как писал уважаемый GggDrej, где можно о том почитать? может есть хорошие книги по оптимизации кода? СПАСИБО!
0
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). Этот момент можно устранить.
2
hokoko
0 / 0 / 0
Регистрация: 02.02.2013
Сообщений: 13
03.02.2013, 02:12  [ТС] #13
Всем спасибо за помощь!
0
03.02.2013, 02:12
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.02.2013, 02:12
Привет! Вот еще темы с ответами:

Напишите программу, которая использует функцию для вычисления среднего геометрического трех чисел типа int, что вводит пользователь. - C++
Напишите программу, которая использует функцию для вычисления среднего геометрического трех чисел типа int, что вводит пользователь. Язык...

Напишите функцию, которая вычисляет факториал для заданного натурального числа - C++
аголовок функции должен быть следующим: int factorial(int n); Напишите программу, которая получает от пользователя два натуральных числа a...

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

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


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

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

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