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

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

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

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

01.07.2012, 16:11. Просмотров 2617. Ответов 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++
int a, b=0, c=1; cout&lt;&lt;&quot;Введите число Фибоначчи: &quot;&lt;&lt;endl; cin&gt;&gt;a; for(int i=2;i&lt;=(a-3);i++) { a=b+c; b=c; ...

Вычисление числа из последовательности Фибоначчи без использования массива - C++
Последовательность Фибоначчи определяется так: a(0) = 1 ; a(1) = 1; a (k) = a(k-1) + a(k-2). Дано k, вычислить a(k). Не использовать...

Найти наиболее часто встречающееся число без использования массивов - C++
Дана задача: В массиве целых чисел с количеством элементов n найти наиболее часто встречающееся число. Если таких чисел несколько, то...

Вычислить максимальное по модулю число из последовательности действительных чисел, без использования массива - C++
Даны натуральные n, действительные числа a1..an. Получить max(|a1|,..,|an|)

Преобразовать символьное представление целого числа в целое число без использования стандартных функций - C++
Всем доброго вечера! Народ, кто-нибудь знает как пробразовать символьное представление числа &quot;123&quot; в 123 БЕЗ ИСПОЛЬЗОВАНИЯ стандартных...

Написать программу, которая возводит число в соответствующую степень(без использования стандартных функций) - C++
Кто знает как решить задачу на С++. Нужно через цикл while её решить. Написать программу, которая возводит число в соответствующую...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
taras atavin
Ушёл с форума.
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
01.07.2012, 16:25 #2
doomer74, а зачем там повторные вычисления?
MrGluck
Модератор
Эксперт CЭксперт С++
7210 / 4376 / 638
Регистрация: 29.11.2010
Сообщений: 11,887
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Эксперт С++
7210 / 4376 / 638
Регистрация: 29.11.2010
Сообщений: 11,887
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
237 / 222 / 38
Регистрация: 11.06.2012
Сообщений: 1,443
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
1929 / 1195 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
02.07.2012, 14:12 #9
Рекурсия у вас есть, но значения не запоминаются.

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

Вообще, в вашем случае проще создать статический массив(в том смысле, что static).
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();
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.07.2012, 12:18
Привет! Вот еще темы с ответами:

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

Создать файл g, содержащий элементы файла f (действительные числа) без повторных вхождений - C++
Дан файл f , состоящий из действительных элементов . Создать файл g , содержащий элементы файла f без повторных вхождений помогите...

Вывести из файла слова без повторных букв, кроме "Z" - C++
Всем добрый вечер..вот сижу уже скокадней не могу уломать прогу сделаться((вообщем нужно вывести на экран все слова из текстового файла...

Написать программу, которая определяет число Фибоначчи под номером N и проверяет, является ли это число возрастающим - C++
Доброго времени! Есть задача: &quot;Написать программу, которая определяет число Фибоначчи под номером N и проверяет, является ли это...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
03.07.2012, 12:18
Ответ Создать тему
Опции темы

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