Déterminer si un nombre est un nombre de Fibonacci

J'ai besoin d'écrire du code Java qui vérifie si l'utilisateur d'inscription le nombre est dans la séquence de Fibonacci.

Je n'ai pas de problème de l'écriture de la suite de Fibonacci à la sortie, mais (probablement parce que ses tard dans la nuit) j'ai du mal à penser à la séquence de "si", c'est un nombre de Fibonacci. Je garde de départ et recommencer. Ses vraiment en train de faire ma tête.

Ce que j'ai actuellement est le n-ième.

public static void main(String[] args)
{
    ConsoleReader console = new ConsoleReader();

    System.out.println("Enter the value for your n: ");
    int num = (console.readInt());
    System.out.println("\nThe largest nth fibonacci: "+fib(num));
    System.out.println();
}

static int fib(int n){
    int f = 0;
    int g = 1;
    int largeNum = -1;
    for(int i = 0; i < n; i++)
    {
      if(i == (n-1))
          largeNum = f;
      System.out.print(f + " ");
      f = f + g;
      g = f - g;
    }
    return largeNum;
}

Qu'est-ce exactement que vous essayez de faire? obtenir le n-ième nombre de fibonacci? le nombre de fibonacci qui est plus grand que n? découvrez si n est un nombre de fibonacci?
Voir stackoverflow.com/questions/2432669/....
Wow, en regardant les commentaires, il y a beaucoup de discussion sur ce qui est la meilleure solution d'un point de vue algorithmique. Mais n'oubliez pas que c'est les devoirs, et à en juger par le code, ce n'est pas exactement un des algorithmes avancés de cours. Ce qui est probablement souhaité est le code plus facile à comprendre. @Emily, votre instructeur de vous donner le sens de la façon dont vous êtes censé résoudre ce problème?
Voir ici pour des réponses rapides à l'aide de seulement plus, moins et la multiplication: stackoverflow.com/questions/5162780

OriginalL'auteur Emily | 2010-06-29

fibonacci java

28

Lire la section intitulée "reconnaître les nombres de fibonacci" sur wikipedia.

Sinon, un entier positif z est un nombre de Fibonacci si et seulement si l'un des 5z^2 + 4 ou 5z^2 − 4 est un carré parfait.[17]

Alternativement, vous pouvez continuer à produire des nombres de fibonacci jusqu'à ce que l'on devient égal à votre nombre: si c'est le cas, votre numéro est un nombre de fibonacci, si ce n'est, le nombre finira par devenir plus grand que votre numéro, et vous pouvez arrêter. C'est assez inefficace.

Juste par curiosité, quelle ne ce nombre avant il est plus inefficace qu'une racine carrée de l'opération?
J - bonne question. La génération de la première n nombres de fibonacci est une O(n) temps de l'opération. L'extraction de la racine carrée de z est O(log z). Je suis enclin à dire que pour n assez grand pour les nombres de fibonacci à exiger de grands entiers, la racine carrée est plus rapide, mais je ne suis pas sûr.
les valeurs suivantes dans la séquence de Fibonacci approche très particulière ratio (Or). par conséquent, ils peuvent être grossièrement approchée en tant que ratio^le nombre d'étapes pour atteindre le nombre (avec certains des facteurs constants). c'est à dire log(z) ~ n log(phi) - qui indiquerait que le fait de prendre la racine carrée et simplement en comptant jusqu'sont assez proches. Cependant, je pense que l'avantage peut-être que l'on peut évaluer la non-entier-ness d'une racine carrée (c'est à la main en agitant, pas exactement) en moins de log(z).
La Nappe De La Méthode!!!
Vache sacrée bonne réponse! En tant que mathématiques majeur, je suis étonné que cela pourrait effectivement être vrai. Génial-o.

OriginalL'auteur IVlad

Si je comprends bien, ce que vous devez faire (au lieu d'écrire la première n nombres de Fibonacci) est de déterminer si n est un nombre de Fibonacci.

De sorte que vous devriez modifier votre méthode pour générer la séquence de Fibonacci jusqu'à ce que vous obtenez un certain nombre >= n. Si elle est égale, n est un nombre de Fibonacci, pas autrement.

Mise à jour: buggé par @Moron répétée de revendications au sujet de la formule de base de l'algorithme d'avoir une meilleure performance pour la simple ci-dessus, j'ai fait un test de comparaison concrètement entre Jacopo de la solution l'algorithme du générateur de et StevenH dernière version formule à base d'algorithme. Pour référence, voici le code exact:

public static void main(String[] args) {
measureExecutionTimeForGeneratorAlgorithm(1);
measureExecutionTimeForFormulaAlgorithm(1);
measureExecutionTimeForGeneratorAlgorithm(10);
measureExecutionTimeForFormulaAlgorithm(10);
measureExecutionTimeForGeneratorAlgorithm(100);
measureExecutionTimeForFormulaAlgorithm(100);
measureExecutionTimeForGeneratorAlgorithm(1000);
measureExecutionTimeForFormulaAlgorithm(1000);
measureExecutionTimeForGeneratorAlgorithm(10000);
measureExecutionTimeForFormulaAlgorithm(10000);
measureExecutionTimeForGeneratorAlgorithm(100000);
measureExecutionTimeForFormulaAlgorithm(100000);
measureExecutionTimeForGeneratorAlgorithm(1000000);
measureExecutionTimeForFormulaAlgorithm(1000000);
measureExecutionTimeForGeneratorAlgorithm(10000000);
measureExecutionTimeForFormulaAlgorithm(10000000);
measureExecutionTimeForGeneratorAlgorithm(100000000);
measureExecutionTimeForFormulaAlgorithm(100000000);
measureExecutionTimeForGeneratorAlgorithm(1000000000);
measureExecutionTimeForFormulaAlgorithm(1000000000);
measureExecutionTimeForGeneratorAlgorithm(2000000000);
measureExecutionTimeForFormulaAlgorithm(2000000000);
}
static void measureExecutionTimeForGeneratorAlgorithm(int x) {
final int count = 1000000;
final long start = System.nanoTime();
for (int i = 0; i < count; i++) {
isFibByGeneration(x);
}
final double elapsedTimeInSec = (System.nanoTime() - start) * 1.0e-9;
System.out.println("Running generator algorithm " + count + " times for " + x + " took " +elapsedTimeInSec + " seconds");
}
static void measureExecutionTimeForFormulaAlgorithm(int x) {
final int count = 1000000;
final long start = System.nanoTime();
for (int i = 0; i < count; i++) {
isFibByFormula(x);
}
final double elapsedTimeInSec = (System.nanoTime() - start) * 1.0e-9;
System.out.println("Running formula algorithm " + count + " times for " + x + " took " +elapsedTimeInSec + " seconds");
}
static boolean isFibByGeneration(int x) {
int a=0;
int b=1;
int f=1;
while (b < x){
f = a + b;
a = b;
b = f;
}
return x == f;
}
private static boolean isFibByFormula(int num) {
double first = 5 * Math.pow((num), 2) + 4;
double second = 5 * Math.pow((num), 2) - 4;
return isWholeNumber(Math.sqrt(first)) || isWholeNumber(Math.sqrt(second));
}
private static boolean isWholeNumber(double num) {
return num - Math.round(num) == 0;
}

Les résultats ont surpris même moi:

Running generator algorithm 1000000 times for 1 took 0.007173537000000001 seconds
Running formula algorithm 1000000 times for 1 took 0.223365539 seconds
Running generator algorithm 1000000 times for 10 took 0.017330694 seconds
Running formula algorithm 1000000 times for 10 took 0.279445852 seconds
Running generator algorithm 1000000 times for 100 took 0.030283179 seconds
Running formula algorithm 1000000 times for 100 took 0.27773557800000004 seconds
Running generator algorithm 1000000 times for 1000 took 0.041044322 seconds
Running formula algorithm 1000000 times for 1000 took 0.277931134 seconds
Running generator algorithm 1000000 times for 10000 took 0.051103143000000004 seconds
Running formula algorithm 1000000 times for 10000 took 0.276980175 seconds
Running generator algorithm 1000000 times for 100000 took 0.062019335 seconds
Running formula algorithm 1000000 times for 100000 took 0.276227007 seconds
Running generator algorithm 1000000 times for 1000000 took 0.07422898800000001 seconds
Running formula algorithm 1000000 times for 1000000 took 0.275485013 seconds
Running generator algorithm 1000000 times for 10000000 took 0.085803922 seconds
Running formula algorithm 1000000 times for 10000000 took 0.27701090500000003 seconds
Running generator algorithm 1000000 times for 100000000 took 0.09543419600000001 seconds
Running formula algorithm 1000000 times for 100000000 took 0.274908403 seconds
Running generator algorithm 1000000 times for 1000000000 took 0.10683704200000001 seconds
Running formula algorithm 1000000 times for 1000000000 took 0.27524084800000004 seconds
Running generator algorithm 1000000 times for 2000000000 took 0.13019867100000002 seconds
Running formula algorithm 1000000 times for 2000000000 took 0.274846384 seconds

En bref, l'algorithme du générateur de manière plus performante que la formule de la solution basée sur du positif valeurs int - même proche du maximum int valeur, il est deux fois plus rapide!
Tellement de conviction basée sur l'optimisation de la performance 😉

Pour l'enregistrement, la modification du code ci-dessus pour utiliser long des variables au lieu de int, le générateur de l'algorithme devient plus lent (comme prévu, puisqu'il a ajouter long valeurs d'aujourd'hui), et le basculement point où la formule commence à être plus rapide est d'environ 1000000000000L, c'est à dire 10¹².

Update2: Comme IVlad et Moron noté, je ne suis pas un expert dans les calculs en virgule flottante 🙂 en fonction de leurs suggestions, j'ai amélioré la formule:

private static boolean isFibByFormula(long num)
{
double power = (double)num * (double)num;
double first = 5 * power + 4;
double second = 5 * power - 4;
return isWholeNumber(Math.sqrt(first)) || isWholeNumber(Math.sqrt(second));
}

Ramené le passage point de env. 10⁸ (pour le long version - le générateur avec int est encore plus rapide pour toutes les valeurs int). Pas de doute que le remplacement de la sqrt appels avec quelque chose comme suggéré par @Débile de les pousser vers le bas, le passage point de plus.

Mon (et IVlad) point était simplement qu'il y aura toujours un point de basculement, en dessous de laquelle le générateur de l'algorithme est plus rapide. Si les revendications à propos de celui qui fonctionne mieux n'ont aucune signification en général, que dans un contexte.

c'est un naïf, mais travail approche. Rappelez-vous, c'est les devoirs, pas une critique pour les performances du système de production 🙂 Et même être optimal, en fonction du contexte (voir @IVlad du commentaire ci-dessus) - avez-vous réellement fait toute la mesure du rendement afin de voir dans quelles circonstances la formule indiquée dans Ivlad la réponse est plus performante que la génération de séquences? Si non, de quoi parlons-nous?
deux choses à ce sujet: "downvoting est parfois fait pour obtenir les bonnes réponses à la partie supérieure. Parfois, cela signifie downvoting tous, mais une seule réponse." 1) cela sonne étrangement proche de tactique downvoting 2) c'est d'un ridicule explication pour downvoting un réponse 1 score au moment de la réponse sommet a 12 😉 bien sûr, n'hésitez pas à downvote, je n'ai pas l'esprit les points perdus. Ce que j'ai l'esprit est fragile raisonnement.
point de downvoting est d'obtenir des réponses de qualité vers le haut" - IMO c'est le point de upvoting. Et si vous pensez que j'ai été ce qui implique IVlad était le downvoter, lire plus attentivement.
N'utilisez pas les Mathématiques.Sqrt ou les Mathématiques.Pow! 🙂 Utiliser les binaires de recherche pour déterminer si 5f^2 +- 4 est un carré parfait. Ou mieux encore, utiliser ceci: stackoverflow.com/questions/295579/...
+1 pour le fait de benchmarking au lieu de simplement deviner.

OriginalL'auteur Péter Török

6

Au lieu de passer l'index, n, écrire une fonction qui prend une limite, et d'obtenir pour générer les nombres de Fibonacci jusqu'à et y compris cette limite. Obtenir pour retourner un Booléen selon qu'il frappe ou saute au-dessus de la limite, et vous pouvez l'utiliser pour vérifier si cette valeur est dans la séquence.

Puisque c'est les devoirs, un coup de pouce comme c'est probablement tout ce que nous devrions être en vous donnant...

OriginalL'auteur David M

Ok. Puisque les gens j'ai dit que je suis juste de parler l'air mince ('faits' vs 'devine'), sans toutes les données à sauvegarder, j'ai écrit un test de mon propre.

Pas java, mais C# code ci-dessous.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace SO
{
class Program
{
static void Main(string[] args)
{
AssertIsFibSqrt(100000000);
MeasureSequential(1);
MeasureSqrt(1);
MeasureSequential(10);
MeasureSqrt(10);
MeasureSequential(50);
MeasureSqrt(50);
MeasureSequential(100);
MeasureSqrt(100);
MeasureSequential(100000);
MeasureSqrt(100000);
MeasureSequential(100000000);
MeasureSqrt(100000000);
}
static void MeasureSequential(long n)
{
int count = 1000000;
DateTime start = DateTime.Now;
for (int i = 0; i < count; i++)
{
IsFibSequential(n);
}
DateTime end = DateTime.Now;
TimeSpan duration = end - start;
Console.WriteLine("Sequential for input = " + n + 
" : " + duration.Ticks);
}
static void MeasureSqrt(long n)
{
int count = 1000000;
DateTime start = DateTime.Now;
for (int i = 0; i < count; i++)
{
IsFibSqrt(n);
}
DateTime end = DateTime.Now;
TimeSpan duration = end - start;
Console.WriteLine("Sqrt for input =  " + n + 
" : " + duration.Ticks);
}
static void AssertIsFibSqrt(long x)
{
Dictionary<long, bool> fibs = new Dictionary<long, bool>();
long a = 0;
long b = 1;
long f = 1;
while (b < x)
{
f = a + b;
a = b;
b = f;
fibs[a] = true;
fibs[b] = true;
}
for (long i = 1; i <= x; i++)
{
bool isFib = fibs.ContainsKey(i);
if (isFib && IsFibSqrt(i))
{
continue;
}
if (!isFib && !IsFibSqrt(i))
{
continue;
}
Console.WriteLine("Sqrt Fib test failed for: " + i);
}
}
static bool IsFibSequential(long x)
{
long a = 0;
long b = 1;
long f = 1;
while (b < x)
{
f = a + b;
a = b;
b = f;
}
return x == f;
}
static bool IsFibSqrt(long x)
{
long y = 5 * x * x + 4;
double doubleS = Math.Sqrt(y);
long s = (long)doubleS;
long sqr = s*s;
return (sqr == y || sqr == (y-8));
}
}
}

Et voici la sortie

Sequential for input = 1 : 110011
Sqrt for input =  1 : 670067
Sequential for input = 10 : 560056
Sqrt for input =  10 : 540054
Sequential for input = 50 : 610061
Sqrt for input =  50 : 540054
Sequential for input = 100 : 730073
Sqrt for input =  100 : 540054
Sequential for input = 100000 : 1490149
Sqrt for input =  100000 : 540054
Sequential for input = 100000000 : 2180218
Sqrt for input =  100000000 : 540054

La méthode sqrt bat la méthode naïve lorsque n=50, peut-être en raison de la présence de matériel de soutien sur ma machine. Même si elle était de 10^8 (comme dans l'épreuve de Pierre), il y a au plus 40 nombres de fibonacci en vertu de cette coupure, ce qui pourrait facilement être mis dans une table de recherche et de toujours battre la version naïve pour les plus petites valeurs.

Aussi, Peter a une mauvaise mise en œuvre de la SqrtVersion. Il n'a pas vraiment besoin de calculer deux racines carrées ou calculer des puissances de l'utilisation des Mathématiques.Pow. Il aurait au moins essayé de faire mieux avant la publication de ses résultats de référence.

De toute façon, je vais laisser les faits parler d'eux-mêmes, au lieu de la soi-disant 'devine'.

Très intelligent le point sur le nombre étonnamment petit de fib les nombres en dessous de la fréquence de coupure. Ce fil est sur le feu!

OriginalL'auteur

2

Un entier positif x est un nombre de Fibonacci si et seulement si l'un de 5x^2 + 4 et 5x^2 - 4 est un carré parfait

avez-vous une référence pour cette formule? c'est que même correct?
Reconnaître les nombres de Fibonacci: en.wikipedia.org/wiki/...

OriginalL'auteur Soufiane Hassou
2

Il y a un certain nombre de méthodes qui peuvent être utilisées pour déterminer si un nombre donné est dans la séquence de fibonacci, une sélection de ce qui peut être vu sur wikipedia.

Compte tenu de ce que vous avez fait déjà, cependant, je serais probablement utiliser plus de force brute approche, telle que la suivante:
1. Générer un nombre de fibonacci
2. Si c'est moins que le nombre de cibles, de générer de la prochaine fibonacci et répétez
3. Si c'est le numéro de la cible, alors le succès
4. Si c'est plus grand que le numéro de la cible, puis l'échec.
Je serais probablement utiliser une méthode récursive, en passant un courant n-valeur (ie. donc, il calcule le n-ième nombre de fibonacci) et le numéro de la cible.

OriginalL'auteur Edd

//Program begins
public class isANumberFibonacci {
public static int fibonacci(int seriesLength) {
if (seriesLength == 1 || seriesLength == 2) {
return 1;
} else {
return fibonacci(seriesLength - 1) + fibonacci(seriesLength - 2);
}
}
public static void main(String args[]) {
int number = 4101;
int i = 1;
while (i > 0) {
int fibnumber = fibonacci(i);
if (fibnumber != number) {
if (fibnumber > number) {
System.out.println("Not fib");
break;
} else {
i++;
}
} else {
System.out.println("The number is fibonacci");
break;
}
}
}
}
//Program ends

OriginalL'auteur Nithya

Si mon Java n'est pas trop rouillé...

static bool isFib(int x) {
int a=0;
int b=1;
int f=1;
while (b < x){
f = a + b;
a = b;
b = f;
}
return x == f;
}

OriginalL'auteur Iacopo

1

D'essayer d'utiliser le code que vous avez déjà écrit, je souhaiterais vous proposer la suite de la première, comme c'est la solution la plus simple (mais pas le plus efficace):
```
private static void main(string[] args)
{
//This will determnine which numbers between 1 & 100 are in the fibonacci series
//you can swop in code to read from console rather than 'i' being used from the for loop
for (int i = 0; i < 100; i++)
{
bool result = isFib(1);
if (result)
System.out.println(i + " is in the Fib series.");
System.out.println(result);
}
}
private static bool isFib(int num)
{
int counter = 0;
while (true)
{
if (fib(counter) < num)
{
counter++;
continue;
}
if (fib(counter) == num)
{
return true;
}
if (fib(counter) > num)
{
return false;
}
}
}
```
Je propose une solution plus élégante dans la génération de nombres de fibonacci, qui tire profit de la récursivité de la sorte:
```
public static long fib(int n) 
{
if (n <= 1) 
return n;
else 
return fib(n-1) + fib(n-2);
}
```
Pour le crédit supplémentaire de lecture: http://en.wikipedia.org/wiki/Fibonacci_number#Recognizing_Fibonacci_numbers

Vous allez voir qu'il y a quelques des moyens plus efficaces pour tester si un nombre est dans la Fibonacci de la série à savoir: (5z^2 + 4 ou 5z^2 − 4) = un carré parfait.
```
//(5z^2 + 4 or 5z^2 − 4) = a perfect square 
//perfect square = an integer that is the square of an integer
private static bool isFib(int num)
{
double first = 5 * Math.pow((num), 2) + 4;
double second = 5 * Math.pow((num), 2) - 4;
return isWholeNumber(Math.sqrt(first)) || isWholeNumber(Math.sqrt(second));
}
private static bool isWholeNumber(double num)
{
return num - Math.round(num) == 0;    
}
```
Comme indiqué par Péter Török dans une autre réponse à cette question, les tests pour un carré parfait est seulement pour suffisamment grand grand nombre (autour de e 1000000000000 et au-delà, dans ses points de repère). Bien sûr, il pourrait devenir plus rapide pour les faibles valeurs si vous remplacez la vérification pour savoir si un nombre est un carré parfait avec quelque chose de plus efficace.
N'en déplaise à Peter, mais sa mise en œuvre de sqrt vérifier suce et est pratiquement d'aucune utilité dans l'analyse comparative.
Je ne prétends pas le mien - c'était du copier-collé directement à partir d'ici 🙂
Je vois. Je m'excuse 🙂

OriginalL'auteur holsee
0

Je ne sais pas si il y a une formule que vous pouvez appliquer à l'entrée de l'utilisateur, cependant, vous pouvez générer la séquence de fibonacci et de la comparer à l'entrée de l'utilisateur jusqu'à ce qu'il est devenu plus petit que le dernier numéro est généré.
```
int userInput = n;
int a = 1, b = 1;
while (a < n) {
if (a == n)
return true;
int next = a + b;
b = a;
a = next;
}
return false;
```
OriginalL'auteur Chris J
0

Vous pouvez le faire de deux façons , la récursivité et les mathématiques.
la manière récursive
commencer à générer une séquence de fibonacci jusqu'à ce que vous frappez le nombre ou la passer
la manière mathématique joliment décrit ici ...
http://www.physicsforums.com/showthread.php?t=252798

bonne chance.

OriginalL'auteur Stas
0

Tenir compte de la séquence de nombres de Fibonacci 1,1,2,3,5,8,13,21, etc. Il est souhaitable de construire 3 piles chacune de capacité 10 contenant des numéros de séquences susmentionnées comme suit:

Pile 1: 10 Premiers numéros de la séquence.
Pile 2: les 10 Premiers nombres premiers à partir de la séquence.
Pile 3: 10 non-nombres premiers à partir de la séquence.

(i) Donner un algorithme de l'organigramme
(ii) Écrire un programme (en BASIC, C++ ou Java) pour mettre en œuvre cette.

De sortie:pile opérations que vous devrait s'afficher dans n'importe quelle forme les 3 piles avec les valeurs détenues en eux.

OriginalL'auteur Seidu Lukman Lutie

Constatation de l'existence d'un nombre de Fibonacci est basé sur la formule:

public static boolean isNumberFromFibonacciSequence(int num){
if (num == 0 || num == 1){
return true;
}
else {
//5n^2 - 4 OR 5n^2 + 4 should be perfect squares
return isPerfectSquare( 5*num*num - 4) || isPerfectSquare(5*num*num - 4);
}
}
private static boolean isPerfectSquare(int num){
double sqrt = Math.sqrt(num);
return sqrt * sqrt == num;
}

OriginalL'auteur realPK

Pensais que c'était simple jusqu'à ce que j'avais à rack de ma tête il y a quelques minutes. Son tout à fait différent de la génération d'une séquence de fibonacci. Cette fonction renvoie 1 si est Fibonnaci ou 0 si pas

public static int isFibonacci (int n){
int isFib = 0;
int a = 0, b = 0, c = a + b; //set up the initial values
do 
{
a = b;
b = c;
c = a + b;
if (c == n)
isFib = 1;
} while (c<=n && isFin == 0)
return isFib;
}
public static void main(String [] args){
System.out.println(isFibonacci(89));
}

OriginalL'auteur karto

Vous devez vous connecter pour publier un commentaire.