Class Loesung83

java.lang.Object
  Loesung83

public class Loesung83
extends Object

Loesungsvorschlag fuer Aufgabe 8-3. Fibonaccisuche.

Version:

$Revision: 1.5 $

Author:

Arne Johannessen

See Also:

Aufgabenblatt 8

Field Summary

static int[]

FIBONACCI Die Fibonaccifolge F, angepasst fuer die Fibonaccisuche.

Constructor Summary

Loesung83()

Method Summary

static int	find(int[] array, int key) Durchsucht einen Array mit der Fibonaccisuche.
protected static int	find(int[] array, int key, int leftIndex, int rightIndex, int fibonacciIndex) Durchsucht einen Array mit der Fibonaccisuche.
static void	main(String[] args) Treiber fuer Aufruf von der Kommandozeilenschnittstelle.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

FIBONACCI

public static final int[] FIBONACCI

Die Fibonaccifolge F, angepasst fuer die Fibonaccisuche. Diese Folge enthaelt alle Fibonaccizahlen in int; dies sind alle Fibonaccizahlen kleiner oder gleich F₄₆ = 1836311903.

Im Allgemeinen ist die Fibonaccifolge wie folgt definiert:
FIBONACCI[n] = (n == 0 ? 0 : (n == 1 ? 1 : (FIBONACCI[n - 2] + FIBONACCI[n - 1])))

Um klaren Code in der Rekursion zu haben, wird abweichend davon FIBONACCI[0] = 1 definiert; dies spart eine eigene if-Bedingung fuer sehr kurze Teil-Arrays ein. Auch wird FIBONACCI[47] = Integer.MAX_VALUE definiert, um die Korrektheit des Algorithmus auch bei langen Arrays herzustellen.

Constructor Detail

Loesung83

public Loesung83()

Method Detail

find

public static int find(int[] array,
                       int key)

Durchsucht einen Array mit der Fibonaccisuche. Zurueckgeliefert wird der Index einer Fundstelle.

Fuer eine Fibonaccisuche muss der Array sortiert sein.

Parameters:

array - das zu durchsuchende Array

key - den zu suchenden Wert

Returns:

den Index desjenigen Elements in array, das den Wert key hat

Throws:

KeyNotFoundException - falls der Array den gesuchten Wert nicht enthaelt

NullPointerException - falls array == null

See Also:

Arrays.sort(int[])

find

protected static int find(int[] array,
                          int key,
                          int leftIndex,
                          int rightIndex,
                          int fibonacciIndex)

Durchsucht einen Array mit der Fibonaccisuche. Zurueckgeliefert wird der Index einer Fundstelle.

Fuer eine Fibonaccisuche muss der Array sortiert sein.

Damit diese Methode korrekt ist, muessen beim Aufruf folgende Vorbedingungen erfuellt sein:

• array enthaelt den Suchraum, mit array.length > 0
• array.length > leftIndex >= 0
• rightIndex - leftIndex + 1 == FIBONACCI[fibonacciIndex]
• FIBONACCI enthaelt die Fibonaccifolge, mit FIBONACCI[0] == 1

Das Verhalten dieser Methode bei Nichterfuellung dieser Vorbedingungen ist nicht definiert.

Parameters:

array - das zu durchsuchende Array

key - den zu suchenden Wert

leftIndex - der Index, der die untere Grenze des zu durchsuchenden Bereichs im Array darstellt (einschliesslich)

rightIndex - der Index, der die obere Grenze des zu durchsuchenden Bereichs im Array darstellt (einschliesslich); der Abstand zu leftIndex muss in jedem Fall eine Fibonaccizahl sein

fibonacciIndex - der Index derjenigen Fibonaccizahl, die dem Abstand zwischen leftIndex und rightIndex entspricht

Returns:

den Index desjenigen Elements in array, das den Wert key hat

Throws:

KeyNotFoundException - falls der Array den gesuchten Wert nicht enthaelt

ArrayIndexOutOfBoundsException - falls array.length == 0

NullPointerException - falls array == null

See Also:

Arrays.sort(int[])

main

public static void main(String[] args)

Treiber fuer Aufruf von der Kommandozeilenschnittstelle.