Loesungen
Results 1 to 29 of 29

Thread: Loesungen

  1. #1

    Title
    Dipl.Ing
    Join Date
    Mar 2002
    Location
    Wien 12
    Posts
    1,135
    Thanks
    72
    Thanked 366 Times in 208 Posts

    Post SS 02 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
    Last edited by yrucrem; 13-10-2002 at 04:11.

  2. #2
    DancingComet's Avatar
    Title
    Master
    Join Date
    Mar 2002
    Location
    wien 3
    Posts
    140
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Arrow kleiner Fehler

    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!!

    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
    Last edited by DancingComet; 05-05-2002 at 12:15.

  3. #3

    Title
    Veteran
    Join Date
    May 2002
    Location
    Wien
    Posts
    2
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Arrow

    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!

  4. #4

    Title
    Dipl.Ing
    Join Date
    Mar 2002
    Location
    Wien 12
    Posts
    1,135
    Thanks
    72
    Thanked 366 Times in 208 Posts
    @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.
    Last edited by yrucrem; 05-05-2002 at 23:44.

  5. #5

    Title
    Veteran
    Join Date
    May 2002
    Location
    Wien
    Posts
    2
    Thanks
    0
    Thanked 0 Times in 0 Posts
    @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,

  6. #6

    Title
    Dipl.Ing
    Join Date
    Mar 2002
    Location
    Wien 12
    Posts
    1,135
    Thanks
    72
    Thanked 366 Times in 208 Posts
    @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.

  7. #7

    Title
    Principal
    Join Date
    Feb 2002
    Posts
    27
    Thanks
    0
    Thanked 0 Times in 0 Posts
    @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

  8. #8

    Title
    Dipl.Ing
    Join Date
    Mar 2002
    Location
    Wien 12
    Posts
    1,135
    Thanks
    72
    Thanked 366 Times in 208 Posts
    > 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.
    Last edited by yrucrem; 09-05-2002 at 18:01.

  9. #9
    Walter Huber's Avatar
    Title
    Elite
    Join Date
    May 2002
    Posts
    387
    Thanks
    11
    Thanked 5 Times in 3 Posts

    Unhappy

    @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.

  10. #10

    Title
    Dipl.Ing
    Join Date
    Mar 2002
    Location
    Wien 12
    Posts
    1,135
    Thanks
    72
    Thanked 366 Times in 208 Posts
    @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)
    Last edited by yrucrem; 09-05-2002 at 18:04.

  11. #11
    Walter Huber's Avatar
    Title
    Elite
    Join Date
    May 2002
    Posts
    387
    Thanks
    11
    Thanked 5 Times in 3 Posts
    @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

  12. #12

    Title
    Principal
    Join Date
    Apr 2002
    Posts
    60
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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?

  13. #13

    Title
    Dipl.Ing
    Join Date
    Mar 2002
    Location
    Wien 12
    Posts
    1,135
    Thanks
    72
    Thanked 366 Times in 208 Posts
    @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 ;-)

  14. #14

    Title
    Principal
    Join Date
    Feb 2002
    Posts
    57
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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??

  15. #15
    Walter Huber's Avatar
    Title
    Elite
    Join Date
    May 2002
    Posts
    387
    Thanks
    11
    Thanked 5 Times in 3 Posts
    genau das hab ich auch gemeint

  16. #16
    -z0nk-'s Avatar
    Title
    Master
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    169
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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-

  17. #17

    Title
    Dipl.Ing
    Join Date
    Mar 2002
    Location
    Wien 12
    Posts
    1,135
    Thanks
    72
    Thanked 366 Times in 208 Posts
    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.
    Last edited by yrucrem; 12-05-2002 at 23:45.

  18. #18
    eXe's Avatar
    Title
    Principal
    Join Date
    Feb 2002
    Posts
    99
    Thanks
    0
    Thanked 0 Times in 0 Posts
    frage zu bsp 7
    wieso muß ich nach dem einfügen von der 4 splitten?

    check die b bäume irgendwie no net ganz

  19. #19
    -z0nk-'s Avatar
    Title
    Master
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    169
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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-
    zonked [zpnkt] - if someone is zonked or zonked out, they are not capable of doing anything because they are tired, drunk, or drugged; an informal word.

  20. #20

    Title
    Dipl.Ing
    Join Date
    Mar 2002
    Location
    Wien 12
    Posts
    1,135
    Thanks
    72
    Thanked 366 Times in 208 Posts
    @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.
    Last edited by yrucrem; 12-05-2002 at 23:43.

  21. #21
    Sam's Avatar
    Title
    Elite
    Join Date
    Feb 2002
    Posts
    263
    Thanks
    22
    Thanked 6 Times in 6 Posts
    an yrucrem:

    Frage zu Bsp.2 : soll nicht jedes rechte Kind ein linkes Kind haben und umgekehrt???

    sorry, hatte mich verlesen, passt schon

  22. #22
    -z0nk-'s Avatar
    Title
    Master
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    169
    Thanks
    0
    Thanked 0 Times in 0 Posts
    @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-
    zonked [zpnkt] - if someone is zonked or zonked out, they are not capable of doing anything because they are tired, drunk, or drugged; an informal word.

  23. #23
    dose's Avatar
    Title
    Dipl.Ing
    Join Date
    Feb 2002
    Location
    Meidllling
    Posts
    1,037
    Thanks
    1
    Thanked 0 Times in 0 Posts
    Mein Vorschlag für Bsp. 6:
    <pre>SMGT(p,s) {
    x=NULL;
    solange (p != NULL) && (p.key != s) {
    falls s &lt; p.key {
    x=p; /* es existiert auf jeden Fall ein Element größer als s */
    p=p.leftson;
    }
    sonst falls s &gt; 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 !
    Last edited by dose; 12-05-2002 at 23:54.
    yast, SuSEconfig, apt-get and rpm - the 4 horsemen of the apocalypse

    Platform of insanity :: www.dose-xp.org

  24. #24
    eXe's Avatar
    Title
    Principal
    Join Date
    Feb 2002
    Posts
    99
    Thanks
    0
    Thanked 0 Times in 0 Posts
    huch ]I[dose?

  25. #25
    dose's Avatar
    Title
    Dipl.Ing
    Join Date
    Feb 2002
    Location
    Meidllling
    Posts
    1,037
    Thanks
    1
    Thanked 0 Times in 0 Posts
    @ eXe: that's
    RIGHT


    Und noch ne Frage zu Bsp. 7:
    Im 3. Absatz steht: "Dabei wird das -te Element (in Deutsch: das Element in der Mitte - wobei bei einer ungeraden Anzahl aufgerundet wird)"...
    Heißt aber nicht dieses , daß man ABrundet ?
    Last edited by dose; 13-05-2002 at 00:13.
    yast, SuSEconfig, apt-get and rpm - the 4 horsemen of the apocalypse

    Platform of insanity :: www.dose-xp.org

  26. #26
    AntiBit's Avatar
    Title
    Super Moderator
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    738
    Thanks
    0
    Thanked 6 Times in 3 Posts
    Jope, das heisst abrunden!
    Dürfte ein kleiner Fehler sein.
    Hätten uns Spiele wie Pac-Man in unserer Jugend beeinflusst, würden wir heute durch dunkle Räume irren, elektronische Musik hören und Pillen fressen.

  27. #27
    dose's Avatar
    Title
    Dipl.Ing
    Join Date
    Feb 2002
    Location
    Meidllling
    Posts
    1,037
    Thanks
    1
    Thanked 0 Times in 0 Posts
    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...
    yast, SuSEconfig, apt-get and rpm - the 4 horsemen of the apocalypse

    Platform of insanity :: www.dose-xp.org

  28. #28
    Wings-of-Glory's Avatar
    Title
    CO-Administrator
    Join Date
    Jan 2002
    Posts
    3,989
    Thanks
    338
    Thanked 498 Times in 262 Posts
    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' durchgegangen, und bei mir findet der algorithmus die '5'.

    Code:
    1: m=|_(n-1)/2_|;
    2:wiederhole
    3: falls A[m]&gt;x dann {
    4:      m=|_m/2_|;
    5:  } sonst falls A[m]&lt;x dann {
    6:      m=|_m+m/2_|;
    7:   } sonst {
    8:        return m;
    9:    }
    10: bis (m&lt;0) <FONT FACE=Symbol>&#218;</FONT> (m&gt;n-1)
    11: return -1;
    Code:
    x=5; n=9;
    1: m=|_(9-1)/2=4;
    2:
    3: falls A[m]&gt;x dann { // A[4]&gt;x --&gt; 3&gt;5 NEIN
    5: sonst falls A[m]&lt;x dann { // A[4]&gt;x --&gt; 3&lt;5 JA
    6: m=|_4+4/2_|=6
    10: //endbedingung nicht erfüllt weiter bei 3
    3: falls A[6]&gt;x dann { // A[6]&gt;x --&gt; 5&gt;5 NEIN
    5: sonst falls A[m]&lt;x dann { // A[6]&gt;x --&gt; 5&lt;5 NEIN
    7: sonst {
    8: return m // m=6 --&gt; 5 an der stelle m gefunden! abbruch der schleife!!
    Liege ich da richtig?
    ich glaube yrucrem hat sich verschaut und den code so interpretiert
    Code:
    1:wiederhole
    2: m=|_(n-1)/2_|;
    3: falls A[m]&gt;x dann {
    4:      m=|_m/2_|;
    5:  } sonst falls A[m]&lt;x dann {
    6:      m=|_m+m/2_|;
    7:   } sonst {
    8:        return m;
    9:    }
    10: bis (m&lt;0) <FONT FACE=Symbol>&#218;</FONT> (m&gt;n-1)
    11: return -1;
    Otto: Apes don't read philosophy. - Wanda: Yes they do, Otto, they just don't understand
    Beleidigungen sind Argumente jener, die über keine Argumente verfügen.
    «Signanz braucht keine Worte.» | «Signanz gibts nur im Traum.»


    Das neue MTB-Projekt (PO, Wiki, Mitschriften, Ausarbeitungen, Folien, ...) ist online
    http://mtb-projekt.at

  29. #29

    Title
    Elite
    Join Date
    Dec 2001
    Posts
    340
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Nein das passt schon das is eine Endlosschleife...
    &nbsp;&nbsp;&nbsp;- - - Begin Search - - -
    &nbsp;&nbsp;Collection: 0 1 2 3 4 5 6 7 8, key 5
    &nbsp;&nbsp;Checking position 4: 4
    &nbsp;&nbsp;Checking position 6: 6
    &nbsp;&nbsp;Checking position 3: 3
    &nbsp;&nbsp;Checking position 4: 4
    &nbsp;&nbsp;Checking position 6: 6
    &nbsp;&nbsp;Checking position 3: 3
    &nbsp;&nbsp;Checking position 4: 4
    &nbsp;&nbsp;Checking position 6: 6
    &nbsp;&nbsp;Checking position 3: 3
    &nbsp;&nbsp;Checking position 4: 4
    &nbsp;&nbsp;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
    PHP Code:
        /**
         * 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 " ": " collection[m]);
                    
    = (int) 2;
                } else if (
    collection[m] < key) {
                    if (
    verbose)
                        
    printStream.println(" Checking position " ": " collection[m]);
                    
    = (int) + (2);
                } else {
                    if (
    verbose)
                        
    printStream.println(" Checking position " ": "
                                            
    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 (!(
    0) || !(> (collection.length 1)));
            return -
    1;
        } 
    Last edited by martin; 16-05-2002 at 12:44.
    I invented ctrl-alt-del but Bill [Gates] made it famous
    Dave Bradly, IBM PC designer

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •