Zahl auf Fibonaccizahl prüfen



  • Hallo zusammen,
    ich möchte ein Miniprogramm schreiben, dass eine Zahl, die per Parameter übergeben wird, überprüft, ob es sich um eine Fibonaccizahl handelt. Ich habe diesen Code:

    int fibRec(int num)
        {
          if(num<=2)
              return 1;
          return fibRec(num-1) + fibRec(num-2);
        }
    

    Diese Funktion gibt aber nur die "num"te Fibonaccizahl zurück. Natürlich könnte ich ein dynamisches Array mit allen Fibonaccizahlen füllen und dann die überprüfende Zahl mit jedem Elemt vergleichen. Aber es muss doch auch einfacher gehen. Könnt ihr mir helfen, wie ich den obigen Code abändern muss? Dabei muss die Funktion rekursiv bleiben. Die zu prüfende Zahl wird per Parameter übergeben.
    Vielen Dank
    Mr Fib



  • was hast du denn schon?



  • Ja, ich verstehe den geposteten Code, doch ich frage mich halt, ob ich das Problem nicht einfacer lösen kann. Ich bin aus der Arraygeschichte noch auf keine einfache und simple Lösung gekommen und suche daher jetzt nach Anregungen.

    Vielen Dank
    Mr Fib



  • hast du dir die aufgabe selber gestellt oder bekommen?
    falls bekommen: poste mal komplett...

    mir würde auch nur nen ansatz einfallen, der 2 fkt braucht...
    und keine der beiden sieht so aus, wie die, die du gepostet hast^^

    bb



  • Das Einzige, was mir einfällt, wäre: Du gehst alle Fibonacci-Zahlen hintereinander durch (dazu kannst du die Funktion benutzen, die ja rekursiv bleiben muss). Wenn das Ergebnis genau der eingegebenen Zahl entspricht, ist es ja eine Fibonacci-Zahl, wenn es größer ist, kannst du abbrechen, und es ist keine. So ersparst du dir wenigstens das mit dem Array.

    Es gibt aber bestimmt noch eine bessere, rechnerische Variante.


  • Mod

    Amgon schrieb:

    Es gibt aber bestimmt noch eine bessere, rechnerische Variante.

    Genauso ist es. In der englischen Wikipedia sind ein paar schöne Kriterien erklärt. Jetzt frage ich mich natürlich, warum der Threadersteller diese nicht kennt, wenn er so eine Aufgabe gestellt bekommt und man sich innerhalb weniger Minuten diese Kriterien anlesen kann.



  • template<typename T>
    T add(T a, T b)
    {
      return a + b;
    }
    
    bool is_fib(std::size_t val)
    {
      std::size_t fib_nr[2] = {1, 2};
      std::size_t i;
      for(i = 0; fib_nr[i] < val; i = ++i%2)
      {
        fib_nr[i] = add(fib_nr[0], fib_nr[1]);
      }
    
      return fib_nr[i] == val;
    }
    

    so sollte es glaube ich _in etwa_ gehen!?
    kannst dich ja noch ma melden, falls es so schon komplett richtig ist^^

    bb


Log in to reply