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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 18, средняя оценка - 4.94
doomer74
1 / 1 / 0
Регистрация: 01.12.2011
Сообщений: 51
#1

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

01.07.2012, 16:11. Просмотров 2526. Ответов 9
Метки нет (Все метки)

Всем привет.
Надо написать программу вычисления числа Фибоначчи рекурсивно, причем избегая повторных вычислений. То есть запоминать найденные значения, чтобы не вычислять их каждый раз заново.


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

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++
Преобразовать символьное представление целого числа в целое число без использования стандартных функций C++
Написать программу, которая возводит число в соответствующую степень(без использования стандартных функций) C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
taras atavin
Ушёл с форума.
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
01.07.2012, 16:25     Число Фибоначчи без использования повторных вычислений #2
doomer74, а зачем там повторные вычисления?
MrGluck
Модератор
Эксперт CЭксперт С++
6992 / 4163 / 594
Регистрация: 29.11.2010
Сообщений: 11,045
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
Модератор
Эксперт CЭксперт С++
6992 / 4163 / 594
Регистрация: 29.11.2010
Сообщений: 11,045
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
231 / 216 / 36
Регистрация: 11.06.2012
Сообщений: 1,425
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
1927 / 1193 / 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     Число Фибоначчи без использования повторных вычислений
Еще ссылки по теме:
C++ Создать файл g, содержащий элементы файла f (действительные числа) без повторных вхождений
C++ Вывести из файла слова без повторных букв, кроме "Z"
Написать программу, которая определяет число Фибоначчи под номером N и проверяет, является ли это число возрастающим C++
Вывести одно целое число - результат вычислений.С++ C++
Найти трехзначное число x, зная результаты вычислений с его цифрами C++

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

Или воспользуйтесь поиском по форуму:
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     Число Фибоначчи без использования повторных вычислений
Ответ Создать тему
Опции темы

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