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

Число Фибоначчи без использования повторных вычислений - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ Найти сумму элементов того массива, в котором больше положительных чисел http://www.cyberforum.ru/cpp-beginners/thread617409.html
Program ABC; Const n=10; m=20; type t1=array of integer; t2=array of integer; var a:t1; b:t2; i,s,k1,k2: integer;
C++ Неправильно работает код Вот ссылка на код #include <iostream> #include <cmath> using namespace std; int main() { cout<<"Введите число "<<endl; int n,k=3; double x1=1,x2=2,x3=1.6667; cin>>n; http://www.cyberforum.ru/cpp-beginners/thread617406.html
Как экспортировать переменную (константу) из dll C++
Понимаю что очень глупый вопрос, но нету времени.. Как экспортировать константу и потом ее получить, динамически подгрузив библу. Функции экспортирую так #ifdef __cplusplus #define EXPORT extern "C" __declspec (dllexport) #else #define EXPORT __declspec (dllexport) #endif
Программа в виде шаблона функции C++
помогите оформить программу в виде шаблона функции, пожалуйста! #include <iostream> using namespace std; int main() { const int size = 4;
C++ Нужна программа с классами http://www.cyberforum.ru/cpp-beginners/thread617349.html
Здравствуйте. Нужна программа с классами, и пояснением что она делает.. абсолютно любая и рабочая Заранее спасибо!
C++ В массиве М(45) найти максимальный В массиве М(45) найти максимальный среди отрицательных элементов и число нулевых элементов стоящих после него подробнее

Показать сообщение отдельно
doomer74
1 / 1 / 0
Регистрация: 01.12.2011
Сообщений: 51
03.07.2012, 12:18  [ТС]     Число Фибоначчи без использования повторных вычислений
Через static я делал. Там значения выдает практически мгновенно на больших числах.

А сделав через динамический массив, я разницу во времени не заметил. Хотя числа вроде запоминаются в массиве! Не пойму, в чем проблема. Как все-таки можно через динамический массив сделать?
А то и там, и там получается экспоненциальная зависимость.

Добавлено через 26 минут
Я понял, в чем ошибка. Почему не работает программа быстро.
Сделав отладку, я обнаружил, что неверно заполняю динамический массив нулями. Как мне это сделать?

Добавлено через 37 минут
Хм, и снова не там ошибка. Я забыл точку с запятой поставить в условии. Массив нулями заполняется нормально.
Но в самой функции вычисления Фибоначчи почему-то в массив не запоминается ничего.

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
31
32
33
34
35
36
37
#include <conio.h>
#include <iostream>
#include <clocale>
#include <ctime>
using namespace std;
 
unsigned long long Fibonacci (int n, unsigned long long * Fib)
{   
    if (*(Fib + n) == 0) // Проверяем элемент массива на равенство нулю. Если не он не равен нулю, значит, мы еще не работали с элементом массива
            {
                if ((n == 1) || (n == 2)) // Первые два элемента последовательности
                    return (*( Fib + n ) = 1);
                else 
                    return (*(Fib + n) = Fibonacci(n - 1, Fib) + Fibonacci(n - 2, Fib));  //Рекурсивный вызов функции 
            }
    else
    return (*(Fib + n));
}
 
void main()
{ 
    setlocale(LC_CTYPE, "Rus");
    int n; // Количество элементов в последовательности  Фибоначчи
    cout << "Введите число  N = "; cin >> n; // Вводим количество элементов
    
    unsigned long long *Fib = new unsigned long long [n]; //Создаем динамический массив под числа Фибоначчи
    for (int i = 0; i < n; i++) // Заполняем его нулями
        *(Fib + i) = 0;
    
    unsigned int start_time = clock();
    cout << "Число Фибоначчи = " << Fibonacci(n, Fib) << endl; // Точка рекурентного вызова функции
    unsigned int end_time = clock();
    unsigned int search_time = end_time - start_time;
    cout << "Search time = " << search_time ;
    delete [] Fib;
    _getch();
}
p. s. функцию clock() вставил, чтобы измерить время работы алгоритма

Добавлено через 1 час 25 минут
Если кому-то интересно, вот рабочий код. У меня на компьютере вычисляет большие числа Фибоначчи до 93 за 7-8 миллисекунд.
Так что там кто-то говорил, что в рекурсии нет повторных вычислений?

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
31
32
33
34
35
36
37
38
#include <conio.h>
#include <iostream>
#include <clocale>
#include <ctime>
using namespace std;
 
unsigned long long Fibonacci (int n, unsigned long long * Fib)
{   
    if (n==0) return 0; // Нулевой элемент
    // Проверяем элемент массива на равенство нулю. Если не он не равен нулю, значит, мы еще не работали с элементом массива
    if (Fib[n-1] != 0) return (Fib[n-1]);
    else                                        
            {
                if ((n == 1) || (n == 2)) // Если первые два элемента последовательности
                    return (Fib[n-1] = 1); 
                else 
                    return (Fib[n-1] = Fibonacci(n - 1, Fib) + Fibonacci(n - 2, Fib));  // Рекурсивный вызов функции 
            }
}
 
void main()
{ 
    setlocale(LC_CTYPE, "Rus");
    int n; // Количество элементов в последовательности  Фибоначчи
    cout << "Введите число  N = "; cin >> n; // Вводим количество элементов
    
    unsigned long long *Fib = new unsigned long long [n]; //Создаем динамический массив под числа Фибоначчи
    for (int i = 0; i < n; i++) // Заполняем его нулями
        *(Fib + i) = 0;
    
    unsigned int start_time = clock();
    cout << "Число Фибоначчи = " << Fibonacci(n, Fib) << endl; // Точка рекурентного вызова функции
    unsigned int end_time = clock();
    unsigned int search_time = end_time - start_time;
    cout << "Search time = " << search_time ;
    delete [] Fib;
    _getch();
}
 
Текущее время: 10:10. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru