Loesungen
Results 1 to 22 of 22

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

    SS 02 Loesungen

    Ich dachte ich waere spaet dran, mit den Loesungen, dabei ist ja naechste Woche gar keine Uebung.

    /edit 30.05.02:
    Aber durch meinen DM-Abgabetermin bin ich nun doch ziemlich weit zurueckgefallen. Die Loesungen sollten aber bis zum Wochenende komplett sein.

    - Beispiele 6, 8 und 10 wurden hinzugefuegt
    - Beispiel 7 wurde korrigiert
    - Beispiel 8 wurde korrigiert
    - Pseudocode fuer Beispiel 10 wurde vereinfacht

    seit 04.06.02, 17:11 ist die Version 1.0 online unter uebung.html
    Last edited by yrucrem; 13-10-2002 at 04:12.

  2. #2

    Title
    Dipl.Ing
    Join Date
    Mar 2002
    Location
    Wien 12
    Posts
    1,135
    Thanks
    72
    Thanked 366 Times in 208 Posts
    Ich versuche eigentlich das signal/noise Verhaeltnis meiner Posts auf einem ertraeglichen niveau zu halten, aber wenn ich den obigen Post nur geaendert haette, wuerde das keiner mitbekommen, darum dieser neue Beitrag.

    Die html-Datei die vorher dort stand gibt es nicht mehr. Inzwischen ist eine pdf-Datei mit den meisten Loesungen verfuegbar.

  3. #3
    DoomedOne
    zu 9:
    was passiert wenn die folge nur gleiche zahlen enthält?
    dann sollt der baum wieder unbalanciert sein oder seh ich das falsch?
    er wäre sogar eine lineare liste...

  4. #4
    eXe's Avatar
    Title
    Principal
    Join Date
    Feb 2002
    Posts
    99
    Thanks
    0
    Thanked 0 Times in 0 Posts
    @ yrucrem

    danke für deine lösungen ham mir sehr geholfen

    (gottseidank muß ich jetz keine mehr machen , weil ich winfler bin )

  5. #5

    Title
    Dipl.Ing
    Join Date
    Mar 2002
    Location
    Wien 12
    Posts
    1,135
    Thanks
    72
    Thanked 366 Times in 208 Posts
    @DoomedOne:
    Hmm, das stimmt. Aber andererseits steht in der Angabe, dass das normale Einfuegen() fuer natuerliche Suchbaeume verwendet werden soll (insbesondere kein AVL-Einfuegen) . Und da kann man irgendwie nicht verhindern, dass bei lauter gleichen Zahlen ein unbalancierter Baum herauskommt.

    Man koennte vielleicht nach dem zweiten rekursiven Aufruf von erstelle() so eine Art Balance-Uberpruefung vornehmen und gegebenenfalls rotieren, aber das kommt schon ziemlich nah an AVL.

    Ich denke die Angabe war schon so gemeint, dass man den Fall, dass nur gleiche Zahlen kommen, ignorieren kann (ich werde das jedenfalls tun ;-)).

  6. #6

    Title
    Elite
    Join Date
    Feb 2002
    Posts
    347
    Thanks
    3
    Thanked 15 Times in 11 Posts
    ich wollte mich auch nur für die lösungen bedanken...
    (soviel zum thema signal/noise ;-)

  7. #7
    DoomedOne
    jo glaub auch das man mit normalem einfügen keine besseren lösungen bekommen kann. Ich hab mir aber noch ein paar gedanken drüber gemacht und vielleicht gehts so:

    PHP Code:
    erstelle(lrfatherwo)
    {
     if ( 
    <= r)
     {
       
    floor((r) / 2);
       
    father einfügen(A[m], fatherwo);
       
    erstelle(l1fatherlinks);
       
    erstelle(1rfatherrechts);
      }
    }

    einfügen(xwherewo)
    {
     
    = new El(x);
     if (
    start == null
     {
      
    start t//wurzel
      
    return start;
     }

     if (
    where.key)
      
    where.left t;
     else if (
    where.key)
      
    where.right t;
     else
     {
      if (
    wo == links)
       
    where.left t;
      else
       
    where.right t;
      }
     return 
    t;

    aufruf mit; erstelle(0, n, null, links)
    P.s: das ist sicher nicht die optimale lösung

  8. #8
    VTEC's Avatar
    Title
    Baccalaureus
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    674
    Thanks
    0
    Thanked 1 Time in 1 Post

    Signal/Noise sinkt!!!

    @ DoomedOne: Dein Listing schaut im Dark-Style aus, als ob Du es tarnen wolltest , wenns markiert ist, gehts eh

    @yrucrem: Vielen Dank für Die Lösungen wieder, ich hab leider nicht so viel Zeit mich selbst eingehend damit zu beschäftigen, sodaß ich ohne Anleitung selbst die Lösung find.

    C YA
    HaRdCoRe HaS JuSt BeGuN!

  9. #9

    Title
    Hero
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    185
    Thanks
    0
    Thanked 0 Times in 0 Posts
    könnte das beispiel 10 so funktionieren?

    [edit] der algorithmus ist falsch
    PHP Code:
    Zusammenhang(s)
    initialisiere alle Knoten v € V mit markiert[v] = 0;
    für alle Knoten v € V
    {
         
    ZH(v)
    }
    für alle Knoten v€V
    {
         if (
    markiert[v] == 1)
               return 
    nicht_stark_zusammenhängend
    }
    return 
    stark_zusammenhängend


    ZH
    (v)
    für alle Knoten w € V
    {
          
    falls (es existiert keine Kante (w,voder es existiert keine Kante (v,w)
                
    markiert[v] = 1;

    Last edited by Lukas; 30-05-2002 at 15:12.

  10. #10

    Title
    Dipl.Ing
    Join Date
    Mar 2002
    Location
    Wien 12
    Posts
    1,135
    Thanks
    72
    Thanked 366 Times in 208 Posts
    @Lukas:
    Wenn ich das richtig verstehe, sagt dein Algorithmus, dass der Graph nicht stark zusammenhaengend ist, sobald er zwei Knoten findet, die nicht durch eine Kante verbunden sind.

    Ein Beispiel: V = {v, w, x, y}, E = {(v, x), (x, w), (w, y), (y, v)}. Deiser Graph, waere stark zusammenhaengend, obwohl es keine Kante (v, w) oder (w, v) gibt.

    Ich wuerde vorschlagen, bei jeden Knoten eine Traversierung zu starten und dabei die Knoten immer mit anderen Zahlen zu markieren. Nach jeder Traversierung muessen alle Knoten die selbe Markierung haben. Wenn nicht, heiszt das, dass dieser eine Knoten nicht erreicht werden konnte.

  11. #11

    Title
    Hero
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    185
    Thanks
    0
    Thanked 0 Times in 0 Posts
    ja stimmt. hab mich bei der definition von stark zusammenhängend irgendwie verlesen...

  12. #12
    DoomedOne
    zu 10:
    warum musst du imer in jedem knoten einen marker neu setzen?
    würde es nicht reichen zu zählen wie viele knoten gefunden wurde? also ne int variable global machen und immer wenn ein unbesuchter knoten auf besucht gesetzt wird die var um 1 zu erhöhen.
    wenn dann nach einem durchgang traversiere der zähler != gesamt-knotenanzahl -1 ist, ist es nicht stark zusammenhängend.

    außerdem kann man noch schauen ob von einem knoten überhaupt eine verbindung weg geht, wenn nicht kann es gar nicht stark zusammenhängend sein

  13. #13

    Title
    Dipl.Ing
    Join Date
    Mar 2002
    Location
    Wien 12
    Posts
    1,135
    Thanks
    72
    Thanked 366 Times in 208 Posts
    Ja stimmt eigentlich. An einen Zaehler hatte ich gar nicht gedacht (globale Variablen sind mir etwas unangenehm ;-)). Wie gesagt, die Idee ist einfach fuer jeden Knoten zu pruefen, ob man alle anderen Knoten erreichen kann, wie man das macht ist egal. Danke fuer den Hinweis, mit dem Zaehler ist es viel leichter zu pruefen, ob alle Knoten erreicht wurden. Leider ist es immer noch quadratisch ;-).

    Hat eigentlich jemand eine Idee, fuer Beispiel 8? Bei dem bin ich mir noch nicht sicher.
    Last edited by yrucrem; 03-06-2002 at 00:14.

  14. #14

    Title
    Veteran
    Join Date
    Feb 2002
    Posts
    21
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Bsp 3

    Hab ich da was falsch gemacht, oder funktioniert deine 2. Hashfunktion nicht so wie sie sollte?
    Beim Wert -311 bekomme ich mit deiner Funktion h2(k) = 5 - 311 mod 17 auf
    h2(k) = 0 !! (-306/17 = -18 und 0 Rest!)
    Und damit haben wir einen Teufelskreis...

    Wie kommst du für h2(k) auf 17?

  15. #15

    Title
    Dipl.Ing
    Join Date
    Mar 2002
    Location
    Wien 12
    Posts
    1,135
    Thanks
    72
    Thanked 366 Times in 208 Posts
    Punkt vor Strich! Modulo bindet staerker als Plus oder Minus.

  16. #16
    steve's Avatar
    Title
    Baccalaureus
    Join Date
    Jan 2002
    Location
    planet earth
    Posts
    539
    Thanks
    14
    Thanked 2 Times in 2 Posts
    zum thema 6
    würd ich sagen, dass er ganz eindeutig nicht stimmt (es sei denn, ich hab die angabe falsch verstanden).

    bsp 8:
    meiner meinung nach stimmt der algorithmus. er nimmt ja schließlich immer das "billigste" element, das den bedingungen entspricht. (hundertprozentig sicher bin ich mir nicht, aber mein hirn konnte bisher keinen gegenbeweis ausspucken...) gegenstimmen?
    Last edited by steve; 03-06-2002 at 16:02.
    -----BEGIN GEEK CODE BLOCK-----
    Version: 3.12
    GAT d-(+) s++: a- C++$>+$ U++>+++ P++>+++ L+++ !E W++>$ !N K? w(--)@ !O !M V? PS+ PE++(-)> Y+ PGP(+) t---(-) !5 X R- tv-(--) b++>$ DI+ D+(++) G(+) e>++++* h-- r++ y++
    ------END GEEK CODE BLOCK------ .

  17. #17
    dose's Avatar
    Title
    Dipl.Ing
    Join Date
    Feb 2002
    Location
    Meidllling
    Posts
    1,037
    Thanks
    1
    Thanked 0 Times in 0 Posts
    Ein paar Ergänzungen / Korrekturen für Blatt 5...

    ad 7: Nur der Vollständigkeit halber: Der Knoten g (25) wurde vergessen...ist zwischen f und b/p, ist aber nicht in der Lösung (Kreis zwischen 3, 4, 2, 8)

    ad 8: Hätte mir ursprünglich auch gedacht, daß der Algorithmus funktionieren könnte, heute in unserer Übungsstunde hatte jedoch jemand ein Beispiel gebracht, das das Gegenteil beweist - und auch die Tutorin überrascht hat Zu finden is eine "Skizze" auf http://www.dose-xp.org/algodat5_8.gif (nicht schlagen für die Ausführung, ich werd kein Medieninformatiker ) - für d(max)=2 z.B. würde der Algorithmus nicht die richtige Lösung liefern.

    ad 10:
    Meine Lösung beruht auf folgendem Prinzip: Da es zu jedem Knoten von jedem Knoten aus einen Weg geben soll (per Definition), müßte die erreichbare Knotenzahl von jedem Knoten (AnzahlKnoten - 1) sein, mit einem etwas modifizierten Tiefensuchealgorithmus (DFS_mod) läßt sich das leicht für jeden Knoten herausfinden, dann noch eine weitere Funktion rundherum (StarkZus), die das für alle Knoten "errechnet", vergleicht, und fertig ist das ganze. Die Laufzeit mag zwar nicht optimal sein, aber was solls...es müßte funktionieren (zumindest theoretisch sollte ich nicht allzu falsch liegen...)

    Code:
    DFS_mod(x);
    {
      markiere(x);
      push(x);
      pop(x);
      erreichbar=0;
      solange (x!=NULL)
      {
        y=naechster_unmarkierter_nachbar(x);
        falls (y!=NULL)
        {
          markiere(y);
          push(y);
          erreichbar++;
        }
        sonst
        {
          y=pop();
        }
        x=pop();
      }
      return(erreichbar);
    }
    
    StarkZus(V)
    {
      x=0;
      y=DFS_mod(V[x]);
      solange ((x==y) && (x<AnzahlKnoten))
      {
        x++;
        y=DFS_mod(V[x]);
      }
      falls (x==y)
      {
        return(wahr);
      }
      sonst
      {
        return(falsch);
      }
    }
    Last edited by dose; 03-06-2002 at 16:05.
    yast, SuSEconfig, apt-get and rpm - the 4 horsemen of the apocalypse

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

  18. #18
    steve's Avatar
    Title
    Baccalaureus
    Join Date
    Jan 2002
    Location
    planet earth
    Posts
    539
    Thanks
    14
    Thanked 2 Times in 2 Posts
    10-1-3-4-5 ist auf deiner skizze der richtige Stammbaum, oder?
    hast recht, ist verblüffend...
    -----BEGIN GEEK CODE BLOCK-----
    Version: 3.12
    GAT d-(+) s++: a- C++$>+$ U++>+++ P++>+++ L+++ !E W++>$ !N K? w(--)@ !O !M V? PS+ PE++(-)> Y+ PGP(+) t---(-) !5 X R- tv-(--) b++>$ DI+ D+(++) G(+) e>++++* h-- r++ y++
    ------END GEEK CODE BLOCK------ .

  19. #19
    dose's Avatar
    Title
    Dipl.Ing
    Join Date
    Feb 2002
    Location
    Meidllling
    Posts
    1,037
    Thanks
    1
    Thanked 0 Times in 0 Posts
    Ja, 10-1-3-4-5 wär die optimale Lösung, aber mit dem veränderten Kruskal kommt ma auf 1-2-4-5-100
    yast, SuSEconfig, apt-get and rpm - the 4 horsemen of the apocalypse

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

  20. #20
    steve's Avatar
    Title
    Baccalaureus
    Join Date
    Jan 2002
    Location
    planet earth
    Posts
    539
    Thanks
    14
    Thanked 2 Times in 2 Posts
    stimmt!
    den algorithmus fürs 10er hab ich wie folgt: einerseits wird in einer steuerfunktion für jeden knoten jedes knoten.markiert=false gesetzt und der counter=0.
    dann gibts einen DFS(knoten)-aufruf für eine DFS-suche mit mitlaufendem counter.
    counter wird returned an steuerfunktion. ist der counter zu klein ausgefallen, schreit er. :eek:
    -----BEGIN GEEK CODE BLOCK-----
    Version: 3.12
    GAT d-(+) s++: a- C++$>+$ U++>+++ P++>+++ L+++ !E W++>$ !N K? w(--)@ !O !M V? PS+ PE++(-)> Y+ PGP(+) t---(-) !5 X R- tv-(--) b++>$ DI+ D+(++) G(+) e>++++* h-- r++ y++
    ------END GEEK CODE BLOCK------ .

  21. #21

    Title
    Veteran
    Join Date
    May 2002
    Posts
    24
    Thanks
    0
    Thanked 0 Times in 0 Posts
    hat irgendwer schon die lösungen für das 6 und letzte ü-blatt??

  22. #22

    Title
    Dipl.Ing
    Join Date
    Mar 2002
    Location
    Wien 12
    Posts
    1,135
    Thanks
    72
    Thanked 366 Times in 208 Posts
    Sind in Arbeit. Wird vermutlich etwas knapp, wegen der DeathMatch-Pruefung.

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
  •