Test si un nombre est fibonacci
je sais faire la liste des nombres de Fibonacci, mais je ne sais pas comment je peux tester si un nombre donné appartient à la liste de fibonacci - une façon qui vient à l'esprit est de générer la liste de fib. nombres jusqu'à ce nombre et voir si elle appartient au tableau, mais il doit y avoir une autre méthode, plus simple et plus rapide.
des idées ?
20 réponses
un très beau test est que N est un nombre Fibonacci si et seulement si 5 N^2 + 4 ou 5N^2 – 4 est un nombre carré. Pour des idées sur la façon de tester efficacement qu'un nombre est carré se référer à la so discussion .
Espérons que cette aide
Un entier positif ω est un nombre de Fibonacci si et seulement si l'un des 5ω 2 + 4 et 5ω 2 - 4 est un carré parfait.
Voir La Fabuleuse Nombres de Fibonacci pour plus d'.
alors que plusieurs personnes soulignent la solution parfaite-carré, il s'agit de la quadrature D'un nombre de Fibonacci, résultant souvent en un massive produit.
il y a moins de 80 nombres Fibonacci qui peuvent même être tenus dans un entier standard de 64 bits.
voici ma solution, qui fonctionne entièrement plus petit que le nombre à tester.
(écrit en C#, en utilisant types de base comme double et long . Mais l'algorithme devrait bien fonctionner pour les plus gros.)
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);
}
Plus de 4 ans après que j'ai écrit cette réponse, un commentateur a posé des questions sur le deuxième paramètre, passé par
out .
Paramètre #2 est l ' "Index" dans la séquence de Fibonacci.
Si la valeur à tester, T est un nombre Fibonacci, alors idx sera l'indice 1 de ce nombre dans la séquence de Fibonacci. (avec une exception notable)
la séquence de Fibonacci est 1 1 2 3 5 8 13 , etc.
3 est le 4e numéro dans la séquence: IsFib(3, out idx); retournera true et la valeur 4 .
8 est le 6ème numéro dans la séquence: IsFib(8, out idx); retournera true et la valeur 6 .
13 est le 7ème numéro; IsFib(13, out idx); sera retourner true et la valeur 7 .
La seule exception est IsFib(1, out idx); , qui sera de retour 2 , même si la valeur 1 s'affiche à la fois l'indice 1 et 2.
si IsFib est passé un nombre Non-Fibonacci, il retournera false , et la valeur de idx sera l'indice du plus grand nombre de Fibonacci moins que T .
16 n'est pas un Fibonacci valeur.
IsFib(16, out idx); retournera false et la valeur 7 .
Vous pouvez utiliser formule de Binet pour convertir l'indice 7 en Fibonacci valeur 13, qui est le plus grand nombre de moins de 16.
#!/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
si vos nombres sont de taille limitée, que simplement mettre tous les nombres fibonacci sous la limite supérieure dans un hashtable et le confinement de test fera l'affaire. Il y a très peu de nombres de fibonacci (par exemple, seulement 38 en dessous de 5mln), car ils croissent exponentiellement.
si vos nombres sont pas de taille limitée, alors l'astuce suggérée avec les tests carrés sera presque sûrement plus lent que la production de la séquence de fibonacci jusqu'à ce que le nombre est trouvé ou dépassé.
nombre entier positif ω est un nombre Fibonacci
si et seulement Si l'un des 5ω 2 + 4 et 5ω 2 - 4 est un carré parfait
à partir de Le (Fabuleux) Nombres de FIBONACCI par Alfred Posamentier et 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) ;
}
Snippet qui imprime des nombres Fibonacci entre 1k et 10k .
for (int i = 1000; i < 10000; i++)
{
if (isFibonacci(i))
Console.Write(" "+i);
}
OMG il n'y a que quatre !!!
avec une autre méthode
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)]
vers une solution, jetez un oeil à la formule de Binet.
(Cherchez " expression en forme fermée "sous numéro Fibonacci sur Wikipedia)
il est dit que la séquence du nombre de Fibonacci est créé par une formule fermée simple:
je crois que si vous résolvez pour n , et tester si n est un entier, vous aurez votre réponse.
Edit comme le souligne @psmears, le même article de Wikipedia comporte également une section sur la détection des numéros Fibonacci. Wikipédia est une excellente source.
voir la section" reconnaître les nombres de Fibonacci "sur le article de wikipedia sur les nombres de Fibonacci .
de Wikipedia: http://en.wikipedia.org/wiki/Fibonacci_number
un entier Z positif est un Fibonacci nombre si et seulement si l'un des 5z^2 + 4 ou 5z^2-4 est un carré parfait.
basé sur des réponses précédentes de moi et psmears, j'ai écrit ce code C#.
il passe par les étapes lentement, et il peut clairement être réduit et optimisé:
// 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;
}
}
test révèle que cela fonctionne pour les 69 premiers numéros Fibonacci, mais se décompose pour le 70e.
F(69) = 117,669,030,460,994 - Works
F(70) = 190,392,490,709,135 - Fails
en tout, sauf si vous utilisez une bibliothèque BigInt d'une sorte, il est probablement préférable d'avoir une table de recherche simple de la Fibonacci Numérotez et vérifiez cela, plutôt que d'exécuter un algorithme.
une liste des 300 premiers numéros est disponible en ligne.
mais ce code ne esquisse un algorithme réalisable, à condition que vous ayez assez de précision, et ne débordez pas votre système de représentation numérique.
Re: code D'Ahmad - une approche plus simple sans récursion ou pointeurs, assez naïve, mais nécessite à côté d'aucune puissance de calcul pour quoi que ce soit de moins de nombres vraiment titanic (environ 2N additions pour vérifier le nième nombre de fibrillation, qui sur une machine moderne prendra des millisecondes au pire)
/ / retourne pos s'il trouve quelque chose, 0 s'il ne le trouve pas (c/c++ traite n'importe quelle valeur != 0 comme vrai, donc même résultat final)
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;
}
l'expression générale pour un nombre de Fibonacci est F(n) = [ [(1+sqrt(5))/2] sup n+1 - [(1-sqrt(5))/2] sup n+1 ]/ sqrt(5) ..... (*) La deuxième exponentielle va à zéro pour le grand n et la réalisation de la opérations numériques on obtient F (n) = [(1.618) sup n+1 ] / 2.236
si K est le nombre à tester log (k * 2.2336) / log(1.618) doit être un entier!
exemple pour K égal à 13 ma calculatrice donne la réponse 7.00246 Pour K égal 14 la réponse est 7.1564.
Vous pouvez augmenter la confiance dans le résultat en prenant l'entier le plus proche de la répondez et remplacez en (*) pour confirmer que le résultat est K
Quelle est la taille des chiffres?
une table de recherche peut-elle fonctionner pour vous? (une liste précomputée de numéros que vous pouvez rechercher)
il y a aussi une expression en forme fermée que je suppose que vous pourriez Inverser pour obtenir la réponse analytiquement (bien que je ne suis pas un mathématicien, donc je ne peux pas promettre que cette suggestion a du sens)
j'ai couru quelques repères sur les méthodes présentées ici avec l'addition simple, pré-calculant un tableau, et la memoizing les résultats dans un hachage. Pour Perl, au moins, la méthode de la quadrature est un peu plus rapide que la méthode logarithmique, peut-être 20% plus rapide. Comme abelenky le souligne, il s'agit d'un compromis entre le fait que vous ayez la place pour les nombres binaires.
certainement, le moyen le plus rapide est de hachez tous les nombres de Fibonacci dans votre espace de domaine. Ainsi les lignes d'un autre point qu'abelenky fait, il n'y a que 94 de ces suceurs qui sont moins de 2^64.
vous devriez juste les pré-calculer, et les mettre dans un hachage Perl, dictionnaire de Python, ou n'importe quoi.
les propriétés des nombres de Fibonacci sont très intéressantes, mais les utiliser pour déterminer si un entier dans un programme informatique est un est un peu comme écrire un sous-programme pour calculer pi chaque fois que le programme commence.
C'est ma solution je ne suis pas sûr si elle benchmarks. J'espère que cela aide!
def is_fibonacci?(i)
a,b=0,1
until b >= i
a,b=b,a+b
return true if b == i
end
end
ce a,b=b,a+b est en train de faire
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
Un Scala version
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()
}
solution Java peut être fait comme ci-dessous. Mais il peut encore être optimisé
la solution suivante fonctionne pour
- 1≤T≤10 ^5
- 1≤N≤10 ^10
T n'est.des cas de test, N est la gamme de nombre
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;
}
}
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
}
}
et ça?
#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;
}
est-ce que ça va marcher?