C/C++

С++ сириус Номер числа Фибоначчи

Номер числа Фибоначчи
Последовательность Фибоначчи определяется так:

φ0=0
, φ1=1
, φn=φn−1+φn−2
Дано натуральное число A
. Определите, каким по счёту числом Фибоначчи оно является, то есть выведите такое число n
, что φn=A
. Если A
не является числом Фибоначчи, выведите число −1
.

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

Вводится натуральное число A
(2⩽A⩽2⋅109
).

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

Выведите ответ задачи.
Evgeniy J.
Evgeniy J.
273 
 #include  

#include  

#include  

using namespace std; 

using fib_t = unsigned long long; 

constexpr fib_t last = 12200160415121876738ULL; 

constexpr vector fibonacci() { 

    vector fib{ 0, 1 }; 

    size_t i = 1; 

    auto number = fib.at(i - 1) + fib.back(); 

    do { 

        fib.push_back(number); 

        ++i; 

        number = fib.at(i - 1) + fib.back(); 

    } while (number  value; 

    } while (last < value); 

    return value; 

} 

int main() { 

    const auto num = input(">>> "); 

    const auto pos = check(num); 

    cout
Иван Байков
Иван Байков
50 166
Лучший ответ
Evgeniy J. неправиильно
Evgeniy J. спасибо
Для решения этой задачи можно использовать формулу Бине, которая позволяет находить n-е число Фибоначчи по его индексу:

φn=1/√5⋅( ((1+√5)/2)^n - ((1-√5)/2)^n )

Мы можем использовать эту формулу для нахождения индекса n, если мы знаем значение числа Фибоначчи φn. Для этого мы можем округлить выражение внутри квадратных скобок до ближайшего целого числа и проверить, соответствует ли это числу A. Если да, то найденное целое число будет являться искомым индексом n.

Вот код на C++, который решает эту задачу:

```cpp
#include <iostream>
#include <cmath>

using namespace std;

int main() {
unsigned long long a;
cin >> a;

// ищем ближайшее число Фибоначчи, которое больше или равно A
unsigned long long fib_prev = 0, fib_curr = 1, fib_next;
while (fib_curr < a) {
fib_next = fib_prev + fib_curr;
fib_prev = fib_curr;
fib_curr = fib_next;
}

// проверяем, является ли число A числом Фибоначчи
if (fib_curr == a) {
cout << (fib_prev == 0 ? 1 : 2) << endl;
} else {
// используем формулу Бине для нахождения индекса
double phi = (1 + sqrt(5)) / 2;
double n = log(a * sqrt(5) + 0.5) / log(phi);
if (abs(round(n) - n) < 1e-9) {
cout << round(n) + 1 << endl;
} else {
cout << -1 << endl;
}
}

return 0;
}
```

Здесь мы сначала ищем ближайшее число Фибоначчи, которое больше или равно A, используя простой цикл. Затем мы проверяем, является ли число A числом Фибоначчи. Если да, то мы выводим 1 или 2, в зависимости от того, является ли A первым или вторым числом Фибоначчи соответственно. Если A не является числом Фибоначчи, то мы используем формулу Бине для нахождения индекса и проверяем, является ли полученное число целым. Если да, то выводим его, увеличенное на 1, так как индексация в последовательности Фибоначчи начинается с 0. Если нет, то выводим -1.
Жасулан Айжарыков
Жасулан Айжарыков
19 655
Evgeniy J. можно пожалуйста без плавающей точки double
здравствуйте! до свидания
Александр Фёдоров
Александр Фёдоров
8 899

Похожие вопросы