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

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

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

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


c++ recursion fibonacci
person EasyQuestions    schedule 21.11.2012    source источник
comment
Вам нужен фактический тест в самой функции, а затем вам нужно пройти его. У вас есть надлежащая функция, вам просто нужно сформулировать свою проблему и записать, как вы бы ее сделали, на бумаге, и она придет к вам.   -  person sean    schedule 21.11.2012
comment
Это домашнее задание? Потому что есть более простые способы сделать это без какой-либо рекурсии.   -  person SingerOfTheFall    schedule 21.11.2012
comment
Я знаю, что намного проще сделать это итеративно или использовать математическое доказательство, но это нужно делать рекурсивно.   -  person EasyQuestions    schedule 21.11.2012
comment
Я предполагаю, что вы могли бы просто рекурсивно генерировать числа Фибоначчи, пока вы не получите или не превысите число для проверки? Не уверен, что это можно считать рекурсивным тестированием.   -  person Brian L    schedule 21.11.2012
comment
должен быть более быстрый способ сделать это. также когда вы остановите последовательность?   -  person EasyQuestions    schedule 21.11.2012

Ответы (4)


arrow_upward
4
arrow_downward

Традиционный способ - использовать тест Гесселя. N является числом Фибоначчи тогда и только тогда, когда 5N 2 + 4 или 5N 2 - 4 < / em> - квадратное число. Это обсуждается в этом вопросе SO и этот вопрос SO. Вы также можете найти примеры здесь, но на этой странице есть код на 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) время, как описано, например, в этом вопросе SO < / а>.

person SingerOfTheFall    schedule 21.11.2012
comment
это нужно делать рекурсивно, я думаю, в чем моя проблема, как мне сохранять результат каждый раз, когда выполняется рекурсивный вызов, потому что в рекурсии результат не вычисляется, пока не будет достигнут базовый случай. - person EasyQuestions; 21.11.2012

arrow_upward
1
arrow_downward

Мне это кажется немного неуклюжим, но вы можете попробовать:

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);
}

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

Как указывали другие, есть решения, которые не требуют рекурсии.

person kevintodisco    schedule 21.11.2012
comment
спасибо за публикацию, но для этого необходимо передать два предыдущих номера функции при первом вызове. правильно? - person EasyQuestions; 21.11.2012
comment
@EasyQuestions Не тогда, когда вы объявляете их необязательными аргументами, как я. Первоначального вызова типа isFib(144); будет достаточно. - person kevintodisco; 21.11.2012

arrow_upward
0
arrow_downward

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

person Krease    schedule 21.11.2012

arrow_upward
0
arrow_downward

Числа Фибоначчи обладают математическим свойством. Число является числом Фибоначчи тогда и только тогда, когда одно или оба из (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 по аналогичному вопросу.

person LoveToLearn    schedule 08.01.2015
comment
Не совсем понятно, что это добавляет к принятому ответу, кроме немного другой (удаленной) ссылки…. - person Nathan Tuggy; 08.01.2015