Pseudo-Quellcode/Algorithmus/Rekursion |
| 22.04.2004, 15:56 | sonja1893 | Auf diesen Beitrag antworten » |
| Pseudo-Quellcode/Algorithmus/Rekursion Es geht um diesen Quellcode: BINARY SEARCH(A,a) 1 l <- 1 2 r <- n 3 k <- 0 4 while l < r do 5 k <- k+1 6 m <- 7 if A[m] a then l <- m 8 else r <- m-1 9 return A[l] = a Und die Aufgabe lautet: Der obenstehende Algorithmus bekommt als Eingabe ein sortiertes Feld (Array) A mit n Elementen. Es gilt also A[1] A[2] ... A[n]. Dabei sei n eine Zweierpotenz, d.h. n = 2^p, für ein p 0. Außerdem ist ein Wert a gegeben. Der Algorithmus soll herausfinden, ob a in A vorkommt. Die dabei verwendete Variable k wird eigentlich nicht benötigt. Sie ist nur zu Erklärungszwecken da. a) Kommt a nicht in A vor, dann ist BINARY SEARCH korrekt, da dies am Ende durch den Test in Zeile 9 sichergestellt wird. Nehmen wir im Folgenden also an, dass a in A vorkommt. Wir müssen zeigen, dass BINARY SEARCH dann a findet. Zeigen Sie dazu folgende Schleifenvariante in Zeile 4: r - l n/2^k und A[l] a A[r]. b) Algorithmus BINARY SEARCH vergleicht die Elemente von A mit a nur in Zeile 5 (abgesehen vom Schluss in Zeile 9). Mit V(n) bezeichnen wir die Anzahl der Vergleiche, die BINARY SEARCH während des gesamten Ablaufs in Zeile 5 macht. Begründen Sie, dass folgende Rekursionsgleichung für V(n) gilt: V(1) = 0 und V(n) = 1+V(n/2). Zeigen Sie durch Induktion, dass V(n)=log n die Lösung dieser Rekursionsgleichung ist. Also zu dieser Aufgabe fällt mir echt nur "hä?" ein. Ich hab keinen Plan, wie das gehen soll. Blickt einer von euch da vielleicht durch? |
||
| 22.04.2004, 16:54 | Poff | Auf diesen Beitrag antworten » |
| RE: Pseudo-Quellcode/Algorithmus/Rekursion Da ich zu faul bin mich in diesen 'Formalismus' hineinzudenken nur dies, vielleicht hilft dir das ja. Das Prinzip des Binary Search ist folgendes: Du teilst eine sortierte vorhandene Menge in zwei 'gleiche' Teile und prüfst in welcher das gesuchte sich befindet. Diejenige Teilmenge in der das gesuchte ist wird nun erneut geteilt und geprüft in welcher das gesuchte ist ... usw. In Folge triffst du nach recht wenigen Zugriffen auf das eigentlich gesuchte Element. Du musst dich nun nur fragen wie oft sich eine Ausgangsmenge A überhaupt teilen lässt und schon hast du die obere Abschätzung für die maximal möglichen Zugriffe überhaupt bei einer Suche. ... |
||
| 24.04.2004, 11:34 | sonja1893 | Auf diesen Beitrag antworten » |
| RE: Pseudo-Quellcode/Algorithmus/Rekursion Was ist denn eigentlich ein Array oder sortiertes Feld? |
||
| 24.04.2004, 12:34 | Thomas | Auf diesen Beitrag antworten » |
http://www.net-lexikon.de/Array.html Gruß, Thomas |
||
| 24.04.2004, 12:34 | Tonfilm | Auf diesen Beitrag antworten » |
array=feld (allgemein). um den binary search anwenden zu können brauchst du ein sortiertes feld (spezialfall von array), d.h. deine elemente im feld sind der grösse nach geordnet. funktioniert dann wie es poff geschrieben hat, du teilst das feld in der mitte und prüfst, ob das elemet das du suchst im 'oberen' oder 'unteren' teil liegt (indem du es mit dem 'mittleren' element vergleichst). das gleiche wird dann mit dem entsprechenden abschnitt des feldes nochmal gemacht usw. bis man das element gefunden hat oder auch nicht ... der such algorithmus hat ein sehr gutes laufzeitverhalten, da man wesentlich weniger schritte machen muss als es elemente im feld gibt, die komplexität ist O(log(n)). |
||
| 25.04.2004, 12:50 | sonja1893 | Auf diesen Beitrag antworten » |
Ok. Aber ich kapier immer noch nicht, was ich bei a) und b) genau machen soll. 
|
||
| Anzeige | ||
|
|
||
|
|
Verwandte Themen
| Die Beliebtesten » |
| Die Größten » |
|
| Die Neuesten » |
|
