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

Количество чисел Фибоначчи - C++

Восстановить пароль Регистрация
 
Belfegor
Ghost
 Аватар для Belfegor
172 / 172 / 6
Регистрация: 16.09.2012
Сообщений: 524
22.04.2013, 15:28     Количество чисел Фибоначчи #1
Последовательность Фибоначчи - это такая последовательность, в которой каждый элемент равен сумме двух предыдущих, за исключением первых двух элементов F1 = 1, F2 = 1, Fn = Fn-2 + Fn-1.

1 1 2 3 5 8 13 21 …

Задан массив целых чисел, среди которых возможно есть числа Фибоначчи. Подсчитайте количество чисел Фибоначчи в заданном наборе чисел.


Технические условия
Входные данные

В первой строке записано число k - количество чисел, в следующей строке записано k чисел a1, a2, …, ak (0 < k ≤ 1000, 1 ≤ ai < 263).

Выходные данные

Вывести одно число - количество чисел Фибоначчи.
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
40
41
42
43
44
45
46
47
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<string>
#include<set>
#include<algorithm>
#include<vector>
#include<map>
#include<iomanip>
 
using namespace std;
 
#define DB(a) cout<<#a<<"="<<a<<" ";
#define DBN(a) cout<<#a<<"="<<a<<endl;
 
 
typedef long long ll;
typedef unsigned long long ull;
 
 
 
 
ull IsFibon_recursive(ull prev, ull cur, ull x) {
    if (x > prev)
        return IsFibon_recursive(cur, prev + cur, x);
    return x == prev;
}
 
ull IsFibon(ull x) {
    return IsFibon_recursive(0, 1, x);
}
 
int main() {
    ll n, d = 0;
 
    cin >> n;
    ull arr[n];
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    for (int i = 0; i < n; i++) {
        if (IsFibon(arr[i]))d++;
    }
    cout << d << endl;
    return 0;
}
проходит на 50%
считает правильно, проходит на 50%, что делаю не так?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.04.2013, 15:28     Количество чисел Фибоначчи
Посмотрите здесь:

Сумма чисел Фибоначчи C++
Сумма чисел Фибоначчи!!! C++
вывод чисел Фибоначчи C++
C++ Поиск чисел Фибоначчи
C++ Сформировать n чисел Фибоначчи
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
IrineK
Заблокирован
22.04.2013, 16:57     Количество чисел Фибоначчи #2
Учитывая, что 1 ≤ ai < 263, нужен тип unsigned short, а не long.
Количество чисел вообще-то не нужно. Можно считать эту строку в воздух, если условие обязательно.

В проге сразу считываю строку с данными.

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 <sstream>
 
using namespace std;
 
int main()
{   unsigned short num, fPrev, fCur, fNext, count=0;
    string S;
    getline(cin,S);
 
    istringstream iS(S);
    while(iS>>num)
    {   fPrev=1; fCur=1;
        while(num>=fCur)
        {   if (num == fCur) 
            {   count++;
                break;
            }
            fNext = fPrev + fCur;
            fPrev = fCur;
            fCur = fNext;
        }
    }
    
    cout<<"\n\n"<<count<<" Fibonacci numbers found";
    
    cin.get();
    return 0;
}
Belfegor
Ghost
 Аватар для Belfegor
172 / 172 / 6
Регистрация: 16.09.2012
Сообщений: 524
22.04.2013, 17:31  [ТС]     Количество чисел Фибоначчи #3
Цитата Сообщение от IrineK Посмотреть сообщение
Учитывая, что 1 ≤ ai < 263, нужен тип unsigned short, а не long.
сайт отформатировал, там 2^63, Ваша не правильно считает, собственно задача
http://www.e-olimp.com/problems/1358
IrineK
Заблокирован
23.04.2013, 00:40     Количество чисел Фибоначчи #4
Считает правильно, но - медленно )
IrineK
Заблокирован
27.04.2013, 04:00     Количество чисел Фибоначчи #5
Я прошла этот тест.

Чтобы ускорить процесс советую сразу сгенерировать массив из чисел Фибоначчи. Согласно ограничениям на данные вам понадобится 93 числа. Номер числа Фибоначчи и его значение связаны соотношением формулой Бине (есть в Википедии).

Получаем линейный алгоритм:
1) считываем очередное число
2) подставляем его в формулу Бине, определяем соответствующий номер в массиве чисел Фибоначчи
3) сравниваем текущее число с соответствующим числом Фибоначчи, если равны - засчитываем

Время - 15 ms
Belfegor
Ghost
 Аватар для Belfegor
172 / 172 / 6
Регистрация: 16.09.2012
Сообщений: 524
27.04.2013, 14:41  [ТС]     Количество чисел Фибоначчи #6
Цитата Сообщение от IrineK Посмотреть сообщение
Я прошла этот тест.

Чтобы ускорить процесс советую сразу сгенерировать массив из чисел Фибоначчи. Согласно ограничениям на данные вам понадобится 93 числа. Номер числа Фибоначчи и его значение связаны соотношением формулой Бине (есть в Википедии).

Получаем линейный алгоритм:
1) считываем очередное число
2) подставляем его в формулу Бине, определяем соответствующий номер в массиве чисел Фибоначчи
3) сравниваем текущее число с соответствующим числом Фибоначчи, если равны - засчитываем

Время - 15 ms
вот что у еня получилось но на множествах
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
40
41
42
43
44
45
46
47
48
49
50
51
#pragma comment(linker, "/stack:20000000")
 
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <string>
#include <cstdlib>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <set>
#include <list>
#include <deque>
#include <functional>
#include <sstream>
#include <fstream>
using namespace std;
 
#define pii pair<int,int>
#define pll pair<long long,long long>
#define mp make_pair
#define F first 
#define S second
#define ll long long
#define ull unsigned long long
 
 
int main() {
    int n, k = 0;
    set<ull>mnog;
    double a, b, c, p;
    a = (1 + sqrt(5)) / 2;
    b = (1 - sqrt(5)) / 2;
    for (int i = 1; i < 93; i++) {
        mnog.insert((pow(a, i) - pow(b, i)) / sqrt(5));
    }
    cin >> n;
    ll kar[n];
    for (int i = 0; i < n; i++) {
        cin >> kar[i];
    }
    for (int i = 0; i < n; i++) {
        if (mnog.count(kar[i]))k++;
    }
    cout << k << endl;
 
    return 0;
}
50% всего... как вы 3 пункт делали?
iifat
2179 / 1332 / 96
Регистрация: 05.06.2011
Сообщений: 3,689
27.04.2013, 14:53     Количество чисел Фибоначчи #7
Не очень знаю, как там работают множества, но заполнять таки лучше по исходной формуле, целыми числами. При расчёте через степени неизбежны ошибки округления и прочие неточности.
А вот проверять, является ли число числом Фибоначчи -- лучше по формуле. Умножаем на http://www.cyberforum.ru/cgi-bin/latex.cgi?\sqrt5, логарифмируем по большему основанию, http://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{1+sqrt5}2 -- получаем приблизительный номер. Для надёжности можно от него пройтись влево и вправо. Не думаю, чтоб ошибка превышала два.
Belfegor
Ghost
 Аватар для Belfegor
172 / 172 / 6
Регистрация: 16.09.2012
Сообщений: 524
27.04.2013, 15:28  [ТС]     Количество чисел Фибоначчи #8
мы все подходили очень сложно к этому, все намного проще оказалось, всем спасибо, никаких формул никаеого логарифмирования =)
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
27.04.2013, 15:35     Количество чисел Фибоначчи
Еще ссылки по теме:

Последовательность чисел Фибоначчи C++
Сумма чисел Фибоначчи C++
C++ Вычислить количество чисел Фибоначчи до заданного значения

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

Или воспользуйтесь поиском по форуму:
nonedark2008
624 / 502 / 92
Регистрация: 28.07.2012
Сообщений: 1,340
27.04.2013, 15:35     Количество чисел Фибоначчи #9
Цитата Сообщение от Belfegor Посмотреть сообщение
мы все подходили очень сложно к этому, все намного проще оказалось, всем спасибо, никаких формул никаеого логарифмирования =)
На той же самой Википедии есть формула, по которой можно определить является ли число - числом Фиббоначи.
Т.е. не нужно даже генерировать массив из чисел Фиббоначи.
Yandex
Объявления
27.04.2013, 15:35     Количество чисел Фибоначчи
Ответ Создать тему
Опции темы

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