Quicksort und Rekursiv: Türme von Hanoi

[Hoschio]

Hallo !

ich check das mit der rekursivität nicht !

Also jedenfalls nicht an diesem Beispiel:

public class Test
{   public static void main (String args[])
    {   hanoi(4,1,2,3); // bewege 4 Scheiben von 0 nach 1
    }

    static void hanoi (int n, int from, int to, int using)
    // Bewegt n Scheiben von from nach to, wobei using frei ist.
    {   if (n==1)
        {   System.out.println("Move disk from "+from+" to "+to);
        }
        else
        {   hanoi(n-1,from,using,to);
            System.out.println("Move disk from "+from+" to "+to);
            hanoi(n-1,using,to,from);
        }
    }
}

das quicksort problem füg ich gleich hinzu[/code][/quote]

 

[hoschiiiiiiiii]

also hab was vergessen:

das problem sieht wie fiolgt aus

x
xx
xxx
xxxx

Stapel 0 Stapel 1 Stapel 2

Nicht wundern 1+2 sind ja leer.

Das prog bewegt die 4 scheiben von 0 nach 1.

die anderen stapel dürfen genutzt werden.

nur darf ein grössere block nie auf einen kleineneren gelegt werden

sprich der mit 4 x'en hier darf nicht auf 3 x'e oder 2 oder 1 gelegt werden.


das sin die spielregeln !!!!!!!!1


Also versucht das mal anfängergerecht zu erklären :bae:

ich dank im voraus

 

[thE_29]

am besten du nimmst einen Zettel + Bleistift zur Hand startest dein Programm und debugst alles schön durch!

so wirst du sehen was er genau sortiert und so weiß du dann auch 100%ig (naja ungefähr) wie der sort funktioniert!

rekursiv is immer gemein, aber super

 

[Reality]

Wieso wird bei der Rekursion jedes Mal die Variblen vertauscht?! Wenn ich das compiliere, kommt bei mir nur Mist raus. Von sotieren ist das nichts zu sehen...

Liebe Grüße
Reality

 

[Isaac]

Kennst du die Türme von Hanoi? Ein kleinerer Ring darf nie auf einem grösseren Ring liegen.

Wenn du 3 Türme hast und 3 Ringe:

1 -> 2 (kleiner Ring von links in die Mitte)
1 -> 3 (mittlerer Ring von links nach rechts)
2 -> 3 (kleiner Ring auf den mittleren Ring)
1 -> 2 (grosser Ring von links in die Mitte)
3 -> 2 (kleiner Ring von rechts in die Mitte)
3 -> 1 (mittlerer Ring von rechts nach links)
2 -> 1 (kleiner Ring von der mitte nach links)
2 -> 3 (grosser Ring von der mitte nach rechts)
1 -> 2 (kleiner Ring von links in die Mitte)
1 -> 3 (mittlerer Ring von links nach rechts auf den grossen Ring)
2 -> 3 (und den kleinen auf den mittleren und den grossen

 

[Anubis]

Um die Rekursion zu verstehen, muss man erstmal die Rekursion verstehen 8)

Die Türme sind ein schwieriges Beispiel um die Rekursion zu verstehen. Viel einfacher wäre Fakultet:

2! = 1*2 (sprich 2 fakultät gleich 1 mal 2)
3! = 1*2*3
7! = 1*2*3*4*5*6*7
oder rekursiv: (Rekursiv: "sich selbs aufrufend")
7! = 6!*7
6! = 5!*6

Oder Allgeimein:
n! = (n-1)!*n | für: n > 1
1! = 1
0! = 1
für n < 0 ist die Fakultätsfunktion nicht definiert

Dazu eine Methode:

public int fakul (int n) {
// berechnet n!
  if (n > 1) return fakul(n-1) * n;
  if (n < 2) return 1;
}

Die Methode erhählt einen Parameter n und gibt, fall n > 1 ist das Produnkt aus (n-1)! und n zurück und benutz zur Berechnung sich selbst mit dem parameter (n-1).

Für n < 2 (n <= 1) wird 1 zurückgeben.

 

[Hoschi49]

jo das mit der fakultät hab ich schon verstanden

die türme machen mnir aber zu schaffen :autsch:

 

[Anubis]

Das ist auch schenll gelöst:

Grundlösung:
1. Du schiebst alles, bis auf den untersten auf die Reserve
2. Du schiebst den Untersten auf Ziel
3. du schiebst den Reservestapel aufs Ziel

Wie mache ich 1. ?
du betrachtest 1. als einzelne Aufgabe, benutz aber das Ziel als Reserve und die Reserve als Ziel

Das geht so lange weiter, bis zu nur einen schieben brauchst.

Du betrachtest, dass was du bei "Wie mache ich 1. ?" machst, wieder als Gesammtaufgabe.

 

[Hoschi49]

das prinzip war mir klar nur rekursiv kann ich mir das kaum vorstellen aber ichkriegs hin


danke für die posts,

cuuuuuuuuuuu

 

[Anubis]

Hast du schon mal mit Binären Bäumen gearbeitet?

Daran kann man Rekursion sehr gut verstehen.