Türme von Hanoi

S

sala

Mitglied
Hallo,

Ich habe die Lösung von den Türmen von Hanoi auf Rekursiveart.

Aber wie ändert man das um Wenn man Immer nur einen Schritt pro stange gehen will also alles andere bleibt gültig aber imer nur einen Schritt nach dem anderen
 
T

TM69

Bekanntes Mitglied
Du meinst soetwas?
Code:
// Java recursive program to solve tower of hanoi puzzle
 
class GFG
{
    // Java recursive function to solve tower of hanoi puzzle
    static void towerOfHanoi(int n, char from_rod, char to_rod, char aux_rod)
    {
        if (n == 1)
        {
            System.out.println("Move disk 1 from rod " +  from_rod + " to rod " + to_rod);
            return;
        }
        towerOfHanoi(n-1, from_rod, aux_rod, to_rod);
        System.out.println("Move disk " + n + " from rod " +  from_rod + " to rod " + to_rod);
        towerOfHanoi(n-1, aux_rod, to_rod, from_rod);
    }
      
    //  Driver method
    public static void main(String args[])
    {
        int n = 4; // Number of disks
        towerOfHanoi(n, 'A', 'C', 'B');  // A, B and C are names of rods
    }
}
 
S

sala

Mitglied
Ja das nur so as man den Turm nur nacheinander gehen kann also von A zu B und dann zu C bzw von C zu B
 
mihe7

mihe7

Top Contributor
Ich glaube, er meint so etwas:
Java:
import java.util.Stack;
import java.util.Scanner;

public class Hanoi {
    static class Params {
        final int n;
        final char from;
        final char to;
        final char help;

        public Params(int n, char from, char to, char help) {
            this.n = n;
            this.from = from;
            this.to = to;
            this.help = help;
        }
    }
    enum Direction { UP, DOWN };

    private Stack<Params> calls;
    private Direction direction = Direction.DOWN;

    public void init(int n) {
        calls = new Stack<>();
        calls.push(new Params(n, 'A', 'C', 'B'));
    }

    public boolean done() {
        return calls.isEmpty();
    }

    public void step() {
        Params params = calls.peek();
        switch (direction) {
            case DOWN:
                char from = params.from;
                char to = params.help;
                char help = params.to;
                for (int i = params.n-1; i >= 1; i--) {
                    calls.push(new Params(i, from, to, help));
                    char tmp = to;
                    to = help;
                    help = tmp;
                }

                params = calls.pop();
                System.out.println("Move disk 1 from rod " + params.from + " to rod " + params.to);
                direction = Direction.UP;
                break;
            case UP:
                params = calls.pop();
                System.out.println("Move disk " + params.n + " from rod " + params.from + " to rod " + params.to);
                calls.push(new Params(params.n-1, params.help, params.to, params.from));
                direction = Direction.DOWN;
                break;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        Hanoi h = new Hanoi();
        h.init(4);
        int step = 0;
        while (!h.done()) {
            System.out.println(++step + ". Schritt (Return, um auszuführen)");
            sc.nextLine();
            h.step();
        }
    }


}
 
M

marlem

Bekanntes Mitglied
Hallo,

ich suche ein Codebeispiel Türme von Hanoi mit Java bei dem die Türme mit ASCII-Zeichen und System.out.println dargestellt werden.
Gibt es sowas?
 
mihe7

mihe7

Top Contributor
Du brauchst ja nur nach jedem Schritt die Türme auszugeben, oder verstehe ich Dich falsch?
 
B

BestGoalkeeper

Bekanntes Mitglied
Ja, genau das!
ich habe es mit for-schleifen versucht, aber das klappt nicht.
Mit Rekursion soll es gehen.
In Google gibt es nur Lösungen mit Grafik.
ich brauche es mit ASCII-Zeichen und System.out.println .
Das muss noch refactored werden:
Java:
import java.util.ArrayList;
import java.util.List;

public class Main {
	public static class Stab {
		List<Integer> l = new ArrayList<>();

		int pop() {
			return l.remove(l.size() - 1);
		}

		void push(int i) {
			l.add(i);
		}
	}
	int n = 4;
	Stab a, b, c;

	Main() {
		a = new Stab();
		b = new Stab();
		c = new Stab();
		for (int i = 0; i < n; i++) {
			a.push(n - i);
		}
	}

	void print() {
		StringBuilder s = new StringBuilder();
		for (int i = 0; i < n; i++) {
			int x = n - i - 1;
			s.append(getDisc(x, a));
			s.append(getDisc(x, b));
			s.append(getDisc(x, c));
			s.append("\n");
		}
		System.out.println(s);
	}

	String getDisc(int x, Stab s) {
		StringBuilder b = new StringBuilder();
		if (x < s.l.size()) {
			for (int i = s.l.get(x); i > 0; i--) {
				b.append("xx");
			}
		}
		return center(b);
	}

	String center(StringBuilder b) {
		int h = n - b.length() / 2;
		for (int i = 0; i < h; i++) {
			b.insert(0, " ");
		}
		for (int i = 0; i < h; i++) {
			b.append(" ");
		}
		return b.toString();
	}

	void bewege(int i, Stab a, Stab b, Stab c) {
		if (i > 0) {
			bewege(i - 1, a, c, b);
			c.push(a.pop());
			print();
			bewege(i - 1, b, a, c);
		}
	}

	public static void main(String[] args) {
		Main m = new Main();
		m.print();
		m.bewege(m.n, m.a, m.b, m.c);
	}
}
Code:
   xx                   
  xxxx                  
 xxxxxx                 
xxxxxxxx                

                        
  xxxx                  
 xxxxxx                 
xxxxxxxx   xx           

                        
                        
 xxxxxx                 
xxxxxxxx   xx     xxxx  

                        
                        
 xxxxxx            xx   
xxxxxxxx          xxxx  

                        
                        
                   xx   
xxxxxxxx xxxxxx   xxxx  

                        
                        
   xx                   
xxxxxxxx xxxxxx   xxxx  

                        
                        
   xx     xxxx          
xxxxxxxx xxxxxx         

                        
           xx           
          xxxx          
xxxxxxxx xxxxxx         

                        
           xx           
          xxxx          
         xxxxxx xxxxxxxx

                        
                        
          xxxx     xx   
         xxxxxx xxxxxxxx

                        
                        
                   xx   
  xxxx   xxxxxx xxxxxxxx

                        
                        
   xx                   
  xxxx   xxxxxx xxxxxxxx

                        
                        
   xx            xxxxxx 
  xxxx          xxxxxxxx

                        
                        
                 xxxxxx 
  xxxx     xx   xxxxxxxx

                        
                  xxxx  
                 xxxxxx 
           xx   xxxxxxxx

                   xx   
                  xxxx  
                 xxxxxx 
                xxxxxxxx
 
M

marlem

Bekanntes Mitglied
@BestGoalkeeper
Vielen Dank. Das compileren hat geklappt, das starten noch nicht, weil ich angeblich eine falsche Java-Version aktiviert habe.
so bald ich das Problem gelöst habe, melde ich mich wieder.
 
M

marlem

Bekanntes Mitglied
Problem gelöst.
Programm macht genau das was es soll. Vielen Dank !
Jetzt schaue ich mir den Code an, damit ich es verstehe wie sowas programmiert wird.
 
B

BestGoalkeeper

Bekanntes Mitglied
Super! aber ich refactore das vielleicht nochmal, wenn gewünscht.
 
B

BestGoalkeeper

Bekanntes Mitglied
Hier bitte, das sollte jetzt besser verständlich sein:
Java:
import java.util.ArrayList;
import java.util.List;

public class Main {
	public static class Stab {
		private List<Integer> l = new ArrayList<>();

		public Stab(int n) {
			for (int i = n; i > 0; i--) {
				push(i);
			}
		}

		public int pop() {
			return l.remove(l.size() - 1);
		}

		public void push(int i) {
			l.add(i);
		}

		public int getSize(int x) {
			if (x < l.size()) {
				return l.get(x);
			}
			return 0;
		}
	}

	private int n;
	private Stab[] staebe;

	public Main(int n) {
		if (n <= 0) {
			throw new IllegalArgumentException();
		}
		this.n = n;
		staebe = new Stab[] { new Stab(n), new Stab(0), new Stab(0) };
	}

	public void print() {
		StringBuilder s = new StringBuilder();
		for (int i = 0; i < n; i++) {
			int x = n - i - 1;
			for (int j = 0; j < staebe.length; j++) {
				s.append(getDisc(x, staebe[j]));
			}
			s.append("\n");
		}
		System.out.println(s);
	}

	private String getDisc(int x, Stab s) {
		StringBuilder b = new StringBuilder();
		int n2 = s.getSize(x);
		int n3 = n - n2 + 2;
		for (int i = 0; i < n3; i++) {
			b.append(" ");
		}
		for (int i = 0; i < n2; i++) {
			b.append("xx");
		}
		for (int i = 0; i < n3; i++) {
			b.append(" ");
		}
		return b.toString();
	}

	public void bewege() {
		bewege(n, staebe[0], staebe[1], staebe[2]);
	}

	private void bewege(int i, Stab a, Stab b, Stab c) {
		if (i > 0) {
			bewege(i - 1, a, c, b);
			c.push(a.pop());
			print();
			bewege(i - 1, b, a, c);
		}
	}

	public static void main(String[] args) {
		Main m = new Main(4);
		m.bewege();
	}
}
 
M

marlem

Bekanntes Mitglied
@BestGoalkeeper
ich versuche mal Deinen Code nachzuvollziehen.
Meine Analyse bezieht sich auf Deinen ersten Code!

Die Klasse Stab ist ein Stack. Mit ihm legst Du die 3 Türme an.
Im Konstruktor der Klasse Main Turm a bekommt 4 Scheiben.
Mit der Funktion getDisc wandelst Du die Zahlen in xx um.
Mit der Funktion center sorgst Du dafür die Zeichen x horizontal
zentriert ausgegeben werden.
Die Funktion print() gibt die 3 Türme aus.
Die Funktion bitte schrittweise erklären, weil da habe ich meinen
geistigen "Hänger"!
Mein Problem:
Du gibst 3 Stacks aus, die unterschiedlich viele Elemente (Scheiben)
haben und das mit einer For-Schleife.
Das verstehe ich nicht!
 
B

BestGoalkeeper

Bekanntes Mitglied
print() könntest du dir so vorstellen

staebe.png


a1 bis a4 ist Stab A, b1 bis b4 ist Stab B... die grauen Kästchen signalisieren, dass sich in dem Kästchen eine Scheibe befindet, also wird dann entsprechend oft "xx" dem StringBuilder hinzugefügt.
 
B

BestGoalkeeper

Bekanntes Mitglied
Sorry, merke gerade, die Grafik ist verkerht herum, der Anfang wäre bei a1 bis c1 und von c1 nach a2 usw. :(
 
M

marlem

Bekanntes Mitglied
Vielen vielen Dank für die Grafik.
Nochmal Fragen zum Code von print():
i sind die Zeilen?
j sind die Spalten?
Du speicherst die Darstellung aller Türme auf den StringBuilder s und druckst die ganzen Türme auf einmal mit
System.out.println?

Richtig?
 
M

marlem

Bekanntes Mitglied
Hi,
kannst Du mir noch diese Funktion erklären:
Java:
private String getDisc(int x, Turm s) {
        StringBuilder b = new StringBuilder();
        int n2 = s.getSize(x);
        int n3 = n - n2 + 2;
        for (int i = 0; i < n3; i++) {
            b.append(" ");
        }
        for (int i = 0; i < n2; i++) {
            b.append("**");
        }
        for (int i = 0; i < n3; i++) {
            b.append(" ");
        }
        return b.toString();
    }

Dass die Funktion die Turmscheiben als ASCII-Zeichen darstellt, habe ich verstanden, aber die Bedeutung der ganzen ns habe ich nicht verstanden.
 
B

BestGoalkeeper

Bekanntes Mitglied
Ja ich hätte das kommentieren sollen... Zuerst werden für eine Scheibe die Leerzeichen davor hinzugefügt, dann die "xx" - und dann die Leerzeichen danach. n ist die Anzahl an Scheiben, die es geben kann (hier 4). n2 ist die aktuelle Scheibe, die gerade dargestellt werden soll. n3 ist quasi die Hälfte des Rests und die Anzahl an Leerzeichen, die je davor und danach hinzugefügt werden sollen.
Zeile 4... das "+ 2" ist die Anzahl des zusätzlichen Zwischenraums an Leerzeichen.
Ich dachte, weil die Tiefe der Methode jetzt nicht mehr so hoch ist (kein zusätzlicher Aufruf), wär die Methode jetzt einfacher zu verstehen...
 
M

marlem

Bekanntes Mitglied
Danke.
Das ich es nicht verstanden habe, liegt an mir.
Aber jetzt ist alles klar. Danke.
 
M

marlem

Bekanntes Mitglied
Ich lerne seit März 2020 die Programmiersprache Python.
Ein Python-Programm welches unter Windows entwickelt wurde unter Ubuntu und MacOS laufen lassen ist sehr einfach.
Jetzt programmiere ich mit Python eine Art Sprachassistent.
Die Kommandos werden geschrieben und nicht gesprochen.
Die Antworten kommen nicht als Sprachausgabe sondern als Text.
Jetzt wollte ich das man mit meinem Assistenten Türme von Hanoi spielen kann.
Die Türme mit Zahlen darstellen war kein Problem.
Das was Du mir jetzt erklärt hast habe ich nicht hinbekommen.

Bedeutet: Ich werde jetzt die Java-Lösung in Python coden :)
 
B

BestGoalkeeper

Bekanntes Mitglied
Python:
n = 4
staebe = [[4,3,2,1],[],[]]
def move():
    pout()
    move1(n,staebe[0],staebe[1],staebe[2])
def move1(i,a,b,c):
    if i > 0:
        move1(i-1,a,c,b)
        c.append(a.pop())
        pout()
        move1(i-1,b,a,c)
def pout():
    print(staebe)
    for i in reversed(range(n)):
        for s in staebe:
            if i < len(s):
                n2 = n - s[i] + 2
                for j in range(n2):
                    print(" ",end='')
                for j in range(s[i]):
                    print("**",end='')
                for j in range(n2):
                    print(" ",end='')
            else:
                for j in range(n + 2):
                    print("  ",end='')
        print()
move()
 
B

BestGoalkeeper

Bekanntes Mitglied
Aber müsste vielleicht noch refactored werden, bin mir fast sicher, dass es da noch ein paar Kniffe gibt ;)
 
B

BestGoalkeeper

Bekanntes Mitglied
Hier mal etwas zum ausprobieren für euch. Ich nehme Verbesserungsvorschläge gerne an!
Bei n=3 hält es bei mir an. Für n=4 hält es bei mir nach ca. 1 Stunde an:
Python:
n = 3;
class Tuerme:
    ts = [[],[],[]]
    def __init__(self, n:int):
        for i in reversed(range(1,n+1)):
            self.ts[0].append(i);
    def display(self):
        print(self.ts)
    def legal(self, von:int, nach:int):
        if 0 <= von < 3 and 0 <= nach < 3:
            if len(self.ts[von]) > 0 and (len(self.ts[nach]) == 0 or self.ts[von][-1] < self.ts[nach][-1]):
                return True
        return False
    def move(self, von:int, nach:int):
        if self.legal(von,nach):
            self.ts[nach].append(self.ts[von].pop())
        else:
            raise Exception("not legal")
    def won(self):
        if len(self.ts[0]) == 0:
            if len(self.ts[1]) == 0:
                for i in range(len(self.ts[2])-1):
                    if self.ts[2][i] < self.ts[2][i+1]:
                        return False
                return True
            if len(self.ts[2]) == 0:
                for i in range(len(self.ts[1])-1):
                    if self.ts[1][i] < self.ts[1][i+1]:
                        return False
                return True
        return False
    def best_move(self):
        moves = []
        for a in range(3):
            for b in range(3):
                if (self.legal(a,b)):
                    moves.append([(a,b)])
        while True:
            m = moves.pop(0)
            for mov in m:
                self.move(mov[0],mov[1])
            if self.won():
                for mov in reversed(m):
                    self.move(mov[1],mov[0])
                return m[0]
            for a in range(3):
                for b in range(3):
                    if (self.legal(a,b)):
                        m2 = m.copy()
                        m2.append((a,b))
                        moves.append(m2)
            for mov in reversed(m):
                self.move(mov[1],mov[0])
        return []

tuerme = Tuerme(n)
tuerme.display()
while not tuerme.won():
    b = tuerme.best_move()
    print(b)
    tuerme.move(b[0],b[1])
    tuerme.display()

Bei euch auch?
 
B

BestGoalkeeper

Bekanntes Mitglied
Problem gelöst:
Python:
import random as r

n = 10;
class Tuerme:
    ts = [[],[],[]]
    def __init__(self, n:int):
        for i in reversed(range(1,n+1)):
            self.ts[0].append(i);
    def display(self):
        print(self.ts)
    def legal(self, von:int, nach:int):
        if 0 <= von < 3 and 0 <= nach < 3:
            if len(self.ts[von]) > 0 and (len(self.ts[nach]) == 0 or self.ts[von][-1] < self.ts[nach][-1]):
                return True
        return False
    def move(self, von:int, nach:int):
        if self.legal(von,nach):
            self.ts[nach].append(self.ts[von].pop())
        else:
            raise Exception("not legal")
    def won(self):
        if len(self.ts[0]) == 0:
            if len(self.ts[1]) == 0:
                for i in range(len(self.ts[2])-1):
                    if self.ts[2][i] < self.ts[2][i+1]:
                        return False
                return True
            if len(self.ts[2]) == 0:
                for i in range(len(self.ts[1])-1):
                    if self.ts[1][i] < self.ts[1][i+1]:
                        return False
                return True
        return False
    def get_ts_tuple(self):
        return (tuple(self.ts[0]),tuple(self.ts[1]),tuple(self.ts[2]))
    def best_move(self):
        moves = []
        set_moves = {self.get_ts_tuple()};
        for a in range(3):
            for b in range(3):
                if (self.legal(a,b)):
                    moves.append([(a,b)])
        while True:
            m = moves.pop(0)
            for mov in m:
                self.move(mov[0],mov[1])
            if self.get_ts_tuple() in set_moves:
                for mov in reversed(m):
                    self.move(mov[1],mov[0])
                continue
            else:
                set_moves.add(self.get_ts_tuple())
            if self.won():
                for mov in reversed(m):
                    self.move(mov[1],mov[0])
                return m[0]
            for a in range(3):
                for b in range(3):
                    if (self.legal(a,b)):
                        m2 = m.copy()
                        m2.append((a,b))
                        moves.append(m2)
                        # moves.insert(r.randint(0,len(moves)),m2)
            for mov in reversed(m):
                self.move(mov[1],mov[0])
        return []

tuerme = Tuerme(n)
tuerme.display()
while not tuerme.won():
    b = tuerme.best_move()
    print(b)
    tuerme.move(b[0],b[1])
    tuerme.display()
 
B

BestGoalkeeper

Bekanntes Mitglied
Noch schnell eine Anmerkung, falls jemand hierauf stößt und sich wundert, warum das alles so langsam ist... Natürlich ist jeder Algorithmus der auf Wikipedia steht schneller, um den optimalsten nächsten Schritt systematisch in O(1) zu berechnen, aber ich wollte da einmal mit "roher Gewalt" ran... Und klar es wäre auch "schlauer", den einmal berechneten optimalen Weg zu speichern und einfach den nächsten Schritt zurückzugeben (aber dazu müsste man auch immer den optimalen Weg wählen)... Also nicht wundern, wenn "rohe Gewalt" nicht die optimalste Lösung für dieses Spielchen darstellt.
 
B

BestGoalkeeper

Bekanntes Mitglied
Hier nochmal mit einem Cut, der circa die Hälfte der Möglichkeiten abschneidet, wodurch nur noch ca. die Hälfte der Zeit benötigt wird. Wobei ich aber einen Knoten des Suchbaumes nicht sinnvoll bewerten kann...
Also kann für einen Knoten berechnet werden ,wie weit dieser vom Zielknoten entfernt ist? Wahrscheinlich nicht. :(
Python:
import random as r

n = 8;
class Tuerme:
    ts = [[],[],[]]
    def __init__(self, n:int):
        for i in reversed(range(1,n+1)):
            self.ts[0].append(i);
    def display(self):
        print(self.ts)
    def legal(self, von:int, nach:int):
        if 0 <= von < 3 and 0 <= nach < 3:
            if len(self.ts[von]) > 0 and (len(self.ts[nach]) == 0 or self.ts[von][-1] < self.ts[nach][-1]):
                return True
        return False
    def move(self, von:int, nach:int):
        if self.legal(von,nach):
            self.ts[nach].append(self.ts[von].pop())
        else:
            raise Exception("not legal")
    def won(self):
        if len(self.ts[0]) == 0:
            if len(self.ts[1]) == 0 or len(self.ts[2]) == 0:
                return True
        return False
    def get_ts_tuple(self):
        return (tuple(self.ts[0]),tuple(self.ts[1]),tuple(self.ts[2]))
    def get_shuffled_options(self):
        o = [(0,1),(0,2),(1,0),(1,2),(2,0),(2,1)]
        # r.shuffle(o)
        return o
    def best_move(self):
        moves = []
        set_moves = {self.get_ts_tuple()};
        for o in self.get_shuffled_options():
            a = o[0]
            b = o[1]
            if (self.legal(a,b)):
                moves.append([(a,b)])
        while len(moves) > 0:
            m = moves.pop(0)
            for mov in m:
                self.move(mov[0],mov[1])
            if self.get_ts_tuple() not in set_moves:
                set_moves.add(self.get_ts_tuple())
                if self.won():
                    for mov in reversed(m):
                        self.move(mov[1],mov[0])
                    return m[0]
                for o in self.get_shuffled_options():
                    a = o[0]
                    b = o[1]
                    if (self.legal(a,b)):
                        self.move(a,b)
                        # CUT!
                        if self.get_ts_tuple() not in set_moves:
                            m2 = m.copy()
                            m2.append((a,b))
                            moves.append(m2)
                        self.move(b,a)
            for mov in reversed(m):
                self.move(mov[1],mov[0])
        return []

tuerme = Tuerme(n)
tuerme.display()
while not tuerme.won():
    b = tuerme.best_move()
    print(b)
    tuerme.move(b[0],b[1])
    tuerme.display()
 
B

BestGoalkeeper

Bekanntes Mitglied
Hab mal gerade einen Benchmark mit n=7 durchgeführt:

Figure_1.png


Die Y-Achse gibt die Zeit in Sekunden pro best_move() call wieder...

Der eine Ausreißer kommt wohl weil ich nebenbei noch Musik höre....
 
mrBrown

mrBrown

Super-Moderator
Mitarbeiter
Du meinst soetwas?
Code:
// Java recursive program to solve tower of hanoi puzzle

class GFG
{
    // Java recursive function to solve tower of hanoi puzzle
    static void towerOfHanoi(int n, char from_rod, char to_rod, char aux_rod)
    {
        if (n == 1)
        {
            System.out.println("Move disk 1 from rod " +  from_rod + " to rod " + to_rod);
            return;
        }
        towerOfHanoi(n-1, from_rod, aux_rod, to_rod);
        System.out.println("Move disk " + n + " from rod " +  from_rod + " to rod " + to_rod);
        towerOfHanoi(n-1, aux_rod, to_rod, from_rod);
    }
     
    //  Driver method
    public static void main(String args[])
    {
        int n = 4; // Number of disks
        towerOfHanoi(n, 'A', 'C', 'B');  // A, B and C are names of rods
    }
}
BTW, damit die Quelle wenigstens auch mal erwähnt wird, in der es noch ein paar Erklärungen gibt: https://www.geeksforgeeks.org/c-program-for-tower-of-hanoi/
 
B

BestGoalkeeper

Bekanntes Mitglied
Hier einmal für n=8:
Python:
import time
import random as r

# importing the required module
import matplotlib.pyplot as plt

n = 8;

class Towers:
    ts = [[], [], []]
    seconds = []

    def __init__(self, n:int):
        for i in reversed(range(1, n + 1)):
            self.ts[0].append(i);

    def display(self):
        print(self.ts)

    def legal(self, a:int, b:int):
        if 0 <= a < 3 and 0 <= b < 3:
            if len(self.ts[a]) > 0 and (len(self.ts[b]) == 0 or self.ts[a][-1] < self.ts[b][-1]):
                return True
        return False

    def move(self, a:int, b:int):
        if self.legal(a, b):
            self.ts[b].append(self.ts[a].pop())
        else:
            raise Exception("not legal")

    def won(self):
        if len(self.ts[0]) == 0:
            if len(self.ts[1]) == 0 or len(self.ts[2]) == 0:
                return True
        return False

    def get_ts_tuple(self):
        return (tuple(self.ts[0]), tuple(self.ts[1]), tuple(self.ts[2]))

    def get_shuffled_options(self):
        # o = [(0, 1), (0, 2), (1, 0), (1, 2), (2, 0), (2, 1)]
        # r.shuffle(o)
        return ((0, 1), (0, 2), (1, 0), (1, 2), (2, 0), (2, 1))

    def best_move(self):
        t1 = time.time()
        moves = []
        set_moves = {self.get_ts_tuple()};
        for o in self.get_shuffled_options():
            a = o[0]
            b = o[1]
            if (self.legal(a, b)):
                moves.append([(a, b)])
        while len(moves) > 0:
            m = moves.pop(0)
            for mov in m:
                self.move(mov[0], mov[1])
            if self.get_ts_tuple() not in set_moves:
                set_moves.add(self.get_ts_tuple())
                if self.won():
                    for mov in reversed(m):
                        self.move(mov[1], mov[0])
                    t2 = time.time()
                    self.seconds.append(t2-t1)
                    return m[0]
                for o in self.get_shuffled_options():
                    a = o[0]
                    b = o[1]
                    if (self.legal(a, b)):
                        self.move(a, b)
                        # CUT!
                        if self.get_ts_tuple() not in set_moves:
                            m2 = m.copy()
                            m2.append((a, b))
                            moves.append(m2)
                        self.move(b, a)
            for mov in reversed(m):
                self.move(mov[1], mov[0])
        return []

towers = Towers(n)
towers.display()
while not towers.won():
    b = towers.best_move()
    print(b)
    towers.move(b[0], b[1])
    towers.display()
for s in towers.seconds:
    print(s)
x = []
for i in range(len(towers.seconds)):
    x.append(i)
# plotting the points
plt.plot(x, towers.seconds)
# naming the x axis
plt.xlabel('x - axis (number of call)')
# naming the y axis
plt.ylabel('y - axis (seconds per call)')
# giving a title to my graph
plt.title('My first graph!')
# function to show the plot
plt.show()

Figure_3.png


Kann jemand den Knick bei etwa x=130 erklären (ca. bei der Hälfte...)? Danke.
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
B Türme von Hanoi mit einer beliebigen aber gültigen Eingabe lösen Java Basics - Anfänger-Themen 5
S Rekursion Rückgabe - Türme von Hanoi Java Basics - Anfänger-Themen 16
K Türme von Hanoi - Rekursiv. Java Basics - Anfänger-Themen 1
C Türme von Hanoi - Anzhal der Züge Java Basics - Anfänger-Themen 1
D Türme von Hanoi in "Java ist auch eine Insel" Java Basics - Anfänger-Themen 4
D Türme von hanoi Java Basics - Anfänger-Themen 7
B Türme von Hanoi ausgabe Java Basics - Anfänger-Themen 2
shiroX OOP Türme von Hanoi - einfache grafische Ausgabe Java Basics - Anfänger-Themen 2
T Türme von Hanoi Java Basics - Anfänger-Themen 9
D > 3 Türme von Hanoi Java Basics - Anfänger-Themen 11
J Erste Schritte türme von hanoi verständnisprobleme Java Basics - Anfänger-Themen 6
B Türme von Hanoi - Iterator Java Basics - Anfänger-Themen 50
R Türme von Hanoi mit beliebiger Startposition Java Basics - Anfänger-Themen 5
G Verständnisproblem Türme von Hanoi Java Basics - Anfänger-Themen 4
X Türme von Hanoi - Iterativ Java Basics - Anfänger-Themen 8
B Türme von Hanoi: aktuelle Belegungszustände ausgeben? Java Basics - Anfänger-Themen 2
T Rekursiver Algorithmus: Türme von Hanoi Java Basics - Anfänger-Themen 8
H Quicksort und Rekursiv: Türme von Hanoi Java Basics - Anfänger-Themen 9
X Turm von Haoi - 4 Scheiben 4 Türme Java Basics - Anfänger-Themen 11
P Hanoi Java Basics - Anfänger-Themen 1
R Hanoi rekursiv lösen Problem Java Basics - Anfänger-Themen 1
E Hanoi-Varianten rekursiv Java Basics - Anfänger-Themen 2
P Hanoi rekursiv zu iterativ umbauen Java Basics - Anfänger-Themen 20
F Methoden Hanoi - Anzahl der Bewegungen Java Basics - Anfänger-Themen 8
kulturfenster Probleme mit Hanoi Java Basics - Anfänger-Themen 3
B Kann Quellcode von "Hanoi" nicht verstehen. Bitte Java Basics - Anfänger-Themen 4
kulturfenster Hanoi Java Basics - Anfänger-Themen 28
D Hanoi Java Basics - Anfänger-Themen 6
L Hanoi II : Rekursiviker gesucht Java Basics - Anfänger-Themen 22

Ähnliche Java Themen

Anzeige

Neue Themen


Oben