как рекурсивно проверить, является ли число числом Фибоначчи?

Question

как рекурсивно проверить, является ли число числом Фибоначчи?

Мне нужно написать программу, которая рекурсивно проверяет, является ли число числом Фибоначчи; Эту же задачу легко выполнить итеративно; также легко найти n-е число Фибоначчи рекурсивно, но я застрял в том, как проверить, является ли число Фибоначчи рекурсивным.
вот код для поиска n-го фиб. число:

int fib(int n){
if (n <= 1){
return n;
}else {
return (fib(n-1) + fib (n-2));
}
}

что я не знаю, как сделать, это как изменить код выше, чтобы проверить, является ли данное число Фибоначчи?

3

c++fibonacci recursion

Решение

Другие решения

Это немного неуклюже для меня, но вы можете попробовать:

bool isFib(int numToCheck int twoPrev = 0, int prev = 1) {
if (numToCheck == twoPrev || numToCheck == prev)
return true;

int currentFibNumber = twoPrev + prev;
if (currentFibNumber == numToCheck)
return true;
else if (currentFibNumber > numToCheck)
return false;

return isFib(numToCheck, prev, currentFibNumber);
}

Это в основном повторяет числа Фибоначчи с помощью рекурсии, пока либо сгенерированное число не превысит проверяемое вами значение, либо не будет найдено совпадение.

Как уже отмечали другие, есть решения для этого, которые не требуют рекурсии.

1

Определение, является ли число числом Фибоначчи Похоже, то же самое, но в Java — вы могли бы получить то, что вы ищете там.

0

Числа Фибоначчи имеют математическое свойство.
Число есть число Фибоначчи тогда и только тогда, когда один или оба из (5 * n ^ 2 + 4) или (5 * n ^ 2 — 4) являются идеальным квадратом (Источник: Wiki).

Этот метод намного проще, чем метод рекурсивного вызова функций. Проверьте эту ссылку:

http://www.geeksforgeeks.org/check-number-fibonacci-number/

Другой метод:

static bool IsFib(long n)//n is the number to be checked
{
double root5 = Math.Sqrt(5);
double phi = (1 + root5) / 2;

long idx    = (long)Math.Floor( Math.Log(n*root5) / Math.Log(phi) + 0.5 );
long u = (long)Math.Floor( Math.Pow(phi, idx)/root5 + 0.5);

return (u == n);
}

Этот код работает для больших входов.
Он был опубликован abelenky в stackoverflow для аналогичного вопроса.

0

Источник

Accepted Answer

Традиционным способом является использование теста Гесселя. N является числом Фибоначчи тогда и только тогда, когда 5N² + 4 или же 5N² — 4 квадратное число Это обсуждается в этот ТАК вопрос а также этот ТАК вопрос. Вы также можете найти примеры Вот, но эта страница имеет код на Python (хотя это легко понять).

Теперь, если вас попросили использовать рекурсию специально … Один из способов — начать генерацию чисел Фибоначчи, пока сгенерированное число не станет больше или равно числу, которое вы тестируете. Если есть совпадение, проверенное число принадлежит последовательности Фибоначчи. Если совпадения нет, и вы сгенерировали число больше проверенного, то проверенное число не является числом Фибоначчи.

Вот основной (и уродливый) пример для вас:

bool isFibonacci( int testedNumber, int a = 1, int b = 1 )
{
if( testedNumber == 0 || testedNumber == 1 )
return true;//returning true for 0 and 1 right away.
int nextFib = a + b;//getting the next number in the sequence
if( nextFib > testedNumber )
return false;//if we have passed the tested number, it's not in the sequence
else if( nextFib == testedNumber )
return true;//if we have a perfect match, the tested number is in the sequence
else
isFibonacci( testedNumber, b, nextFib );//otherwise, get the next fibonacci number and repeat.
}

Используйте это так же, как isFibonacci( the_number_you_want_to_test );

Обратите внимание, что числа Фибоначчи могут быть рассчитаны в O(log n) время, как описано, например, в этот ТАК вопрос.

4