View Full Version : Loesungen
Aufgabe 4 geht um vieles einfacher und uebersichtlicher (der Ansatz von vorher ist mir direkt peinlich ;-)).
Aenderungen seit v0.1:
- Aufgaben 5 und 6 hinzugefuegt.
- Aufgaben 7 bis 10 hinzugefuegt
- Erklaerungen zu den Aufgaben 3 bis 10 hinzugefuegt
- Aufgabe 8 korrigiert
- Tippfehler in Aufgabe 9 ausgebessert
- Pseudocode in Aufgabe 6 etwas vereinfacht (und korrigiert)
- Zu Aufgabe 7 wurde etwas mehr Kommentar hinzugefuegt
- Aufgabe 4 wurde vereinfacht
- Falsches mathematisches Zeichen in Aufgabe 7 wurde ausgebessert
seit 13.05.02, 11:09 ist die Version 1.0 online unter uebung.html (http://stud3.tuwien.ac.at/~e0125335/studium/algodat_1/uebung.html)
DancingComet
05-05-2002, 12:12
hab mir grade dein pdf angschaut... so nebenbei ich find das super von dir dass du die lösungen immer ins netz stellst... jetzt kapier ich endlich diese B-Bäume!! :cool:
naja jedenfalls hab ich beim bsp. 9 einen kleinen fehler gefunden:
in der zeile 8 sollte doch 21 und nicht 8 stehen oder? weil 8 gibts ja in der angabe gar nicht.
mfg
hallo yrucrem,
Danke sehr fuer deinen feinliche Arbeit wieder.
Ich glaube in bsp 6 braucht man nicht so viel vergleiche. Kann mann einfach das losen mit folgendes pseudo code.
Suche (p,x) {
h=NULL;
Solange (p!=NULL) {
Falls (x > p.key)
p=p.rightson
sonst
{ h=p ; p=p.leftson }
}
return h;
}
versuch mal!
@serseri:
Stimmt den einen Vergleich, ob das neu gefundene Element auch wirklich kleiner ist als eines das vorher gefunden wurde ist eigentlich ueberfluessig (ist ja eine Eigenschaft eines Suchbaums).
Aber statt dem "sonst ...", wuerde ich doch ein "sonst falls (x < p.key) ..." verwenden. Wenn es naemlich weder groeszer noch kleiner ist, dann muss es genau x sein und dann kann man die Suche sofort abbrechen (und sich unter umstaenden ein paar Ebenen des Baumes sparen).
Ich wuerde also aus meinem Pseudocode nur die Zeilen 11 und 12 streichen (die ja wirklich ueberfluessig sind). Das ist dann Deinem Code eh ziemlich aehnlich.
@yrucrem:
bei meinem Algorithm muss man jeden fall hilfzeiger h einsetzen. Weil ich retorniere das endlich.
Ich meine entweder gleich oder gross ist.
Wenn du einsetzt sonst fall mit "sonst falls (x < p.key) ...", dann h nicht ersetzt wenn x = p.key.
so retorniere NULL statt die key p, die gleichgross wie x.
Ich glaube das algorithm muss genau gleich bleiben, oder?
mlg,
@serseri:
Damit wollte ich nur sagen, dass ich auf jeden Fall alle drei Faelle pruefen wuerde (p.key < x; p.key > x und p.key == x), weil die Schleife unter umstaenden etwas frueher abgebrochen werden kann (sie wird zumindest auf keinen fall laenger).
Natuerlich, wenn du in deinem Code ein "sonst falls ..." benutzt, muss nach den beiden Abfragen ob groeszer oder kleiner auch der Fall behandelt werden, dass das x gleich dem gerade betrachteten Element ist. Und wenn dem so ist, kann man gleich einen Zeiger auf eben diesen Knoten zurueckgeben.
meriadoc
07-05-2002, 17:22
@yrucrem
ganz eine vorsichtige frage zu aufgabe 6:
wenn du einen baum hast und zB x=4 suchst, es aber keinen knoten 4 gibt, wird found retourniert, und found=NULL, oder?????
aber wenn x=4 dann musst man den nächst höheren knoten zurückgeben, das wäre dann 5 oder 6 oder...
je nach dem!
bitte sag mir, wenn ich komplett falsch liege!
thx
> wenn du einen baum hast und zB x=4 suchst, es
> aber keinen knoten 4 gibt, wird found retourniert,
> und found=NULL, oder?????
Nicht ganz. Wenn kein Knoten 4 existiert, aber Knoten mit groeszerem Schluessel, wird nicht NULL sondern der kleinste Knoten, der groeszer ist als 4, zurueckgegeben.
Wenn nur Elemente existieren, die kleiner sind als 4, wird NULL zurueckgegeben.
/edit 09.05.02:
meriadoc hatte recht. In meinem Pseudocode war ein kleiner Fehler (siehe die Nachfolgenden Posts) und deshalb wurde NULL zurueckgegeben, auch wenn Elemente Exisitieren die groeszer als x sind. Die obige Antwort trifft nur zu, wenn man den Code korrigiert.
Walter Huber
09-05-2002, 16:26
@yrucrem
bei beispiel 6 deiner lösung verstehe ich nicht ganz, wie found zum schluss auf das kleinste element das grösser ist als x zeigen kann, wenn du aus deinem alten code die "found = curr" rausgenommen hast. soweit ich das sehe wird found bei dir nie neu deklariert und bleibt somit in jedem fall null.
falls ich unrecht hab.
bitte erklärs mir.
@Walter Huber:
Danke fuer den Hinweis, ich habe etwas zu viel aus dem Pseudocode entfernt. Gleich unter "if (curr.key > x) {" kommt eigentlich "found = curr;". In der ersten Version Des Pseudocodes hatte ich davor noch eine if-Abfrage die aber nichts gebracht hat, und als ich die entfernt habe ist wohl etwas zu viel mitgegangen ;-)
@meriadoc:
Wenn deine Frage auch so gemeint war, dass found kein neuer wert zugewiesen wird, hattest du natuerlich recht. Tut mir leid, wenn ich hier fuer Verwirrung gesorgt habe.
(Ich habe meine obigen Posts (inkl. dem Ersten, der immer die wichtigsten Aenderungen der Loesung enthaelt (!)), korrigiert)
Walter Huber
10-05-2002, 14:19
@yrucrem
zu 6)
ich glaube das man die if zeile schon braucht, sonst überschreibt er so lange bis er aus dem baum herauskommt und gibt somit den letzten wert zurück anstatt des richtigen wertes. hier ist meine lösung:
1: found = NULL
2: solange p != NULL {
3: falls x > p.key dann {
4: p = p.rightson
5: }
6: falls x < p.key dann {
7: p = p.leftson
8: falls p > x dann {
9: found = p
10: }
11: }
12: }
13: retourniere found
ich denke das es so jetzt stimmt.
zu 1)
die eingabe müsste 123456789 und nicht wie du geschrieben hast 012345678 lauten damit er bei der suche nach 5 in eine endlosschleife kommt.
er vergleicht nicht m > x und m < x sondern A[m] > x und A[m] < x
damit m = A[m] ist muss A[1] = 1 sein und so weiter nicht 0 wie du geschrieben hast.
falls ich mich irre bitte ich um hilfe
funcollect
11-05-2002, 18:02
ZU BEISPIEL 3 --> 5 entfernen
wäre es nicht gescheiter einfach dend dreier statt den fünfer hinzuschreiben dadurch ist ja sind ja auch die bedingungen erfüllt? oder`?
denn es heisst: Geegnet sind der Knoten mit dem größten Schlüssel des linken Unterbaumes bzw. der Knoten mit dem kleisnten Schlüssel des rechten unterbaumes da sie z am ähnlichsten sind. Im Prinzip ist es gleich, für welche variante man sich enscheidet, weil beides wieder zu einem gültigen binären Suchbaum führt!
wäre doch auch eine lösung oder?
@Walter Huber:
ad 6)
Ich bin mir nicht sicher, was du mit quote: aus dem baum herauskommt /quote, meinst. Ich nehme an, du meinst sobald curr der NULL-Zeiger zugewiesen wird. Stimmt schon, found wird bis zum Schluss ueberschrieben und dieser Wert wird retourniert, aber das ist auch der Richtige (wegen der Eigenschaften eines Binaeren Suchbaums)!
Wenn "found" noch nichts zugeordnet wurde, heiszt das ja, dass man bis jetzt immer nur nach rechts gegangen ist. Wenn man jetzt ein curr.key findet, das groeszer ist als x, wird es "found" zugeordnet und man geht in den linken Unterbaum. Und das heiszt, dass alle Elemente die wir jetzt noch finden koennen, nur noch kleiner oder gleich dem sein koennen, auf das "found" gerade zeigt.
Dein Pseudocode kann uebrigens zwei Ebenen runter gehen, ohne zu ueberpruefen ,ob p nicht bereits auf den NULL-Zeiger verweist. Zum Beispiel bei diesem Baum: 1 ist die Wurzel, 4 ist deren rechtes Kind (ein linkes gibt es nicht). Das x sei 3. 1 ist kleiner als 3 also gehen wir nach rechts. 4 ist groeszer als 3 also, geht dein Algorithmus in den linken Teilbaum (der nicht existiert, p ist also NULL) und dann kommt noch ein Schluesselvergleich, obwohl p schon auf NULL zeigt.
ad 1)
Meine Eingabe funktioniert schon. A[1] ist naemlich gleich 1. Der Array-Index beginnt naemlich bei 0 zu zaehlen (A[0, ..., n - 1])!
@funcollect:
Natuerlich ist das auch eine Loesung. Wie gesagt, man kann entweder den Predeccessor oder den Successor nehmen. Ich habe mich fuer den Successor aus zwei Gruenden entschieden:
1. Wurde im Skriptum auch standartmaeszig der Successor benutzt.
2. Konnte ich so ein etwas komplexeres Beispiel beschreiben (und dadurch vielleicht ein paar Leuten die Baeume etwas verstaendlicher machen).
Sicherlich die einfachste Loesung waere den Dreier zu nehmen, aber dazu koennte man nicht mehr viel Erklaerung anbringen ;-)
PliniusSecundus
12-05-2002, 11:31
yrucrem: Probier einmal deinen Algorithmus Bsp 6 für den Baum (12,10,7,8) in dieser Reihenfolge eingefügt. Suche nach 9. Sollte eigentlich 10 ausgeben, gibt aber 8 aus, oder irre ich mich??
Walter Huber
12-05-2002, 11:34
genau das hab ich auch gemeint
jo stimmt, da ist noch ein kleiner fehler bei yucrem.
was haltet ihr davon:
Suchen(root, x)
__________________________________________________ __
p = root;
z = null;
if x < p {
if (p.left == null) || (p.left.key < x && p.left.right == NULL) return p;
else {
z = p;
Suchen(p.left, x);
}
}
if x > p {
if (p.right == null) return z;
else Suchen(p.right, x);
}
if (x == p) return p;
mfg, -z0nk-
Ich habe es mit diesem Baum probiert und es funktioniert. Wenn das Element, kleiner als x ist wird "found" KEIN neuer Wert zugewiesen (also kann gar nicht die 8 gefunden werden).
Fuer oben gennanten Baum laeuft der Algorithmus folgendermaszen ab:
- curr zeigt auf 12; 12 ist groeszer als 9, also found = curr = 12 und dann in den linken Unterbaum.
- curr zeigt auf 10; 10 ist groeszer als 9, also found = curr = 10 und dann in den linken Unterbaum.
- curr zeigt auf 7; 7 ist kleiner als 9, also gleich (und OHNE Zuweisung) in den rechten Unterbaum.
- curr zeigt auf 8; 8 ist kleiner als 9, also gleich (wieder OHNE Zuweisung) in den rechten Unterbaum.
- curr zeigt auf NULL und die while-Schleife bricht ab. "found" wird zurueckgegeben (und zeigt auf 10!).
/edit 12.05.02:
waerend ich das geschrieben habe, hat -z0nk- auch etwas gepostet. Die Aussagen in meinem Post beziehen sich auf die Fragen von PliniusSecundus und Walter Huber.
frage zu bsp 7
wieso muß ich nach dem einfügen von der 4 splitten?
check die b bäume irgendwie no net ganz ;)
naja ... cs verträgt sich halt net mit b-bäumen ;)
also der b-baum sollte ordnung 4 haben, dh ein knoten darf maximal 3 elemente und 4 kinder haben.
mfg,
-z0nk-
@alle die denken mein Code funktioniert nicht:
Wenn ich wirklich falsch liege, ist das ein wirklich hartnaeckiger Denkfehler. Ich hoffe Ihr verzeiht, wenn ich noch immer stur an meinem Algorithmus festhalte, denn ich denke, dass er wirklich funktioniert!
-zOnk-'s Algorithmus ist Meinem eigentlich recht aehnlich, nur das eben, _vor_ einem neuen Schleifendurchlauf (bei ihm eine Rekursion) ueberprueft wird, ob der naechste Knoten nicht schon NULL ist (bei mir geschieht das am Anfang der Schleife).
@eXe:
(1)Beim Einfuegen geht man die Elemente des Knotens von links nach rechts durch. Falls man ein Element findet dass groeszer ist als das einzufuegende bleibt man _davor_ stehen (wenn es keines gibt, das groeszer ist, bleibt man gezwungener Maszen "Ende" des Knotens stehen). Wenn an dieser Stelle eine Verzweigung zu einem Kind Existiert, geht man dort hinunter und beginnt wieder bei ->1. Gibt es kein Kind an dieser Stelle, fuegt man das Element genau an dieser Stelle ein.
Wie -zOnk- gesagt hat gibt eine Maximal Anzahl an Elementen die in einem Knoten sein duerfen, bei unserem Beispiel 3. Wenn wir also die 4 eingefuegt haben sieht der Knoten so aus: [1 2 3 4] und das ist zu groesz also muessen wir splitten.
an yrucrem:
Frage zu Bsp.2 : soll nicht jedes rechte Kind ein linkes Kind haben und umgekehrt???
sorry, hatte mich verlesen, passt schon ;)
@yucrem: hab mir jetzt einmal deinen algorithmus durchgelesen und mir die "found = curr;" zeile dazugedacht.
funktioniert glaub ich eh tadellos (is ja wirklich fast dasselbe, wie meiner). hab mir vorher nur das pdf file angeschaut und net checkt, dass da noch eine zeile dazugehört.
MfG, -z0nk-
Mein Vorschlag für Bsp. 6:
<pre>SMGT(p,s) {
x=NULL;
solange (p != NULL) && (p.key != s) {
falls s < p.key {
x=p; /* es existiert auf jeden Fall ein Element größer als s */
p=p.leftson;
}
sonst falls s > p.key {
p=p.rightson;
}
}
falls (s==p.key) {
return(p); /* s wurde gefunden */
}
sonst {
return(x); /* entweder minimales Element größer als s oder NULL zurückgeben */
}
}
</pre>
Anmerkung: Hatte zwei Zeilen vertauscht, danke an yrucrem für den Hinweis !
@ eXe: that's
RIGHT
:)
Und noch ne Frage zu Bsp. 7:
Im 3. Absatz steht: "Dabei wird das http://www.dose-xp.org/m2.gif-te Element (in Deutsch: das Element in der Mitte - wobei bei einer ungeraden Anzahl aufgerundet wird)"...
Heißt aber nicht dieses http://www.dose-xp.org/m2.gif, daß man ABrundet ?
Jope, das heisst abrunden!
Dürfte ein kleiner Fehler sein.
Jup...im Skript steht aber aufrunden, is also nur das falsche Zeichen...und jetzt, nachdem ich auch anscheinend die B-Bäume kapiert hab, kann ich voller Stolz sagen: ich komm auf dasselbe Ergebnis wie yrucrem !
So, jetzt fehlen mir nur mehr Bsp 8 und 9...also auf gehts, Hashing-Kapitel lesen und versuchen zu verstehen... ;)
Wings-of-Glory
16-05-2002, 05:17
yrucrem schreibt: (sinngemäß)
bei der folge: 0,1,2,3,4,5,6,7,8
wenn wir hier die '5' suchen wollen, kommen wir in eine endlosschleife ...
ich weiss nicht, ob es daran liegt, dass es so spät ist, aber ich bin den code per hand 'im
debug-modus' :D durchgegangen, und bei mir findet der algorithmus die '5'.
1: m=|_(n-1)/2_|;
2:wiederhole
3: falls A[m]>x dann {
4: m=|_m/2_|;
5: } sonst falls A[m]<x dann {
6: m=|_m+m/2_|;
7: } sonst {
8: return m;
9: }
10: bis (m<0) <FONT FACE=Symbol>Ú</FONT> (m>n-1)
11: return -1;
x=5; n=9;
1: m=|_(9-1)/2=4;
2:
3: falls A[m]>x dann { // A[4]>x --> 3>5 NEIN
5: sonst falls A[m]<x dann { // A[4]>x --> 3<5 JA
6: m=|_4+4/2_|=6
10: //endbedingung nicht erfüllt weiter bei 3
3: falls A[6]>x dann { // A[6]>x --> 5>5 NEIN
5: sonst falls A[m]<x dann { // A[6]>x --> 5<5 NEIN
7: sonst {
8: return m // m=6 --> 5 an der stelle m gefunden! abbruch der schleife!!
Liege ich da richtig? :rolleyes:
ich glaube yrucrem hat sich verschaut und den code so interpretiert
1:wiederhole
2: m=|_(n-1)/2_|;
3: falls A[m]>x dann {
4: m=|_m/2_|;
5: } sonst falls A[m]<x dann {
6: m=|_m+m/2_|;
7: } sonst {
8: return m;
9: }
10: bis (m<0) <FONT FACE=Symbol>Ú</FONT> (m>n-1)
11: return -1;
Nein das passt schon das is eine Endlosschleife...
- - - Begin Search - - -
Collection: 0 1 2 3 4 5 6 7 8, key 5
Checking position 4: 4
Checking position 6: 6
Checking position 3: 3
Checking position 4: 4
Checking position 6: 6
Checking position 3: 3
Checking position 4: 4
Checking position 6: 6
Checking position 3: 3
Checking position 4: 4
Search exceeded worst case runtime of linear search, probably endless loop
<strong>EDIT:</strong> ich glaub dein Denkfehler ist folgender: dieses Feld wird ab 0 nummeriert und nicht wie bei AlgoDat sonst üblich ab 1. In der Angabe steht: der als Eingabe ein Feld A[0,..., n - 1] usw.
Wen's interessiert hier noch mein Quellcode
/**
* Straightforward (stupid, hence the class name) binary search
* implementation of a homwork for the algorithms and data structures course
*/
public int doSearch(int key) {
int m = (int) (collection.length - 1) / 2;
int count = 0;
if (verbose) {
printStream.println(" - - - Begin Search - - -");
printStream.print(" Collection:");
print();
printStream.println(", key " + key);
}
do {
if (collection[m] > key) {
if (verbose)
printStream.println(" Checking position " + m + ": " + collection[m]);
m = (int) m / 2;
} else if (collection[m] < key) {
if (verbose)
printStream.println(" Checking position " + m + ": " + collection[m]);
m = (int) m + (m / 2);
} else {
if (verbose)
printStream.println(" Checking position " + m + ": "
+ collection[m] + ", returning");
return m;
}
if (++count > collection.length) {
if (verbose)
printStream.println(" Search exceeded worst case runtime of linear search, probably endless loop");
return -1;
}
} while (!(m < 0) || !(m > (collection.length - 1)));
return -1;
}
vBulletin® v3.7.1, Copyright ©2000-2009, Jelsoft Enterprises Ltd.