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

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

Войти
Регистрация
Восстановить пароль
 
Belfegor
Ghost
172 / 172 / 6
Регистрация: 16.09.2012
Сообщений: 526
#1

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

22.04.2013, 15:28. Просмотров 1008. Ответов 8
Метки нет (Все метки)

Последовательность Фибоначчи - это такая последовательность, в которой каждый элемент равен сумме двух предыдущих, за исключением первых двух элементов 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%, что делаю не так?
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.04.2013, 15:28
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Количество чисел Фибоначчи (C++):

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

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

Вычислить количество чисел Фибоначчи до заданного значения - C++
#include &lt;iostream&gt; #include &lt;cstdlib&gt; using namespace std; int main () { int n, a = 0, b = 1, c = a + b; cin &gt;&gt; n; cout &lt;&lt;...

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

Вывести количество чётных чисел Фибоначчи меньше заданного числа - C++
Нужно вывести количество четных чисел Фибоначчи меньше заданного числа

Вывести количество чисел Фибоначчи, в записи которых старшая цифра парная - C++
Нужно вывести количество n-значных чисел Фибоначчи (0,1,1,2,3,...f(n)=f(n-1)+f(n-2)), в записи которых старшая цифра парная. Могу...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
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;
}
1
Belfegor
Ghost
172 / 172 / 6
Регистрация: 16.09.2012
Сообщений: 526
22.04.2013, 17:31  [ТС] #3
Цитата Сообщение от IrineK Посмотреть сообщение
Учитывая, что 1 ≤ ai < 263, нужен тип unsigned short, а не long.
сайт отформатировал, там 2^63, Ваша не правильно считает, собственно задача
http://www.e-olimp.com/problems/1358
0
IrineK
Заблокирован
23.04.2013, 00:40 #4
Считает правильно, но - медленно )
0
IrineK
Заблокирован
27.04.2013, 04:00 #5
Я прошла этот тест.

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

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

Время - 15 ms
1
Belfegor
Ghost
172 / 172 / 6
Регистрация: 16.09.2012
Сообщений: 526
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 пункт делали?
0
iifat
2235 / 1388 / 103
Регистрация: 05.06.2011
Сообщений: 3,822
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 -- получаем приблизительный номер. Для надёжности можно от него пройтись влево и вправо. Не думаю, чтоб ошибка превышала два.
1
Belfegor
Ghost
172 / 172 / 6
Регистрация: 16.09.2012
Сообщений: 526
27.04.2013, 15:28  [ТС] #8
мы все подходили очень сложно к этому, все намного проще оказалось, всем спасибо, никаких формул никаеого логарифмирования =)
0
nonedark2008
908 / 647 / 134
Регистрация: 28.07.2012
Сообщений: 1,760
27.04.2013, 15:35 #9
Цитата Сообщение от Belfegor Посмотреть сообщение
мы все подходили очень сложно к этому, все намного проще оказалось, всем спасибо, никаких формул никаеого логарифмирования =)
На той же самой Википедии есть формула, по которой можно определить является ли число - числом Фиббоначи.
Т.е. не нужно даже генерировать массив из чисел Фиббоначи.
1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
27.04.2013, 15:35
Привет! Вот еще темы с ответами:

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

Для чисел от -50 до 50 найти количество четных отрицательных и количество положительных нечетных чисел - C++
Ребят,всем привет! Помогите пожалуйста решить данную задачу.Ее нужно написать на я зыке C /C++,каждую из них с постусловием и...

Найти количество отрицательных чисел, количество нулевых и подсчитать сумму положительных чисел - C++
Т.к. я полный 0 в этом, вынужден обратиться к профи) надеюсь на вашу помощь. 1. Произвести следующую обработку 15 целых чисел: найти...

Поиск чисел Фибоначчи - C++
Доброго времени суток! Написал программку, которая находит значение n-элемента в последовательности Фибоначчи. Изначально в ней...


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

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

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