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

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

Войти
Регистрация
Восстановить пароль
 
Sh@dow777
12 / 12 / 3
Регистрация: 10.12.2013
Сообщений: 655
#1

Числа фибоначчи - C++

21.12.2013, 22:47. Просмотров 689. Ответов 15
Метки нет (Все метки)

Написал вот такую программу. Вычисляет n-ый элемент Фибоначчи. Нужно для задачи.

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
#include <stdio.h>
 
long i(long);
int count, T;
long int n, s;
 
int main()
{
    scanf("%d", &T);
 
    for(count = 1;count <= T;++count){
        scanf("%ld", &n);
        s = i(n);
        printf("%ld\n", s);
    }
 
    return 0;
}
 
long i(long n){
    if(n == 0 || n == 1)
        return n;
    else return i(n - 1) + i(n - 2);
}
Вычисляет правильно, но ответ не принимает. Пишет "Превышено максимальное время работы". В чем проблема?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
21.12.2013, 22:47     Числа фибоначчи
Посмотрите здесь:

C++ Числа Фибоначчи
C++ числа Фибоначчи
Числа Фибоначчи C++
Числа Фибоначчи! C++
C++ Числа Фибоначчи
Числа Фибоначчи C++
C++ Числа Фибоначчи
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
max777alex
44 / 44 / 3
Регистрация: 01.02.2012
Сообщений: 822
21.12.2013, 23:18     Числа фибоначчи #2
надо кэшировать

C++
1
2
3
4
5
6
7
8
9
long d[100];
 
long i(long n){
    if(n == 0 || n == 1)
        return 1;
    else if(d[n])
          return d[n];
    else return d[n] = i(n - 1) + i(n - 2);
}
для n == 0 ответ 1
Sh@dow777
12 / 12 / 3
Регистрация: 10.12.2013
Сообщений: 655
21.12.2013, 23:33  [ТС]     Числа фибоначчи #3
не помогло. допустим, 40 член долго вычисляет.
max777alex
44 / 44 / 3
Регистрация: 01.02.2012
Сообщений: 822
21.12.2013, 23:40     Числа фибоначчи #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
#include <stdio.h>
 
long long i(long);
int count, T;
long long n, s;
 
int main()
{
    scanf("%d", &T);
 
    for(count = 1;count <= T;++count){
        scanf("%ld", &n);
        s = i(n);
        printf("%ld\n", s);
    }
 
    return 0;
}
 
long long d[100];
 
long long i(long n){
    if(n == 0 || n == 1)
        return 1;
    else if(d[n])
          return d[n];
    else return d[n] = i(n - 1) + i(n - 2);
}
Sh@dow777
12 / 12 / 3
Регистрация: 10.12.2013
Сообщений: 655
22.12.2013, 00:10  [ТС]     Числа фибоначчи #5
нет, не путаю. попробовал ваш код. теперь система проверки выдает неправильный ответ.
max777alex
44 / 44 / 3
Регистрация: 01.02.2012
Сообщений: 822
22.12.2013, 00:20     Числа фибоначчи #6
А на каком тесте неправильный ответ?

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 <stdio.h>
#include <cstring>
 
long long i(long);
int count, T;
long long n, s;
long long d[100];
 
int main()
{
    scanf("%d", &T);
    memset(d, -1, sizeof d);
    for(count = 1;count <= T;++count){
        scanf("%lld", &n);
        s = i(n);
        printf("%lld\n", s);
    }
 
    return 0;
}
 
long long i(long n){
    if(n == 0 || n == 1)
        return n;
    else if(d[n] != -1)
          return d[n];
    else return d[n] = i(n - 1) + i(n - 2);
}
Nekto
342 / 287 / 10
Регистрация: 23.03.2012
Сообщений: 838
22.12.2013, 00:22     Числа фибоначчи #7
а массив d кто инициализирует нулями?
UPD а, уже вариант с мемсетом кинули =)
max777alex
44 / 44 / 3
Регистрация: 01.02.2012
Сообщений: 822
22.12.2013, 00:24     Числа фибоначчи #8
вообще он по умолчанию нулями забивается, во всяком случае на g++ и на visual c++ это так, а в последнем коде забиваем его -1 функцией memset
Sh@dow777
12 / 12 / 3
Регистрация: 10.12.2013
Сообщений: 655
22.12.2013, 00:27  [ТС]     Числа фибоначчи #9
на 2. первый тест в порядке. я понимаю, что рекурсия замедляет вычисления, нагружает память. но как можно вычислить без рекурсии, пока не знаю. сейчас приступаю к изучению массивов.
max777alex
44 / 44 / 3
Регистрация: 01.02.2012
Сообщений: 822
22.12.2013, 00:29     Числа фибоначчи #10
без рекурсии можно просто пройти циклом по массиву и посчитать все значения до n

C++
1
2
3
4
5
6
7
8
9
10
const int MAXN = 100;
long long d[MAXN];
 
d[0] = 0;
d[1] = 1;
 
// read n
 
for(int i = 2; i < n + 1; ++i)
   d[i] = d[i - 1] + d[i - 2];
Kuzia domovenok
1889 / 1744 / 117
Регистрация: 25.03.2012
Сообщений: 5,917
Записей в блоге: 1
22.12.2013, 00:37     Числа фибоначчи #11
А время превышено потому что рекурсия это крайне медленный метод вычисления чисел Фибоначчи и я совершенно не могу понять, зачем её приводят в пример постоянно, когда возникает эта задача?
Единственный ответ может быть - рекурсия тут лишь для демонстрации рекурсии!
Во всём остальном удобнее считать в цикле!
Сам посуди: зачем рекурсивно вычислять fib(n-2)+fib(n-1), два раза (а на деле больше) проходя весь ряд Фибонначи!?? Уж лучше в цикле посчитать.
Sh@dow777
12 / 12 / 3
Регистрация: 10.12.2013
Сообщений: 655
22.12.2013, 00:38  [ТС]     Числа фибоначчи #12
Спасибо. Оказался правильным вариант с мемсетом. Пока не совсем понял вашу программу. Но это потому, что пока не изучил массивы. Но все же хочу спросить. По идее, мой вариант тоже частично верный? Почему при проверке именно на 2 тесте выдавало ошибку?
max777alex
44 / 44 / 3
Регистрация: 01.02.2012
Сообщений: 822
22.12.2013, 00:39     Числа фибоначчи #13
Цитата Сообщение от Sh@dow777 Посмотреть сообщение
Спасибо. Оказался правильным вариант с мемсетом. Пока не совсем понял вашу программу. Но это потому, что пока не изучил массивы. Но все же хочу спросить. По идее, мой вариант тоже частично верный? Почему при проверке именно на 2 тесте выдавало ошибку?
а второй тест он какой?
Kuzia domovenok
1889 / 1744 / 117
Регистрация: 25.03.2012
Сообщений: 5,917
Записей в блоге: 1
22.12.2013, 00:40     Числа фибоначчи #14
max777alex, можно и на массив не тратить память.
C++
1
2
3
4
5
6
long first=second=1;
for (int i=2; i<n; i++){
  second=first+second;
  first=second-first;
}
printf("%ld", second);
max777alex
44 / 44 / 3
Регистрация: 01.02.2012
Сообщений: 822
22.12.2013, 00:40     Числа фибоначчи #15
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
А время превышено потому что рекурсия это крайне медленный метод вычисления чисел Фибоначчи и я совершенно не могу понять, зачем её приводят в пример постоянно, когда возникает эта задача?
Единственный ответ может быть - рекурсия тут лишь для демонстрации рекурсии!
Во всём остальном удобнее считать в цикле!
Сам посуди: зачем рекурсивно вычислять fib(n-2)+fib(n-1), два раза (а на деле больше) проходя весь ряд Фибонначи!?? Уж лучше в цикле посчитать.
почему же проходя весь ряд Фибонначи? каждое значение вычисляется только один раз, потом кэшируется и дальше просто используется, да и работает с той же асимптотикой, что и цикл
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
22.12.2013, 01:09     Числа фибоначчи
Еще ссылки по теме:

C++ Числа Фибоначчи
Числа Фибоначчи C++
C++ Числа Фибоначчи
Числа Фибоначчи C++
Числа фибоначчи C++

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

Или воспользуйтесь поиском по форуму:
Sh@dow777
12 / 12 / 3
Регистрация: 10.12.2013
Сообщений: 655
22.12.2013, 01:09  [ТС]     Числа фибоначчи #16
max777alex, в смысле? просто показало, что на втором тесте вычисляет больше 1.0000.

Добавлено через 26 минут
Kuzia domovenok, Хороший вариант. Даже обидно, что я до этого не додумался. Я только начал изучать C. За 3 дня надо сдать хотя бы 10 задач. На каникулах усердно буду грызть гранит C++ и ассемблера
Yandex
Объявления
22.12.2013, 01:09     Числа фибоначчи
Ответ Создать тему
Опции темы

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