1) **Binärsuche**
public boolean binarySearch(int[] x, int value) {
int wert = (x.length-1)/2;
while(wert!= 0 && wert!= x.length-1) {
if(value == x[wert])
return true;
else if(value < x[wert])
wert /=2;
else
wert += wert/2;
if(wert==0 && x[0]==value
|| wert==x.length-1 && x[x.length-1]==value)
return true;
}
return false;
}
public static boolean binSuchRek(int[] x, int value) {
return binHelper(x,value,(x.length-1)/2);
}
public static boolean binHelper(int[] x, int value, int marker) {
if(marker ==0 && x[0]==value
|| marker==x.length-1 && x[x.length-1]==value)
return true;
if( marker == 0 || marker == x.length-1)
return false;
if(value == x[marker])
return true;
else if(value < x[marker])
return binHelper(x,value,marker/2);
else
return binHelper(x,value,marker + marker/2);
}
----
2) **Schleifeninvariante**
a)
F1: f = a! (logisch gedacht)
F2: f = n! / a! (f=a*n logisch ausgeschlossen und F2 != F1)
F1:
wp....
f*(a+1) = (a+1)!
f*(a+1) = (a+1)*a!
f = a!
q.e.d.
F2:
wp....
f*a = n! / (a-1)!
f*a = n! / ( a! / a)
f = n! /a!
q.e.d.
b) xxx
----
3)
Z1: private = nur public oder abstract edit: & Z.7 das selbe
Z8: float[] statt int
Z13: Rückgabewert der Funtkion nicht deklariert, int
Z13: } fehlt hinter geschwindigkeit;
Z17: extends -> implements
Z20: verdichtung ist nirgends deklariert worden
- edit: und methode muss public sein
Z25: private = public
Z27: holeLeistung() muss überschrieben werden
Z29: extends -> ,
Z31: : Doppelpunkt darf nicht sein!?
Z33: Rückgabewert int - returnt aber float
----
4a)
Balancierter binärer Suchbaum, bei dem für jeden Knoten die Höhe der beiden Teilbäume sich höchstens um 1 unterscheidet.
Aufwand:
Löschen, Suchen, Einfügen in O(log n)