Fibonacci-Suche

[bmxfahrer]

Hallo ich muss einen Algorithmus für die Fibonacci-Suche schreiben. Meine Frage ist nun ob das Array nur jeweils so lang seien darf wie eine der Fibonaccizahlen groß ist, oder ist die Länge egal ?

Mfg Freddi

[smash]

Ich habe den Algorithmus weder gelernt noch implementiert. Aber es doch anscheinend darum eine der Fibonaccizahlen aus der Fibonacci-Reihe zu finden, richtig?

Die Reihe ist doch unendlich. Also musst du doch irgendwie die Anzahl einschränken. Von mir aus willkürlich N < 100 oder so. Geht das denn nicht aus der Aufgabe hervor?

Außerdem basiert doch die Fibonacci-Reihe auf der Beziehung, siehe Anhang. Das bedeutet ganz konkret, dass z.B. die vierte Zahl der Reihe = 2 ist. Also egal ob ich den index mit 0 oder 1 beginne ist der Index ungleich der Fibonaccizahl. Ausnahmen bestätigen die Regel und sind rein zufällig.

[lupo49]

Vor dem Durchlauf des Algorithmus könntest du abfragen, wie viele Fibonacci-Zahlen berechnet werden sollen. Das ist dann die Größe deines Arrays (Alternativ wäre eine Arraylist).

[bmxfahrer]

Ich hab mich wahrscheinlich ein bisschen falsch ausgedrückt... ich muss einen Algorithmus schreiben der ähnlich der Binären Suche, den Array nicht in der Mitte teilt, sondern den Array im Verhältnis der Fibonaccizahlen. Ich weiß jetzt nur nicht, ob der Array dann eine beliebig lange Länge haben darf, oder einer der Fibonaccizahlen entsprechen muss, um ihn dann in weitere kleinere Bereiche aufteilen zu können.

[smash]

Wie gesagt, ich habe den Algorithmus nicht gelernt, aber wenn ich dich und das was ich kurz gegoogelt habe richtig verstehe, ist der einzige Unterschied zwischen der binären Suche und der Fibonnacisuche, dass der Array an unterschiedlichen Stellen geteilt wird.

Ich behaupte einfach mal, das du also jedes Teil-Array mit N > 1 teilen kannst und müsstest. Ich meine wäre die Alternative, wenn du zu diesem Zeitpunkt das richtige Element noch nicht gefunden hast.

Vielleicht solltest du dir mal Binärbäume und Suchbäume anschauen.

Außerdem würde ich den Array nicht wirklich in Teile zerlegen oder neue Arrays erzeugen. Stattdessen würde ich mehrere Variablen für die Begrenzung des Teilbereichs benutzen in dem gerade gesucht wird. Z.B:

int top;

int bottom;

int current;

Bearbeitet 15. Mai 2010 von smash

[Newling]

Ich weiß natürlich, dass ich mich viel zu spät melde, um noch helfen zu können. Aber da hier noch keine richtige Antwort zur Lösung des Problems gegeben wurde, und die Lösung evtl. immer noch interessant ist, hier mein Hinweis.

Eine Erklärung und ein einfacher Algorithmus dazu ist zu finden in einem Artikel über Ein- und mehrdimensionale Fibonacci Suche von Klaus-E. Schulz