c++ - serie - Prueba si un número es fibonacci

sucesion de fibonacci ejercicios

Question

Sé cómo hacer la lista de los números de Fibonacci, pero no sé cómo puedo probar si un número dado pertenece a la lista de fibonacci. Una forma en la que se tiene en cuenta es generar la lista de fib. numera hasta ese número y ve si pertenece a la matriz, pero tiene que haber otro método más simple y rápido.

Algunas ideas ?

Answer 1

¿Qué tan grandes son las cifras con las que estás lidiando?

¿Podría una tabla de búsqueda funcionar para usted? (una lista precalculada de números que puede buscar)

También hay una expresión de forma cerrada que supongo que podrías invertir para obtener la respuesta analíticamente (aunque no soy matemático, así que no puedo prometer que esta sugerencia tiene sentido)

Answer 2

Basado en respuestas anteriores de mí y psmears, escribí este código de C #.

Pasa por los pasos lentamente, y se puede reducir y optimizar claramente:

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

Las pruebas revelan que esto funciona para los primeros 69 números de Fibonacci, pero se descompone para el 70º.

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

En total, a menos que esté usando una biblioteca de BigInt de algún tipo, probablemente sea mejor tener una tabla de búsqueda simple de los Números de Fibonacci y verificar eso, en lugar de ejecutar un algoritmo.

Una lista de los primeros 300 números está disponible en línea.

Pero este código describe un algoritmo viable, siempre que tenga suficiente precisión y no desborde su sistema de representación numérica.

Answer 3

Como los números de Fibonacci crecen exponencialmente, el método que sugieres es bastante rápido. Otro es esto .

Answer 4

Consulte la sección "Reconocimiento de números de Fibonacci" en el artículo de Wikipedia sobre los números de Fibonacci .

Answer 5

De Wikipedia: http://en.wikipedia.org/wiki/Fibonacci_number

Un entero positivo z es un número de Fibonacci si y solo si uno de 5z ^ 2 + 4 o 5z ^ 2 - 4 es un cuadrado perfecto.

Answer 6

Ejecuté algunos puntos de referencia sobre los métodos presentados aquí junto con una simple adición, pre-cálculo de una matriz y memorando los resultados en un hash. Para Perl, al menos, el método de cuadratura es un poco más rápido que el método logarítmico, tal vez un 20% más rápido. Como señala Abelenky, es una compensación entre si tienes espacio para cuadrar números de bits.

Ciertamente, la manera más rápida es codificar todos los números de Fibonacci en su espacio de dominio. A lo largo de las líneas de otro punto que hace abelenky, solo hay 94 de estos retoños que son menos de 2 ^ 64.

Debería calcularlos previamente y ponerlos en un hash Perl, diccionario Python o lo que sea.

Las propiedades de los números de Fibonacci son muy interesantes, pero usarlas para determinar si un entero en un programa de computadora es uno es como escribir una subrutina para calcular pi cada vez que se inicia el programa.

Answer 7

El entero positivo ω es un número de Fibonacci

Si y solo si uno de 5ω ² + 4 y 5ω ² - 4 es un cuadrado perfecto

de The (Fabulous) FIBONACCI Numbers por Alfred Posamentier e Ingmar Lehmann

bool isFibonacci(int  w)
{
       double X1 = 5 * Math.Pow(w, 2) + 4;
       double X2 = 5 * Math.Pow(w, 2) - 4;

       long X1_sqrt = (long)Math.Sqrt(X1);
       long X2_sqrt = (long)Math.Sqrt(X2);   

       return (X1_sqrt*X1_sqrt == X1) || (X2_sqrt*X2_sqrt == X2) ;
}

Lo copié de esta fuente

Fragmento que imprime números de Fibonacci entre 1k y 10k .

for (int i = 1000; i < 10000; i++)
{
         if (isFibonacci(i))
              Console.Write(" "+i);
}

OMG ¡¡Solo hay CUATRO !!!

Con otro método

from math import *

phi = 1.61803399
sqrt5 = sqrt(5)

def F(n):
    return int((phi**n - (1-phi)**n) /sqrt5)

def isFibonacci(z):
    return F(int(floor(log(sqrt5*z,phi)+0.5))) == z

print [i for i in range(1000,10000) if isFibonacci(i)]

Answer 8

Esta es mi solución. No estoy seguro de si es un punto de referencia. ¡Espero que esto ayude!

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

qué a, b = b, a + b está haciendo

 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 9

Hacia una solución, eche un vistazo a la fórmula de Binet.
(Busque "Expresión de formulario cerrado" bajo Número de Fibonacci en Wikipedia)

Dice que la secuencia del número de Fibonacci se crea mediante una simple fórmula cerrada:

Creo que si resuelves n y pruebas si n es un entero, obtendrás tu respuesta.

Editar Como señala @psmears, el mismo artículo de Wikipedia también tiene una sección sobre detección de números de Fibonacci. Wikipedia es una excelente fuente.

Answer 10

La expresión general para un número de Fibonacci es F (n) = [[(1 + sqrt (5)) / 2] sup n + 1 - [(1-sqrt (5)) / 2] sup n + 1] / sqrt (5) ..... (*) El segundo exponencial va a cero para n grande y para llevar a cabo las operaciones numéricas obtenemos F (n) = [(1.618) sup n + 1] / 2.236

Si K es el número que se probará, el registro (k * 2.2336) / log (1.618) debe ser un número entero.

Ejemplo para K igual a 13 mi calculadora da la respuesta 7.00246 Para K igual a 14, la respuesta es 7.1564.

Puede aumentar la confianza en el resultado tomando el entero más cercano a la respuesta y sustituirlo por (*) para confirmar que el resultado es K

Answer 11

La solución Java se puede hacer de la siguiente manera. Pero aún así se puede optimizar

La siguiente solución funciona para

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

T es no. De casos de prueba, N es rango de número

    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 12

Mientras que varias personas señalan la solución de cuadrado perfecto, se trata de cuadrar un número de Fibonacci, lo que a menudo resulta en un producto masivo .

Hay menos de 80 números de Fibonacci que incluso pueden mantenerse en un entero estándar de 64 bits.

Aquí está mi solución, que opera completamente más pequeña que el número que se probará.
(escrito en C #, usando tipos básicos como double y long . Pero el algoritmo debería funcionar bien para tipos más grandes).

static bool IsFib(long T, out long idx) { double root5 = Math.Sqrt(5); double phi = (1 + root5) / 2; idx = (long)Math.Floor( Math.Log(T*root5) / Math.Log(phi) + 0.5 ); long u = (long)Math.Floor( Math.Pow(phi, idx)/root5 + 0.5); return (u == T); } Más de 4 años después de que escribí esta respuesta, un comentarista preguntó acerca del segundo parámetro, que pasó de out .

El parámetro # 2 es el "Índice" en la secuencia de Fibonacci.
Si el valor que se probará, T es un número de Fibonacci, entonces idx será el índice basado en 1 de ese número en la secuencia de Fibonacci. (con una notable excepción)

La secuencia de Fibonacci es 1 1 2 3 5 8 13 , etc.
3 es el 4º número en la secuencia: IsFib(3, out idx); devolverá true y valor 4 .
8 es el 6º número en la secuencia: IsFib(8, out idx); devolverá true y valor 6 .
13 es el 7 ° número; IsFib(13, out idx); devolverá true y valor 7 .

La única excepción es IsFib(1, out idx); , que devolverá 2 , aunque el valor 1 aparezca en los índices 1 y 2.

Si a IsFib se le pasa un número que no es de Fibonacci, devolverá false , y el valor de idx será el índice del número de Fibonacci más grande menor que T

16 no es un valor de Fibonacci.
IsFib(16, out idx); devolverá false y el valor 7 .
Puede usar la fórmula de Binet para convertir el índice 7 en el valor 13 de Fibonacci, que es el número más grande menor que 16.

Answer 13

Re: código de Ahmad - un enfoque más simple sin recursión o punteros, bastante ingenuo, pero requiere casi ningún poder computacional para nada menos que números realmente titánicos (aproximadamente 2N adiciones para verificar el número Nth fib, que en una máquina moderna tomará milisegundos lo peor)

// devuelve pos si encuentra algo, 0 si no lo hace (C / C ++ trata cualquier valor! = 0 como verdadero, por lo que el resultado final es el mismo)

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 14

Si sus números son de tamaño limitado, simplemente poner todos los números de Fibonacci por debajo del límite superior en una tabla hash y la contención de las pruebas hará el truco. Hay muy pocos números de fibonacci (por ejemplo, solo 38 por debajo de 5 mln), ya que crecen exponencialmente.

Si sus números no son de un tamaño limitado, entonces el truco sugerido con la prueba cuadrada será seguramente más lento que generar la secuencia de fibonacci hasta que se encuentre o exceda el número.

Answer 15

Un entero positivo ω es un número de Fibonacci si y solo si uno de 5ω ² + 4 y 5ω ² - 4 es un cuadrado perfecto.

Vea The Faboulous Fibonacci Numbers para más.

Answer 16

Una versión de 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 17

Una prueba muy buena es que N es un número de Fibonacci si y solo si 5 N^2 + 4 o 5N^2 – 4 es un número cuadrado. Para ideas sobre cómo probar eficientemente que un número es cuadrado, consulte la discusión de SO .

Espero que esto ayude

Answer 18

#!/bin/bash
victim="144"
curl http://aux.planetmath.org/files/objects/7680/fib.txt | sed ''s/^[0-9]*//;s/[ /t]//g'' | grep "^$victim$" >/dev/null 2>/dev/null
if [[ $? -eq 0 ]] ; then
    echo "$victim is a fibonacci number"
else
    echo "$victim aint"
fi

Answer 19

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

esto funcionara?

Answer 20

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

¿Qué tal esto?