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

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

Войти
Регистрация
Восстановить пароль
 
Shato
2 / 2 / 0
Регистрация: 16.03.2011
Сообщений: 82
#1

Фибоначчи - C++

13.11.2011, 14:42. Просмотров 940. Ответов 4
Метки нет (Все метки)

Доброго времени суток. Написал код задачки, но работает ООЧЕНЬ долго. Если сможете помогите исправить, спасибо !
ограничение времени на тест: 0.5 сек.
ограничение памяти на тест: 65536 KB.
ввод: standart
вывод: standart


N-ое число Фибоначчи можно посчитать, используя следующую рекурсивную функцию:

fib(n)

if (n == 0) return 0;

if (n == 1) return 1;

return fib(n - 2) + fib(n - 1);


Ваша задача, для заданного числа N посчитать, сколько раз вызовется функция fib(0) и fib(1) при таком способе подсчета N-го числа Фибоначчи.

Входные данные
В единственной строке содержится целое число N (0 <= N <= 100000).

Выходные данные
Выведите два целых числа - количество вызовов соответственно fib(0) и fib(1). Поскольку ответ может быть очень большим, выведите эти числа по модулю 10000019.

Пример

Ввод
4

Вывод
2 3

Код:
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
#include <iostream>
using namespace std;
 
typedef long long lol;
lol MOD = 10000019;
 
lol fib (lol n, lol &k, lol &p)
{
    if (n == 0)
    {
        k++; 
        return 0;
    }
    if (n == 1)
    {
        p++; 
        return 1;
    }
    return fib (n - 2, k, p) + fib(n - 1, k, p);
}
 
int main() 
{
#ifndef ONLINE_JUDGE
    freopen ("input.txt", "r", stdin);
    freopen ("output.txt", "w", stdout);
#endif
    lol k = 0, p = 0, n;
    cin >> n;
    fib(n, k, p);
 
    cout << k % MOD  << ' ' << p % MOD << endl;;
    
    return 0;
}
Добавлено через 43 минуты
Поможете?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.11.2011, 14:42
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Фибоначчи (C++):

Набрать с чисел Фибоначчи в интервале от 1 до 100, только просто числа, а также их порядковые номера в ряду Фибоначчи - C++
Помогите с задачкой Набрать с чисел Фибоначчи в интервале от 1 до 100, только просто числа, а также их порядковые номера в ряду...

фибоначчи - C++
написать программу которая вычисляет столбцом числа фибоначчи

Фибоначчи - C++
Описать не рекурсивную функцию Fib целого типа, вычисляющую N-е число Фибоначчи F(N) по формуле: F(1) = F(2) = 1, F(k) = F(k-2) + F(k-1),...

Фибоначчи - C++
Дано целое число N(&gt;1), которое является числом Фибоначчи: N=Fk. Найти целые числа Fk-1 и Fk+1 - предыдущие и последующее числа...

Фибоначчи - C++
14. В заданном целочисленном массиве распечатать те элементы, порядковые номера которых – числа Фибоначчи, а также определить количество...

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

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
soon
2540 / 1305 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
13.11.2011, 15:34 #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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <iostream>
#include <cstring>
#include <ctime>
 
long long f0, f1;
 
long long fib(int n)
{
    if(n == 0)
    {
        ++f0;
        return 0;
    }
    else if(n == 1)
    {
        ++f1;
        return 1;
    }
    else return fib(n - 2) + fib(n - 1);
}
    
int main()
{
    std::cout << fib(40) << ' ';
    std::cout << clock() / static_cast<double>(CLOCKS_PER_SEC) << std::endl;
 
    clock_t start = clock();
    long long arr[3];
    arr[0] = 0;
    arr[1] = arr[2] = 1;
    for(int i = 3; i <= 40; ++i)
    {
        arr[0] = arr[1];
        arr[1] = arr[2];
        arr[2] = arr[1] + arr[0];
    }
    std::cout << arr[2] << ' ' << (clock() - start) / static_cast<double>(CLOCKS_PER_SEC) << std::endl;
    return 0;
}
Код
soon@coming:~/src$ g++ tmp.cpp -o tmp
soon@coming:~/src$ ./tmp
102334155 6.63
102334155 0
soon@coming:~/src$
f(1) будет в arr[2], f(0) будет в arr[1].
Дальше 6 секунд ждать не захотел =)

Добавлено через 1 минуту
Но! Нужно учесть n = 0, 1, 2. Можно изначально заполнить массив нулями, тогда будет на 3 итерации больше, можно добавить if/else на n.
Dar101
40 / 40 / 1
Регистрация: 12.05.2011
Сообщений: 109
13.11.2011, 16:11 #3
Рекурсией вы за полсекунды, боюсь, никогда не посчитаете N=100000.

По условию задачи:
«Ваша задача, для заданного числа N посчитать, сколько раз вызовется функция fib(0) и fib(1) при таком способе подсчета N-го числа Фибоначчи».

То есть сами функции вызывать не обязательно, достаточно посчитать их число вызовов.

Вот вам набросок решения, думаю, с типами, размерами и случаем i<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
25
26
27
28
29
#include <iostream>
#include <conio.h>
 
long int MOD = 10000019;
unsigned int cur_zero=0;
unsigned int cur_one=1;
unsigned int prev_zero=1;
unsigned int prev_one=0;
 
int main() 
{
    int n;
    int buffer_zero = 0;
    int buffer_one = 0;
    std::cin >> n;
    for (int i=2; i<=n; i++)
    {
        buffer_zero = cur_zero;
        buffer_one = cur_one;
        cur_zero = cur_zero+prev_zero;
        cur_one  = cur_one+prev_one;
        prev_zero = buffer_zero;
        prev_one = buffer_one;
    }
 
    std::cout << cur_one % MOD  << ' ' << cur_zero % MOD << std::endl;
    getch();
    return 0;
}
Xind
275 / 148 / 7
Регистрация: 05.11.2011
Сообщений: 425
Записей в блоге: 1
13.11.2011, 17:39 #4
Shato, Может стоит попробовать сделать через золотое сечение?
Shato
2 / 2 / 0
Регистрация: 16.03.2011
Сообщений: 82
13.11.2011, 18:26  [ТС] #5
Цитата Сообщение от Xind Посмотреть сообщение
Shato, Может стоит попробовать сделать через золотое сечение?
я хз как, но похоже, что функцией пользоваться вообще не надо
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.11.2011, 18:26
Привет! Вот еще темы с ответами:

Фибоначчи - C++
#include &lt;iostream&gt; using namespace std; int pay (int k) { unsigned int a; int b,p; a = 0; a = 1; a = 1; for (int i=4; i...

Цикл while - фибоначчи - C++
Вводится номер N . Определить N-ое по порядку число Фибоначчи . Используя цикл while ( do while ) . #include &lt;stdio.h&gt; #include...

Числа фибоначчи - C++
в чем недостаток этого алгоритма чисел фибоначчи? #include &lt;iostream&gt; using namespace std; int main() { __int64 a; int n; ...

Число Фибоначчи - C++
Дан одномерный массив А неупорядоченных натуральных чисел.Вывести на экран те элементы массива, которые нельзя представить суммой двух...


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

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

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