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

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

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

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

21.12.2013, 22:47. Просмотров 716. Ответов 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);
}
Вычисляет правильно, но ответ не принимает. Пишет "Превышено максимальное время работы". В чем проблема?
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
21.12.2013, 22:47
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Числа фибоначчи (C++):

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

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

Составьте программу, позволяющую найти все числа Фибоначчи, меньшие заданного числа N - C++
Помогите, пожалуйста. Вот сама задача: Пара кроликов каждый месяц дает приплод – двух кроликов (самца и самку), от которых через два...

Числа Фибоначчи: с какого числа начинается ряд? - C++
Недавно столкнулся с такой проблемой: Некоторые источники утверждают(например Википедия),что ряд чисел Фибоначчи начинается с 0(т.е....

Числа Фибоначчи, простые числа и делители - C++
Write a menu() function that prints the following menu and returns the selected choice: 1. Fibonacci series 2. Prime numbers 3....

Числа Фибоначчи - C++
Здраствуйте! Есть такое задание С максимальной эффективностью решить данную задачу: Вывести количество чисел Фибоначчи (0, 1, 1, 2,...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
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
0
Sh@dow777
12 / 12 / 3
Регистрация: 10.12.2013
Сообщений: 674
21.12.2013, 23:33  [ТС] #3
не помогло. допустим, 40 член долго вычисляет.
0
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);
}
0
Sh@dow777
12 / 12 / 3
Регистрация: 10.12.2013
Сообщений: 674
22.12.2013, 00:10  [ТС] #5
нет, не путаю. попробовал ваш код. теперь система проверки выдает неправильный ответ.
0
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);
}
0
Nekto
342 / 287 / 10
Регистрация: 23.03.2012
Сообщений: 838
22.12.2013, 00:22 #7
а массив d кто инициализирует нулями?
UPD а, уже вариант с мемсетом кинули =)
0
max777alex
44 / 44 / 3
Регистрация: 01.02.2012
Сообщений: 822
22.12.2013, 00:24 #8
вообще он по умолчанию нулями забивается, во всяком случае на g++ и на visual c++ это так, а в последнем коде забиваем его -1 функцией memset
0
Sh@dow777
12 / 12 / 3
Регистрация: 10.12.2013
Сообщений: 674
22.12.2013, 00:27  [ТС] #9
на 2. первый тест в порядке. я понимаю, что рекурсия замедляет вычисления, нагружает память. но как можно вычислить без рекурсии, пока не знаю. сейчас приступаю к изучению массивов.
0
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];
0
Kuzia domovenok
1891 / 1746 / 118
Регистрация: 25.03.2012
Сообщений: 5,925
Записей в блоге: 1
22.12.2013, 00:37 #11
А время превышено потому что рекурсия это крайне медленный метод вычисления чисел Фибоначчи и я совершенно не могу понять, зачем её приводят в пример постоянно, когда возникает эта задача?
Единственный ответ может быть - рекурсия тут лишь для демонстрации рекурсии!
Во всём остальном удобнее считать в цикле!
Сам посуди: зачем рекурсивно вычислять fib(n-2)+fib(n-1), два раза (а на деле больше) проходя весь ряд Фибонначи!?? Уж лучше в цикле посчитать.
0
Sh@dow777
12 / 12 / 3
Регистрация: 10.12.2013
Сообщений: 674
22.12.2013, 00:38  [ТС] #12
Спасибо. Оказался правильным вариант с мемсетом. Пока не совсем понял вашу программу. Но это потому, что пока не изучил массивы. Но все же хочу спросить. По идее, мой вариант тоже частично верный? Почему при проверке именно на 2 тесте выдавало ошибку?
0
max777alex
44 / 44 / 3
Регистрация: 01.02.2012
Сообщений: 822
22.12.2013, 00:39 #13
Цитата Сообщение от Sh@dow777 Посмотреть сообщение
Спасибо. Оказался правильным вариант с мемсетом. Пока не совсем понял вашу программу. Но это потому, что пока не изучил массивы. Но все же хочу спросить. По идее, мой вариант тоже частично верный? Почему при проверке именно на 2 тесте выдавало ошибку?
а второй тест он какой?
0
Kuzia domovenok
1891 / 1746 / 118
Регистрация: 25.03.2012
Сообщений: 5,925
Записей в блоге: 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);
0
max777alex
44 / 44 / 3
Регистрация: 01.02.2012
Сообщений: 822
22.12.2013, 00:40 #15
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
А время превышено потому что рекурсия это крайне медленный метод вычисления чисел Фибоначчи и я совершенно не могу понять, зачем её приводят в пример постоянно, когда возникает эта задача?
Единственный ответ может быть - рекурсия тут лишь для демонстрации рекурсии!
Во всём остальном удобнее считать в цикле!
Сам посуди: зачем рекурсивно вычислять fib(n-2)+fib(n-1), два раза (а на деле больше) проходя весь ряд Фибонначи!?? Уж лучше в цикле посчитать.
почему же проходя весь ряд Фибонначи? каждое значение вычисляется только один раз, потом кэшируется и дальше просто используется, да и работает с той же асимптотикой, что и цикл
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
22.12.2013, 00:40
Привет! Вот еще темы с ответами:

Числа Фибоначчи! - C++
Помогите написать вот такую ​​программу: Заданная последовательность n действительных чисел. Вычислить сумму чисел, порядковые номера...

Числа Фибоначчи - C++
Ввести целое число N &gt; 1. Последовательность чисел Фибоначчи FK (целого типа) определяется следующим образом: F1 =1, F2= 1, FK=FK-2 +...

Числа Фибоначчи - C++
Не понимаю, толком рекурсию.....В какой последовательности будет выполняться код если аргумент будет равен 5 например long fibonacci(int...

Числа Фибоначчи - C++
Вводится натуральное число F. Найти число n, для которого значение n-ого числа Фибоначчи является ближайшим числу F, но не больше его. ...


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

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

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