Проверьте, является ли число Фибоначчи

Question

Я знаю, как составить список чисел Фибоначчи, но я не знаю, как я могу проверить, принадлежит ли данное число к списку Фибоначчи - один из способов, который приходит в голову, - это генерировать список Фибоначчи. числа до этого числа и посмотреть, принадлежит ли он к массиву, но должен быть другой, более простой и быстрый метод.

Есть идеи?

Answer 1

Основываясь на предыдущих ответах мною и psmears, я написал этот код C #.

Он медленно проходит шаги, и его можно явно уменьшить и оптимизировать:

// Input: T: number to test.
// Output: idx: index of the number in the Fibonacci sequence.
//    eg: idx for 8 is 6. (0, 1, 1, 2, 3, 5, 8)
// Return value: True if Fibonacci, False otherwise.
static bool IsFib(long T, out int idx)
{
    double root5 = Math.Sqrt(5);
    double PSI = (1 + root5) / 2;

    // For reference, IsFib(72723460248141) should show it is the 68th Fibonacci number

    double a;

    a = T*root5;
    a = Math.Log(a) / Math.Log(PSI);
    a += 0.5;
    a = Math.Floor(a);
    idx = (Int32)a;

    long u = (long)Math.Floor(Math.Pow(PSI, a)/root5 + 0.5);

    if (u == T)
    {
        return true;
    }
    else
    {
        idx = 0;
        return false;
    }
}

Тестирование показывает, что это работает для первых 69 чисел Фибоначчи, но разбивается на 70-е.

F(69) = 117,669,030,460,994 - Works
F(70) = 190,392,490,709,135 - Fails

В целом, если вы не используете какую-либо библиотеку BigInt, вероятно, лучше иметь простую таблицу поиска чисел Фибоначчи и проверить это, а не запускать алгоритм.

Список первых 300 номеров доступен онлайн.

Но этот код действительно описывает работоспособный алгоритм при условии, что вы достаточно точны и не переполняете систему представления чисел.

Answer 2

Re: Код Ахмада - более простой подход без рекурсии и указателей, довольно наивный, но почти не требующий вычислительной мощности для чего-либо, кроме действительно титанических чисел (примерно 2N дополнений для проверки N-го числа фиб, которое на современной машине в худшем случае займет миллисекунды)

// возвращает pos, если найдет что-либо, 0, если нет (C / C ++ обрабатывает любое значение! = 0 как истину, то есть тот же конечный результат)

int isFib (long n)
{
    int pos = 2;
    long last = 1;
    long current = 1;
    long temp;

    while (current < n)
    {
        temp = last;
        last = current;
        current = current + temp;
        pos++;
    }

    if (current == n)
        return pos;
    else
        return 0;

}

Answer 3

Общее выражение для числа Фибоначчи F (n) = [[(1 + sqrt (5)) / 2] sup n + 1 - [(1-sqrt (5)) / 2] sup n + 1] / sqrt (5) ..... (*) Вторая экспонента стремится к нулю при больших n и выполняя Числовые операции мы получаем F (n) = [(1.618) sup n + 1] / 2.236

Если K - это число, которое нужно проверить, log (k * 2.2336) / log (1.618) должен быть целым числом!

Пример для К равен 13 мой калькулятор дает ответ 7.00246 Для K, равного 14, ответ равен 7,1564.

Вы можете повысить достоверность результата, взяв ближайшее целое число к ответьте и подставьте (*), чтобы подтвердить, что результат равен K

Answer 4

Java решение может быть сделано, как показано ниже. Но все же это можно оптимизировать

Следующее решение работает для

1. 1≤T≤10 ^ 5
2. 1≤N≤10 ^ 10

T нет тестовых случаев, N это диапазон числа

    import java.util.Scanner;
    import java.math.BigDecimal;
    import java.math.RoundingMode;

    public class FibonacciTester {
        private static BigDecimal zero = BigDecimal.valueOf(0);
        private static BigDecimal one = BigDecimal.valueOf(1);
        private static BigDecimal two = BigDecimal.valueOf(2);
        private static BigDecimal four = BigDecimal.valueOf(4);
        private static BigDecimal five = BigDecimal.valueOf(5);

        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            int n = sc.nextInt();
            BigDecimal[] inputs = new BigDecimal[n];
            for (int i = 0; i < n; i++) {
                inputs[i] = sc.nextBigDecimal();
            }

            for (int i = 0; i < inputs.length; i++) {
                if (isFibonacci(inputs[i]))
                    System.out.println("IsFibo");
                else
                    System.out.println("IsNotFibo");
            }


        }

        public static boolean isFibonacci(BigDecimal num) {
            if (num.compareTo(zero) <= 0) {
                return false;
            }

            BigDecimal base = num.multiply(num).multiply(five);
            BigDecimal possibility1 = base.add(four);
            BigDecimal possibility2 = base.subtract(four);


            return (isPerfectSquare(possibility1) || isPerfectSquare(possibility2));
        }

        public static boolean isPerfectSquare(BigDecimal num) {
            BigDecimal squareRoot = one;
            BigDecimal square = one;
            BigDecimal i = one;
            BigDecimal newSquareRoot;
            int comparison = -1;

            while (comparison != 0) {
                if (comparison < 0) {
                    i = i.multiply(two);
                    newSquareRoot = squareRoot.add(i).setScale(0, RoundingMode.HALF_UP);
                } else {
                    i = i.divide(two);
                    newSquareRoot = squareRoot.subtract(i).setScale(0, RoundingMode.HALF_UP);
                }

                if (newSquareRoot.compareTo(squareRoot) == 0) {
                    return false;
                }

                squareRoot = newSquareRoot;
                square = squareRoot.multiply(squareRoot);
                comparison = square.compareTo(num);
            }

            return true;
        }
    }

Answer 5

версия Scala-

def isFib(n: Int): Boolean = {

def checkFib(f1: Int = 1, f2: Int = 1): Boolean = {

if(n == f1 || n == f2) true
else if(n < f2) false
else checkFib(f2, f1+f2)

}

checkFib()

}

Answer 6

Это моё решение, я не уверен, что оно соответствует критериям. Надеюсь, это поможет!

def is_fibonacci?(i)
  a,b=0,1
    until b >= i
        a,b=b,a+b
        return true if b == i
    end
end

что a, b = b, a + b делает

 0, 1 = 1, 0 +1
 1, 1 = 1, 1 + 1
 1, 2 = 2, 1 + 2
 2, 3 = 3, 2 + 3

fib1 = fib2
fib2 = fib1 + fib2

Answer 7

#include <stdio.h>
#include <math.h>

int main()
{
int number_entered, x, y;

printf("Please enter a number.\n");
scanf("%d", &number_entered);
x = y = 5 * number_entered^2 + 4;        /*Test if 5N^2 + 4 is a square number.*/
x = sqrt(x);
x = x^2;
if (x == y)
{
        printf("That number is in the Fibonacci sequence.\n");
    }
x = y = 5 * number_entered^2 - 4;        /*Test if 5N^2 - 4 is a square number.*/
x = sqrt(x);
x = x^2;
if (x == y)
{
    printf("That number is in the Fibonacci sequence.\n");
}
else
{
    printf("That number isn't in the Fibonacci sequence.\n");
}
return 0;
}

Будет ли это работать?

Answer 8

int isfib(int n /* number */, int &pos /* position */)
{
   if (n == 1)
   {
      pos=2;  // 1 1
      return 1;
   }
   else if (n == 2)
   {
      pos=3;  // 1 1 2
      return 1;
   }
   else
   {
      int m = n /2;
      int p, q, x, y;
      int t1=0, t2 =0;
      for (int i = m; i < n; i++)
      {
        p = i;
        q = n -p;    // p + q = n
        t1 = isfib(p, x);
        if (t1) t2 = isfib(q, y);
        if (t1 && t2 && x == y +1)
        {
           pos = x+1;
           return 1; //true
        }
      }
      pos = -1;
      return 0; //false
   }
}

Как насчет этого?

Answer 9

Я провел несколько тестов методов, представленных здесь, а также простое сложение, предварительное вычисление массива и запоминание результатов в хэше. По крайней мере, для Perl метод возведения в квадрат немного быстрее, чем логарифмический, возможно, на 20% быстрее. Как указывает Абеленки, это компромисс между тем, есть ли у вас место для возведения в квадрат битовых чисел.

Конечно, самый быстрый способ - это хэшировать все числа Фибоначчи в вашем доменном пространстве. В соответствии с еще одной точкой зрения Абеленки, есть только 94 из этих присосок, которые меньше, чем 2 ^ 64.

Вы должны просто предварительно вычислить их и поместить в хэш Perl, словарь Python или что-то еще.

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

Answer 10

Насколько велики числа, с которыми вы имеете дело?

Может ли справочная таблица работать на вас? (предварительно вычисленный список номеров, по которым вы можете искать)

Существует также выражение в закрытой форме , которое, я думаю, вы могли бы инвертировать, чтобы получить аналитический ответ (хотя я не математик, поэтому не могу обещать, что это предложение имеет смысл)