Hanoi II : Rekursiviker gesucht

[Leroy42]

Ich habe mich gestern an einen Thread von Timo und merc beteiligt, wobei
mich merc's Frage auch interessiert.

Wie sieht der rekursive Algorithmus zum Finden einer kürzesten Lösung
bei Türme von Hanoi aus, wenn man insgesamt 4 Stangen zur Verfügung hat.

Ich habe mal ein altes Programm von mir rausgekramt und derart erweitert,
daß es mit einer variablen Anzahl von Stangen klarkommt, um eine Unterstützung
beim Finden der Lösung zu bieten
Hanoi.jar
Die Source dazu
Hanoi.java
(Nicht über die Source lästern, ist immerhin ein altes Programm) :shock:

Achtung: Es wird nicht mit der Maus bedient (ist mir zu friemelig) sondern mit der
Tastatur indem man nacheinander die Nummer der Quell- und der Zielstange
eintippt(*). Die Stangen sind von 1 bis n durchnumeriert.

Ich selbst habe schon etwas rumprobiert und habe für die minimale Zugzahl bei
4 Stangen gefunden:
5, 9, 13, 20 Züge bei 3, 4, 5, 6 Scheiben. Bei der Zuganzahl für 6 Scheiben bin ich
mir nicht sicher, ob es einen kürzeren Weg gibt.

Weiß jemand wie ich jetzt das rekursive Schema, und damit eine Formel für
die Zuganzahl, finden kann.

Oder hat jemand einen Ansatz, wie ich das Programm dahingehend erweitere,
daß es via intelligentes Backtracking zumindes die minimale Zuganzahl in
Abhängigkeit von der Scheibenanzahl selbst bestimmt?

Danke im Voraus

(*) Es ist übrigens interessant zu erleben, wie sich unser Gehirn in relativer
kurzer Zeit des Problem annimt und die Finger nur noch über die 3 Tasten
"1", "2" und "3" fliegen um den Turm umzubauen ohne daß wir selbst noch
genau nachvollziehen können, wie wir denken. Ich brauche für einen 6-er Turm
(3 Stangen) inzwischen gerade mal 34 Sekunden :shock:

 

[Leroy42]

Kann mir wirklich niemand einen Tipp geben

Mein Hauptproblem ist, daß ich bei einem Brute-Force-Backtracking auch
zu einem Ende komme und nicht in eine Schleife gerate. Es kann, und wir ja auch,
vorkommen, daß der Backtracking-Algorithmus nach bestimmten
Scheiben-Umsetzungen wieder einen Zustand erreicht, der während der aktuellen
Zugfolge bereits erreicht wurde und den ich dann naturgemäß nicht weiterverfolgen
darf.

Mir ist klar, daß ich dafür die bisher erreichten Zustände merken muß. Aber was
für eine Datenstruktur nehme ich am besten dafür. Es kann ja auch ein Zustand
eintreten, der nur äquivalent zu einem vorherigen in dem Sinne ist, daß nur
die erreichten Teiltürme der beiden Hilfsstangen vertauscht sind. Wie kann ich
das feststellen (oder brauche ich mich darum gar nicht zu kümmern)?

Desweiteren macht mir Schwierigkeiten, daß ich ja nicht nur eine beliebige
Zugfolge finden will, die am Ende den Turm umbaut sondern eine kürzeste.
Dazu widerum muß ich mir ja nicht nur die einzelnen Zustände merken, sondern
auch die bisher jeweils kürzeste ==> Noch 'ne Datenstruktur

Hat jemand Vorschläge wie ich dies bewerkstelligen könnte/sollte?

 

[SlaterB]

ich habs nun auch mal bisschen probiert,

Wertetabelle

2, 3, 4,  5,  6,  7,  8
3, 5, 9, 13, 17, 25, 33

die Rekursionsgleichung ist dann
f(n)=2*f(n-2)+7


ein Beispiel fürs Brute-Force, benutzt eine vorgegeben maximale Suchtiefe, damits nicht zu lange dauert,
bei 6 und auch noch 7 ganz akzeptabel

package test;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

import standard.L;
import standard.P;


public class HanoiBruteforce {

	// Cache für Integer-Werte
	static Integer[] tiefen = new Integer[1000];
	// Cache für Leerzeichen zur Formatierung
	static String[] leer =
		{
			"        |",
			"       |",
			"      |",
			"     |",
			"    |",
			"   |",
			"  |",
			" |",
			"|",
			"|" };

	// Anzahl Scheiben
	static int anz = 6;
	// maximale Tiefe für rekursive Suche
	static int maxTiefe = 22;

	// 4 Stangen
	static LinkedList[] stangen = new LinkedList[4];

	// bisher bekannte Zustände + minimale Tiefe dahin
	static HashMap zustaende = new HashMap();

	// zählt Arbeitsschritte
	static long count = 0;

	// Tiefe der Rekursion
	static int tiefe = 0;

	// Weg der bisherigen Rekursion
	static LinkedList weg = new LinkedList();

	static {
		for (int i = 0; i < tiefen.length; i++) {
			tiefen[i] = new Integer(i);
		}

		for (int i = 0; i < 4; i++) {
			stangen[i] = new LinkedList();
		}

		// Stange 0 füllen
		for (int i = anz; i >= 1; i--) {
			stangen[0].add(tiefen[i]);
		}
		zustandBearbeiten();
	}

	public static void main(String[] args) {
		p("maximale Suchtiefe: " + maxTiefe);
		rek();
		p("count: " + count);
		//		ausgabeMap();
	}

	// ein Rekursionsschritt
	public static void rek() {
		count++;
		if (count > 3000000) {
			p("maximum count: " + count + ", exit");
			P.exit();
		}
		if (count % 10000 == 0) {
			p("count: " + count);
		}
		tiefe++;
		if (tiefe <= maxTiefe) {
			// die 4 Stangen durchgehen und oberste Scheibe bewegen
			for (int i = 0; i < 4; i++) {
				if (stangen[i].isEmpty()) {
					continue;
				}

				Integer scheibe = (Integer) stangen[i].removeLast();

				// Sonderbehandlung für unterste Scheibe:
				// nur sofort zum Ziel bewegen wenn möglich, sonst nix tun
				if (scheibe == tiefen[anz]) {
					if ((i == 1) || !stangen[3].isEmpty()) {

					} else {
						// 4. Stange ist Zielstange, Rekursion
						stangen[3].add(scheibe);
						if (zustandBearbeiten()) {
							rek();
						}
						// alten Zustand wiederherstellen
						stangen[3].removeLast();
					}
				} else {
					// Scheibe auf eine der 4 Stangen legen
					for (int j = 0; j < 4; j++) {
						if (i == j) {
							continue;
						}
						if (stangen[j].isEmpty()
							|| ((Integer) stangen[j].getLast()).intValue()
								> scheibe.intValue()) {

							// Rekursion
							stangen[j].add(scheibe);
							if (zustandBearbeiten()) {
								rek();
							}
							// alten Zustand wiederherstellen	
							stangen[j].removeLast();
						}
					}
				}
				// alten Zustand wiederherstellen				
				stangen[i].add(scheibe);
			}
		}
		// alten Zustand wiederherstellen
		weg.removeLast();
		tiefe--;
	}

	// prueft ob der aktuelle Zustand rekursiv weiterbearbeitet werden soll,
	// dies ist nicht der Fall, wenn schon mal mit geringerer Tiefe bearbeitet
	public static boolean zustandBearbeiten() {
		// Stringrepäsentation für aktuellen Zustand bilden
		StringBuffer f = new StringBuffer();
		for (int i = 0; i < 4; i++) {
			for (Iterator iter = stangen[i].iterator(); iter.hasNext();) {
				f.append(iter.next().toString());
			}
			f.append(leer[stangen[i].size()]);
		}
		String st = f.toString();

		// nach vorherigen gleichen Zustand schauen, evtl. Abbruch
		Integer t = (Integer) zustaende.get(st);
		if ((t != null) && (tiefe >= t.intValue())) {
			return false;
		}

		// Zustand + Tiefe dahin speichern
		zustaende.put(st, tiefen[tiefe]);
		// Zustand in Weg aufnehmen
		weg.add(st);

		// bei einem Zielzustand eine Logmeldung ausgeben
		if (stangen[0].isEmpty()
			&& stangen[1].isEmpty()
			&& stangen[2].isEmpty()) {
			p("\n\n"+st + "    neue Tiefe: " + tiefe);
			ausgabeWeg();
		}
		return true;
	}

	// gibt die Map der bisher gespeicherten Zustände + minimale Tiefe dahin aus
	public static void ausgabeMap() {
		String st = "Anzahl: " + zustaende.size() + "\n";
		List list = new ArrayList(zustaende.keySet());
		Collections.sort(list);
		for (Iterator iter = list.iterator(); iter.hasNext();) {
			String key = (String) iter.next();
			st += P.bL(key, 40) + " -> " + zustaende.get(key) + "\n";
		}
		p(st);
	}

	// gibt den aktuellen Weg aus
	public static void ausgabeWeg() {
		for (Iterator iter = weg.iterator(); iter.hasNext();) {
			p(iter.next());
		}
	}

	public static void p(Object o) {
		System.out.println(o.toString());
	}

}

 

[Frankyboy]

Nach meiner Ansicht müsste der Algorithmus wie folgt lauten:

1. Bewege die kleinsten n − 3 Scheiben von Stab 0 auf 1, unter Benutzung aller 4 Stäbe.
2. Bewege die größten 3 Scheiben von Stab 0 auf 3, ohne Stab 1 zu benutzen.
Das impliziert die Verwendung der optimalen Methode für 3 Stäbe für diese Teilaufgabe, also 7 Züge.
3. Bewege die kleinsten n − 3 Scheiben unter Verwendung aller Stäbe von Stab 1 auf 3.


Damit ergibt das foldende Rekursionsformel:

f(n) = f(n-3) + 7

 

[Leroy42]

Du hast jetzt zwar einen über ein Jahr alten Thread wieder ausgepackt,
aber deine Lösung hört sich interessant an; werd' mal drüber nachdenken...

 

[Leroy42]

...

Ohh! Ich sehe jetzt erst, daß du dir schonmal Gedanken gemacht hast. :shock:

Ich werde deinen Code mal ausprobieren, wenn ich zuhause wieder einen Rechner habe!

 

[Frankyboy]

Mein Posting war gestern nicht korrekt, die Zahl 3 wohl etwas willkürlich gewählt oder vom Vorgänger inspiriert.
Ich habe mir nochmal genauer Gedanken gemacht und den Algorithmus etwas abgewandelt, indem 3 durch k ersetzt wird

1. Bewege die kleinsten n − k Scheiben von Stab 0 auf 1, unter Benutzung aller 4 Stäbe.
2. Bewege die größten k Scheiben von Stab 0 auf 3, ohne Stab 1 zu benutzen.
Das impliziert die Verwendung der optimalen Methode für k Stäbe für diese Teilaufgabe, also 2^k-1 Züge.
3. Bewege die kleinsten n − k Scheiben unter Verwendung aller Stäbe von Stab 1 auf 3.

Für das optimale Ergebnis muss das Minimum über alle k gebildet werden.

Die Rekursionsformel lautet daher wie folgt:

f(n) = min {2xf(n-k) + 2^k-1} für 0<k<n

Bsp.:

f(1) = 1
f(2) = 3
f(3) = min {2Xf(2)+1, 2xf(1)+3} = min{7,5} = 5
f(4) = min {2xf(3)+1, 2xf(2)+3, 2xf(1)+7} = min{11,9,9} = 9
f(5) = min {2xf(4)+1, 2xf(3)+3, 2xf(2)+7, 2xf(1)+15} = min{19,13,13,17} = 13
f(6) = min {2xf(5)+1, 2xf(4)+3, 2xf(3)+7, 2xf(2)+15, 2xf(1)+31} = min{27,21,17,21,33} = 17
f(7) = min {2xf(6)+1, 2xf(5)+3, 2xf(4)+7, 2xf(3)+15, 2xf(2)+31, 2xf(1)+63} = min{35,29,25,25,37,65} = 25
f(8) = min {2xf(7)+1, 2xf(6)+3, 2xf(5)+7, 2xf(4)+15, 2xf(3)+31, 2xf(2)+63, 2xf(1)+127} = min{51,37,33,33,41,69,129}
= 33
f(9) = min {2xf(8)+1, 2xf(7)+3, 2xf(6)+7, 2xf(5)+15, 2xf(4)+31, 2xf(3)+63, 2xf(2)+127, 2xf(1)+255}
= min{67,53,41,41,49,73,133,257} = 41
f(10)= min {2xf(9)+1, 2xf(8)+3, 2xf(7)+7, 2xf(6)+15, 2xf(5)+31, 2xf(4)+63, 2xf(3)+127, 2xf(2)+255, 2xf(1)+511}
= min {83,69,57,49,57,81,137,261,513} = 49
f(11)= min {2xf(10)+1, 2xf(9)+3, 2xf(8)+7, 2xf(7)+15, 2xf(6)+31, 2xf(5)+63, 2xf(4)+127, 2xf(3)+255, 2xf(2)+511,
2xf(1)+1023}
= min {99,85,73,65,65,89,145,265,517,1025} = 65

ab n=10 gilt f(n) = 2 x f(n-4) + 15
für n<10 gilt f(n) = 2 x f(n-3) +7

 

[Marco13]

Naja - die letzte Aussage ist jetzt schon sehr gewagt .... bist du sicher, dass die Formel "ab" n=10 gilt, und nicht vielleicht bei n=20 dann eine andere Formel gelten müßte? Und ob man die beiden (und möglicherweise alle weiteren) Formeln nicht auch als EINE Formel beschreiben könnte (oder können müßte)? Was ändert sich denn bei n=10 so schlagartig, dass da auf einmal eine ganz andere Formel gilt?

Nach einem kurzen Blick auf die Ergebnisse sieht man, dass die Differenzen zwischen zwei f(n) beginnend bei f(2) gerade die folgenden sind:

2
4
4
8
8
8
8
16

Ohne das beweisen zu wollen... es würde mich schon fast wundern, wenn es da nicht so weitergehen würde
...
8
16
...8mal
16
32
...16mal
32
64
...32mal
64

Allerdings habe ich den Algorithmus nicht nachvollzogen, es ist also nur Spekulation auf basis des bisherigen outputs... :roll:

 

[Marco13]

OK, es waren 3 mal "4" (Ich brauch' Koffein :shock: )

Die Lösung sollte in diesem Fall dann sein:
f(n) = f(n-1) + 2 ^ floor(-0.5 + sqrt(0.25 + 2*(n-1))

class Hanoi2
{
    public static void main(String args[])
    {
        for (int n=0; n<50; n++)
        {
            System.out.println("f("+n+") = "+f(n));
        }
    }

    static double f(int n)
    {
        if (n==0)
        {
            return 0;
        }
        double x = Math.pow(2,(int)sol(n-1));
        return x + f(n-1);
    }

    // Inverse of f(x) = Sum(1...x){x}
    static double sol(double s)
    {
        return -0.5 + Math.sqrt(0.25 - -2*s);
    }
}

Die Ausgabe ist dann

f(0) = 0.0
f(1) = 1.0
f(2) = 3.0
f(3) = 5.0
f(4) = 9.0
f(5) = 13.0
f(6) = 17.0
f(7) = 25.0
f(8) = 33.0
f(9) = 41.0
f(10) = 49.0
f(11) = 65.0
f(12) = 81.0
f(13) = 97.0
f(14) = 113.0
f(15) = 129.0
f(16) = 161.0
f(17) = 193.0
f(18) = 225.0
f(19) = 257.0
f(20) = 289.0
f(21) = 321.0
f(22) = 385.0
f(23) = 449.0
f(24) = 513.0
f(25) = 577.0
f(26) = 641.0
f(27) = 705.0
f(28) = 769.0
f(29) = 897.0
f(30) = 1025.0
f(31) = 1153.0
f(32) = 1281.0
f(33) = 1409.0
f(34) = 1537.0
f(35) = 1665.0
f(36) = 1793.0
f(37) = 2049.0
f(38) = 2305.0
f(39) = 2561.0
f(40) = 2817.0
f(41) = 3073.0
f(42) = 3329.0
f(43) = 3585.0
f(44) = 3841.0
f(45) = 4097.0
f(46) = 4609.0
f(47) = 5121.0
f(48) = 5633.0
f(49) = 6145.0
...

was ja so weit (d.h. bis 11) erstmal zu stimmen scheint... Kannst ja mal schauen, ob es bei den restlichen Zahlen auch passt :wink:

 

[Frankyboy]

Ich kann deine Zahlen bestätigen.
Dabei ist mir folgendes aufgefallen:

Es gilt
f(n)=2*f(n-1)+1 für n=1,2
f(n)=2*f(n-2)+3 für n=3,4,5
f(n)=2*f(n-3)+7 für n=6,7,8,9
f(n)=2*f(n-4)+15 für n=10,11,12,13,14

allgemein

f(n) = 2*f(n - floor(-0.5 + sqrt(0.25 + 2*n)) + 2 ^ floor(-0.5 + sqrt(0.25 + 2*n)) -1

Sieht auf den ersten Blick komplizierter aus, ist aber denke ich geeigneter, das eigentliche Problem für ToH mit 4 Stäben zu lösen

 

[Leroy42]

Menno, jetzt habe ich dieses Thema hier angebracht, hab' bei euch
beiden aber nix mehr mitzureden.

Aber

f(n) = 2*f(n - floor(-0.5 + sqrt(0.25 + 2*n)) + 2 ^ floor(-0.5 + sqrt(0.25 + 2*n)) -1

kann nicht der Weisheit letzter Schluß sein;
das widerstrebt meiner rekursiven Seele, die einfache, elegante,
Rekursionsfolgen (Lösungen) favorisiert.

 

[Frankyboy]

Das ist wohl hier das Problem, dass wegen der Komplexität keine einfache Rekursion möglich ist

 

[maki]

kann nicht der Weisheit letzter Schluß sein;
das widerstrebt meiner rekursiven Seele, die einfache, elegante,
Rekursionsfolgen (Lösungen) favorisiert.

Sieh es positiv, Rekursion kostet pro Aufruf einen Stackframe, bei tausenden Stangen könnten die ausgehen... aber klar ist rekursion für so etwas sehr gut geeignet, da der Code aussagekräftiger wird.

 

[Leroy42]

bei tausenden Stangen könnten die ausgehen...

Da das gewöhnliche 3-Stangen-Problem bei 64 Scheiben und einer
Zeit von einer Sekunde zum Umschichten einer Scheibe zur Lösung
bereits 584 Milliarden Jahre benötigt, ist das unerheblich

aber klar ist rekursion für so etwas sehr gut geeignet, da der Code aussagekräftiger wird.

Eben! Und rekursive Lösungen (Formeln) haben in der Regel auch einen sehr einfachen Aufbau;
deswegen mein Bauchgrummeln bei der bisherigen Lösung.

 

[Marco13]

In der Lösung von Frankyboy kam "der häßliche Teil" zwei mal vor. Es sollte, wie gesagt, wohl schon mit
f(n) = f(n-1) + 2 ^ floor(-0.5 + sqrt(0.25 + 2*(n-1))
getan sein.

Durch einen "Definitions-Kniff", der im geposteten Code angedeutet ist, könnte man es noch schöner schreiben, als

f(n) = f(n-1) + 2^floor(g(n-1))
mit g(n)^-1 = (n*n+n)/2

Dieses Invertieren von "h(n) = Sum(1...n){n} = (n*n+n)/2" bringt halt diese Kommazahlen und die Wurzel da rein :? Vielleicht könnte man die, da ja am Ende ein "floor" gemacht wird, auch noch irgendwie rausziehen...

Aber dass man da eigentlich so ein Summenzeichen drin hat, und das dann trotzdem so (vergleichsweise) einfach und schön geschlossen hinschreiben kann, ist doch schonmal was...

 

[Leroy42]

Aber dass man da eigentlich so ein Summenzeichen drin hat, und das dann trotzdem so (vergleichsweise) einfach und schön geschlossen hinschreiben kann, ist doch schonmal was...

Stimmt! Aber wer sagt uns, daß die Formel auch korrekt ist. ???:L

Eine leicht nachvollziehbare Anleitung wie bei der 3-Stangen-Problematik

1) Bringe n-1 Scheiben von A nach C
2) Bringe Scheibe N von A nach B
3) Bringe n-1 Scheiben von C nach B

die durch ihre Einfachheit leicht nachprüfbar ist und direkt
auf die Rekursionsformel

f(n) = f(n-1) + 1 + f(n-1) = 2*f(n-1) + 1 = 2^n - 1

führt, suche ich für 4-Stangen.

Aber eure Antworten sind schonmal sehr hilfreich!

 

[Marco13]

Naja, ehrlich gesagt hab ich nicht den Hauch eines Gedankens an den Algorithmus an sich verwendet :wink: sondern nur daran, eine Formel für die Zahlenfolge zu finden. Auf welcher Basis nun die Aussage steht, dies sei die Folge der kürzesten Lösungswege, weiß ich nicht.

["pause"]

Hab aber gerade mal bei Wikipedia geguckt: http://en.wikipedia.org/wiki/Tower_of_Hanoi - da gibt's ein paar Interessante Informationen dazu.

 

[Leroy42]

http://en.wikipedia.org/wiki/Tower_of_Hanoi - da gibt's ein paar Interessante Informationen dazu.

À propos 3 Stangen-Variante:

Non-recursive solution
...
- move the smallest disk to the peg it has not recently come from.
- move another disk legally (there will be one possibility only)

Woow! Diese Beschreibung der (nichtrekursiven) Lösung
finde ich ja endgeil! Kürzer gehts bestimmt nicht mehr!

 

[Frankyboy]

Aufgrund meines letzten Postings habe ich jetzt folgenden Algorithmus ausgearbeitet:

Bestimme k= floor(-0.5 + sqrt(0.25 + 2*n))

1. Bewege die kleinsten n − k Scheiben von Stab 0 auf 1, unter Benutzung aller 4 Stäbe.
2. Bewege die größten k Scheiben von Stab 0 auf 3, ohne Stab 1 zu benutzen.
3. Bewege die kleinsten n − k Scheiben unter Verwendung aller Stäbe von Stab 1 auf 3.

Das ergibt folgenden Code:

public static void hanoi4(int n,String q,String z, String h1, String h2) {
		if (n>1) {
			int k = (int) (-0.5 + Math.sqrt(0.25 + 2*n));
			hanoi4(n-k,q,h1,z,h2);
			hanoi3(n-k+1,n,q,z,h2);
			hanoi4(n-k,h1,z,q,h2);
		}
		else{
			System.out.println("Ziehe Scheibe "+n+" von "+q+" nach "+z);
		}
	} 
	
	public static void hanoi3(int n1,int n2,String q,String z, String h) {
		if (n2-n1>0) {
			hanoi3(n1,n2-1,q,h,z);
			System.out.println("Ziehe Scheibe "+n2+" von "+q+" nach "+z);
			hanoi3(n1,n2-1,h,z,q);
		}
		else{
			System.out.println("Ziehe Scheibe "+n2+" von "+q+" nach "+z);
		}
	}

Der Aufruf von

hanoi4(8,"1","4","2","3")

ergibt folgenden Output:

Ziehe Scheibe 1 von 1 nach 2
Ziehe Scheibe 2 von 1 nach 3
Ziehe Scheibe 3 von 1 nach 4
Ziehe Scheibe 2 von 3 nach 4
Ziehe Scheibe 1 von 2 nach 4
Ziehe Scheibe 4 von 1 nach 3
Ziehe Scheibe 5 von 1 nach 2
Ziehe Scheibe 4 von 3 nach 2
Ziehe Scheibe 1 von 4 nach 1
Ziehe Scheibe 2 von 4 nach 3
Ziehe Scheibe 3 von 4 nach 2
Ziehe Scheibe 2 von 3 nach 2
Ziehe Scheibe 1 von 1 nach 2
Ziehe Scheibe 6 von 1 nach 4
Ziehe Scheibe 7 von 1 nach 3
Ziehe Scheibe 6 von 4 nach 3
Ziehe Scheibe 8 von 1 nach 4
Ziehe Scheibe 6 von 3 nach 1
Ziehe Scheibe 7 von 3 nach 4
Ziehe Scheibe 6 von 1 nach 4
Ziehe Scheibe 1 von 2 nach 4
Ziehe Scheibe 2 von 2 nach 3
Ziehe Scheibe 3 von 2 nach 1
Ziehe Scheibe 2 von 3 nach 1
Ziehe Scheibe 1 von 4 nach 1
Ziehe Scheibe 4 von 2 nach 3
Ziehe Scheibe 5 von 2 nach 4
Ziehe Scheibe 4 von 3 nach 4
Ziehe Scheibe 1 von 1 nach 2
Ziehe Scheibe 2 von 1 nach 3
Ziehe Scheibe 3 von 1 nach 4
Ziehe Scheibe 2 von 3 nach 4
Ziehe Scheibe 1 von 2 nach 4

Also genau 33 Züge wie gewünscht.

Jetzt viel Spaß beim Ausprobieren

 

[Frankyboy]

Aus der Rekursionsformel kann man auch eine explizite Formel herleiten:

Sie lautet:

f(n) =(n - k(k-1)/2 -1) * 2^k +1

wenn k= floor(-0.5 + sqrt(0.25 + 2*n)) ist.

 

[SlaterB]

hmm, habe ich die Formel falsch abgeschrieben oder ist sie leicht falsch,
nicht übereinstimmend mit den Wertetabellen hier im Topic?

public class Test
{

    public static void main(String[] args)
        throws Exception
    {
        for (int i = 0; i < 20; i++)
        {
            double n = i;
            double k = Math.floor(-0.5 + Math.sqrt(0.25 + 2. * n));
            double f = (n - k * (k - 1) / 2. - 1) * Math.pow(k, 2.) + 1;
            System.out.println("i: " + i + ", " + f);
        }


    }
}


i: 0, 1.0
i: 1, 1.0
i: 2, 2.0
i: 3, 5.0
i: 4, 9.0
i: 5, 13.0
i: 6, 19.0
i: 7, 28.0
i: 8, 37.0
i: 9, 46.0
i: 10, 49.0
i: 11, 65.0
i: 12, 81.0
i: 13, 97.0
i: 14, 113.0
i: 15, 101.0
i: 16, 126.0
i: 17, 151.0
i: 18, 176.0
i: 19, 201.0

 

[Frankyboy]

Dein Code ist falsch.
Versuch es mal mit

Math.pow(2, k)

 

[SlaterB]

ein schlagendes Argument