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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 18, средняя оценка - 4.94
doomer74
1 / 1 / 0
Регистрация: 01.12.2011
Сообщений: 51
01.07.2012, 16:11     Число Фибоначчи без использования повторных вычислений #1
Всем привет.
Надо написать программу вычисления числа Фибоначчи рекурсивно, причем избегая повторных вычислений. То есть запоминать найденные значения, чтобы не вычислять их каждый раз заново.


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

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
#include <conio.h>
#include <iostream>
#include <clocale>
using namespace std;
 
unsigned long Fibonacci (int n, unsigned 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); //Рекурсивный вызов функции 
            }
        return *(Fib + n);
}
 
void main()
{ 
    int n; // Количество элементов в последовательности  Фибоначчи
    cout << "Enter the number N = "; cin >> n; // Вводим количество элементов
    unsigned long *Fib = new unsigned long[n]; //Создаем динамический массив под числа Фибоначчи
    for(int i=0; i<n; i++) // Заполняем его нулями
            Fib[i]=0;
    cout << "Fibonacci number = " << Fibonacci(n, Fib); // Точка рекурентного вызова функции
    delete [] Fib;
    _getch();
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
01.07.2012, 16:11     Число Фибоначчи без использования повторных вычислений
Посмотрите здесь:

Вычислить максимальное по модулю число из последовательности действительных чисел, без использования массива C++
наиболее часто встречающееся число без использования массивов C++
Вычисление числа из последовательности Фибоначчи без использования массива C++
Числа Фибоначчи без использования рекурсии и массивов C++
Написать программу, которая определяет число Фибоначчи под номером N и проверяет, является ли это число возрастающим C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
01.07.2012, 16:25     Число Фибоначчи без использования повторных вычислений #2
doomer74, а зачем там повторные вычисления?
MrGluck
Ворчун
Эксперт С++
 Аватар для MrGluck
4927 / 2670 / 243
Регистрация: 29.11.2010
Сообщений: 7,429
01.07.2012, 16:31     Число Фибоначчи без использования повторных вычислений #3
doomer74, при рекурсии повторных вычислений не будет. Если нужно сохранять значения, например в случае, если нужно посчитать сначала число Ф. 6, а потом 19, то логичнее было бы использовать цикл.
doomer74
1 / 1 / 0
Регистрация: 01.12.2011
Сообщений: 51
01.07.2012, 16:33  [ТС]     Число Фибоначчи без использования повторных вычислений #4
Все. До меня дошло, где неправильно. Я не там освобождал память.
Вот работающий код.

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
#include <conio.h>
#include <iostream>
#include <clocale>
using namespace std;
 
unsigned long Fibonacci (int n, unsigned 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); //Рекурсивный вызов функции 
            }
            return *(Fib + n);
            delete [] Fib;
}
 
void main()
{ 
    setlocale(LC_CTYPE, "Rus");
    int n; // Количество элементов в последовательности  Фибоначчи
    cout << "Введите число  N = "; cin >> n; // Вводим количество элементов
    unsigned long *Fib = new unsigned long[n]; //Создаем динамический массив под числа Фибоначчи
    for(int i=0; i<n; i++) // Заполняем его нулями
            Fib[i]=0;
    cout << "Число Фибоначчи = " << Fibonacci(n, Fib); // Точка рекурентного вызова функции
    _getch();
}


Цитата Сообщение от taras atavin Посмотреть сообщение
doomer74, а зачем там повторные вычисления?
Ну вот именно, что они там не за чем. А если просто с рекурсией делать алгоритм, там одни и те же значения по несколько раз будут вычисляться. Здесь такого не будет.
Сначала создается массив, заполненный нулями. Потом во время вызова функции будет проверка, равно число нулю или нет. Если не равно, значит, его не трогаем, идем дальше.
Экономия памяти.
MrGluck
Ворчун
Эксперт С++
 Аватар для MrGluck
4927 / 2670 / 243
Регистрация: 29.11.2010
Сообщений: 7,429
01.07.2012, 16:39     Число Фибоначчи без использования повторных вычислений #5
doomer74, вы бы лучше об экономии итераций побеспокоились. С повторными вычислениями нужно использовать цикл.
А рекурсия одно и то же значение вычислять не будет.
C++
1
2
3
4
5
unsigned long Fib(unsigned long n) // рекурсивная функция вычисления чисел Фибоначчи
{
    // если число 1 или 2, то возвращаем 1, иначе сумму результатов функции с числами n-1 и n-2 
    return (n == 1 || n == 2 ? 1 : Fib(n-1) + Fib(n-2) );
}
Zuzik
 Аватар для Zuzik
220 / 205 / 34
Регистрация: 11.06.2012
Сообщений: 1,338
01.07.2012, 16:41     Число Фибоначчи без использования повторных вычислений #6
у вас память освобождаться не будет, return выйдет из функции и до освобождения памяти дело просто не дойдет.
ЛетающийЕнот
88 / 67 / 12
Регистрация: 28.06.2012
Сообщений: 161
01.07.2012, 17:07     Число Фибоначчи без использования повторных вычислений #7
Право, зачем массив, если выводить нужно только число?

C++
1
2
3
4
5
6
7
8
9
10
11
int Fibonacci(int n)
{
 int a=0,b=1;
 //if (n==1) return 1;
 for (int i=1; i<n; i++)
 {
  b+=a;
  a=b-a;
 }
 return b;
}
doomer74
1 / 1 / 0
Регистрация: 01.12.2011
Сообщений: 51
02.07.2012, 08:10  [ТС]     Число Фибоначчи без использования повторных вычислений #8
Мне нужно выполнить несколько вариантов вычисления числа Фибоначчи. Поэтому я рассматриваю все возможные !
Обыкновенный рекурсивный я знаю как сделать. Нерекурсивные тоже знаю. Там ничего сложного нет.

Но я еще хочу сделать рекурсивный алгоритм с запоминанием. Я нашел в нескольких книгах алгоритм, реализующийся через статический массив. Можно ли как-либо переделать его через динамический? Как я, например, сделал?
Иначе говоря, мне надо реализовать рекурсивный алгоритм динамическим программированием сверху.
Приэтом я хочу использовать динамический массив. Возможно ли это?
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
02.07.2012, 14:12     Число Фибоначчи без использования повторных вычислений #9
Рекурсия у вас есть, но значения не запоминаются.

Добавлено через 3 минуты
А, нет, проглядел массив.
Цитата Сообщение от doomer74 Посмотреть сообщение
Но я еще хочу сделать рекурсивный алгоритм с запоминанием. Я нашел в нескольких книгах алгоритм, реализующийся через статический массив. Можно ли как-либо переделать его через динамический? Как я, например, сделал?
А в чем проблема?

Вообще, в вашем случае проще создать статический массив(в том смысле, что static).
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.07.2012, 12:18     Число Фибоначчи без использования повторных вычислений
Еще ссылки по теме:

Найти трехзначное число x, зная результаты вычислений с его цифрами C++
Составьте программу без использования строковых переменных, которая разбивает число n на цифры и печатает их в C++
C++ Создать файл g, содержащий элементы файла f (действительные числа) без повторных вхождений

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

Или воспользуйтесь поиском по форуму:
doomer74
1 / 1 / 0
Регистрация: 01.12.2011
Сообщений: 51
03.07.2012, 12:18  [ТС]     Число Фибоначчи без использования повторных вычислений #10
Через 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();
}
Yandex
Объявления
03.07.2012, 12:18     Число Фибоначчи без использования повторных вычислений
Ответ Создать тему
Опции темы

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