Übungsaufgabe Nr. 3

Übersicht

BlitzBasic

Beginners-Corner

	konstantin Betreff: Übungsaufgabe Nr. 3	Fr, Dez 10, 2004 16:53 Antworten mit Zitat
Die Türme von Hanoi Es geht um die Türme von Hanoi. Vielleicht kennen es einige von euch. Es ist ein Puzzle, das die Mönche in den Klöstern in Vietnam damals gespielt haben. Zitat: Das Puzzle hat drei Positionen (üblicherweise "Pflöcke", 1-3), auf denen Scheiben verschiedener Größe abgelegt werden. In der Anfangssituation liegen alle n Scheiben auf Position 1. Ziel ist es durch Bewegung einzelner Scheiben den gesamten Turm aus n Scheiben auf die Zielposition 2 zu bringen. Dabei dürfen immer nur einzelne Scheiben bewegt werden, und es darf nie eine größere auf einer kleineren Scheibe abgelegt werden. Bildlich kann man sich das also folgendermaßen vorstellen: Die Aufgabe Eure Aufgabe ist es nun, zu berechnen wieviele Züge man machen muss, um 20 Scheiben von Position 1 auf Position 2 zu bewegen. Dies ist sehr rechenaufwendig und ein 133MHz Rechner braucht dafür 6 Minuten. Lösungen könnt ihr mir per PN zukommen lassen. Ich bin mal gespannt, wer von euch zuerst auf eine Lösung kommt. (Ein kleiner Ansporn vielleicht: Dies ist eine der häufigsten Aufgaben, die man im Informatikunterricht in der Jgst. 12/13 vorgesetzt bekommt.)

konstantin

Betreff: Übungsaufgabe Nr. 3

Fr, Dez 10, 2004 16:53
Antworten mit Zitat

Die Türme von Hanoi

Es geht um die Türme von Hanoi. Vielleicht kennen es einige von euch. Es ist ein Puzzle, das die Mönche in den Klöstern in Vietnam damals gespielt haben.

Zitat:

Das Puzzle hat drei Positionen (üblicherweise "Pflöcke", 1-3), auf denen Scheiben verschiedener Größe abgelegt werden. In der Anfangssituation liegen alle n Scheiben auf Position 1.
Ziel ist es durch Bewegung einzelner Scheiben den gesamten Turm aus n Scheiben auf die Zielposition 2 zu bringen. Dabei dürfen immer nur einzelne Scheiben bewegt werden, und es darf nie eine größere auf einer kleineren Scheibe abgelegt werden.

Bildlich kann man sich das also folgendermaßen vorstellen:
user posted image

Die Aufgabe
Eure Aufgabe ist es nun, zu berechnen wieviele Züge man machen muss, um 20 Scheiben von Position 1 auf Position 2 zu bewegen. Dies ist sehr rechenaufwendig und ein 133MHz Rechner braucht dafür 6 Minuten.

Lösungen könnt ihr mir per PN zukommen lassen. Ich bin mal gespannt, wer von euch zuerst auf eine Lösung kommt.

(Ein kleiner Ansporn vielleicht: Dies ist eine der häufigsten Aufgaben, die man im Informatikunterricht in der Jgst. 12/13 vorgesetzt bekommt.)

	Rallimen Sieger des 30-EUR-Wettbewerbs	Fr, Dez 10, 2004 17:34 Antworten mit Zitat
Hallo, vielleicht wäre es besser wenn du das Ergebnis schon mal hier zeigst, natürlich nur was rauskommt bei sagen wir mal bei 15 Ringen!
[BB2D \| BB3D \| BB+]

Rallimen

Sieger des 30-EUR-Wettbewerbs

Fr, Dez 10, 2004 17:34
Antworten mit Zitat

Hallo,
vielleicht wäre es besser wenn du das Ergebnis schon mal hier zeigst,
natürlich nur was rauskommt bei sagen wir mal bei 15 Ringen!

[BB2D | BB3D | BB+]

	konstantin	Fr, Dez 10, 2004 17:59 Antworten mit Zitat
Nein.

konstantin

Fr, Dez 10, 2004 17:59
Antworten mit Zitat

Nein.

	Timo	Fr, Dez 10, 2004 18:45 Antworten mit Zitat
darf man immer nur den obersten bewegen? so ganz verstehe ich die Aufgabe noch nicht..

Timo

Fr, Dez 10, 2004 18:45
Antworten mit Zitat

darf man immer nur den obersten bewegen? so ganz verstehe ich die Aufgabe noch nicht..

	konstantin	Fr, Dez 10, 2004 19:00 Antworten mit Zitat
Du darfst immer nur eine der obersten Scheiben bewegen und nie eine größere auf eine kleinere legen.

konstantin

Fr, Dez 10, 2004 19:00
Antworten mit Zitat

Du darfst immer nur eine der obersten Scheiben bewegen und nie eine größere auf eine kleinere legen.

	Rallimen Sieger des 30-EUR-Wettbewerbs	Fr, Dez 10, 2004 19:12 Antworten mit Zitat
Beispiel : mit 3 Scheiben Code: [AUSKLAPPEN] [EINKLAPPEN] Start 1kg 2kg 3kg Turm1 Turm2 Turm3 Zug 1 2kg 3kg 1kg Turm1 Turm2 Turm3 Zug 2 3kg 1kg 2kg Turm1 Turm2 Turm3 Zug 3 1kg 3kg 2kg Turm1 Turm2 Turm3 Zug 4 1kg 3kg 2kg Turm1 Turm2 Turm3 Zug 5 1kg 3kg 2kg Turm1 Turm2 Turm3 Zug 6 2kg 1kg 3kg Turm1 Turm2 Turm3 Zug 7 1kg 2kg 3kg Turm1 Turm2 Turm3
[BB2D \| BB3D \| BB+]

Rallimen

Sieger des 30-EUR-Wettbewerbs

Fr, Dez 10, 2004 19:12
Antworten mit Zitat

Beispiel :
mit 3 Scheiben

Code: [AUSKLAPPEN]

Start
1kg
2kg
3kg
Turm1 Turm2 Turm3

Zug 1

2kg
3kg 1kg
Turm1 Turm2 Turm3

Zug 2

3kg 1kg 2kg
Turm1 Turm2 Turm3

Zug 3
1kg
3kg 2kg
Turm1 Turm2 Turm3

Zug 4
1kg
3kg 2kg
Turm1 Turm2 Turm3

Zug 5

1kg 3kg 2kg
Turm1 Turm2 Turm3

Zug 6
2kg
1kg 3kg
Turm1 Turm2 Turm3

Zug 7 1kg
2kg
3kg
Turm1 Turm2 Turm3

[BB2D | BB3D | BB+]

	Timo	Fr, Dez 10, 2004 19:18 Antworten mit Zitat
achso! Danke Rallimen! Hmm... ich glaub ich werds mal versuchen

Timo

Fr, Dez 10, 2004 19:18
Antworten mit Zitat

achso! Danke Rallimen! Hmm... ich glaub ich werds mal versuchen Wink

	wunderkind	Fr, Dez 10, 2004 21:44 Antworten mit Zitat
Eine nach der anderen vielleicht, du ungeduldiger Jungspund . https://www.blitzforum.de/viewtopic.php?t=7743

wunderkind

Fr, Dez 10, 2004 21:44
Antworten mit Zitat

Eine nach der anderen vielleicht, du ungeduldiger Jungspund Wink

.

https://www.blitzforum.de/viewtopic.php?t=7743

	wunderkind	Fr, Dez 10, 2004 22:00 Antworten mit Zitat
Okay, die Lösung ist fast schon banal . Stichwort geometrische Folgen. n := Anzahl der Steine.

wunderkind

Fr, Dez 10, 2004 22:00
Antworten mit Zitat

Okay, die Lösung ist fast schon banal Wink

. Stichwort geometrische Folgen.

user posted image

n := Anzahl der Steine.

	stfighter01	Fr, Dez 10, 2004 22:52 Antworten mit Zitat
lol ich denk mal wieder zu kompliziert. hab die folge vor mir aufgeschrieben und komm auf diese geniale 10mal so komplizierte version : an= 2^0 + 2^1 + ... + 2^(n-1) haut mir mit dem hammer auf den schädel. spass beiseite: wie wärs mit einer abwandlung der übung auf ein funktionsfähiges hanoi progamm, welches grafisch schritt f. schritt die lösung anzeigt? mfg stfighter
Denken hilft!

stfighter01

Fr, Dez 10, 2004 22:52
Antworten mit Zitat

lol ich denk mal wieder zu kompliziert.

hab die folge vor mir aufgeschrieben und komm auf diese geniale 10mal so komplizierte version Laughing

:
an= 2^0 + 2^1 + ... + 2^(n-1)

haut mir mit dem hammer auf den schädel.

spass beiseite:

wie wärs mit einer abwandlung der übung auf ein funktionsfähiges hanoi progamm, welches grafisch schritt f. schritt die lösung anzeigt?

mfg stfighter

Denken hilft!

	konstantin	Fr, Dez 10, 2004 22:56 Antworten mit Zitat
es ging mir hier eigentlich nicht darum, das bei google ne formel rausgesucht wird oder das man grafische darstellungen programmiert. es ist eine denkaufgabe, bei der man mal nachdenken sollte.

konstantin

Fr, Dez 10, 2004 22:56
Antworten mit Zitat

es ging mir hier eigentlich nicht darum, das bei google ne formel rausgesucht wird oder das man grafische darstellungen programmiert.
es ist eine denkaufgabe, bei der man mal nachdenken sollte.

	wunderkind	Fr, Dez 10, 2004 23:04 Antworten mit Zitat
@Alu Überheblich, gell. Soetwas muss nicht jeder bei Google suchen. Ich zumindest nicht. Und stfighter01 auch nicht, soweit ich das beurteilen kann. Mich würde hingegen mal interessieren, wieso der Rechner (s.o.) sechs Minuten mit dem Problem beschäftigt war!?! Welchen abwegigen Lösungsansatz hast du ihm denn beigepult?

wunderkind

Fr, Dez 10, 2004 23:04
Antworten mit Zitat

@Alu
Überheblich, gell. Soetwas muss nicht jeder bei Google suchen. Ich zumindest nicht. Und stfighter01 auch nicht, soweit ich das beurteilen kann.

Mich würde hingegen mal interessieren, wieso der Rechner (s.o.) sechs Minuten mit dem Problem beschäftigt war!?! Welchen abwegigen Lösungsansatz hast du ihm denn beigepult?

	konstantin	Fr, Dez 10, 2004 23:41 Antworten mit Zitat
wenn du die einzelnen Schritte simulierst, also die Scheiben nacheinander immerwieder hin und her verschiebst und nicht nur irgendeine Formel berechnest, sind es so viele Schritte, das er halt so lange braucht. Bei 100 Scheiben bräuchte ein Mensch z.B. ~2800 Jahre, um alle Schritte auszuführen.

konstantin

Fr, Dez 10, 2004 23:41
Antworten mit Zitat

wenn du die einzelnen Schritte simulierst, also die Scheiben nacheinander immerwieder hin und her verschiebst und nicht nur irgendeine Formel berechnest, sind es so viele Schritte, das er halt so lange braucht. Bei 100 Scheiben bräuchte ein Mensch z.B. ~2800 Jahre, um alle Schritte auszuführen.

	wunderkind	Fr, Dez 10, 2004 23:49 Antworten mit Zitat
Ein Mensch bräuchte bei 100 Scheiben sicher mehr als 2800 Jahre!!! Nutze einfach mal die einfache Formel oben und setze die 100 ein. Selbst wenn jede Sekunde einen Scheibe gelegt werden würde, wäre das Ende der Erde lange vorm Erreichen der Lösung eingetreten. Einfach mal den Taschenrechner bemühen.

wunderkind

Fr, Dez 10, 2004 23:49
Antworten mit Zitat

Ein Mensch bräuchte bei 100 Scheiben sicher mehr als 2800 Jahre!!! Nutze einfach mal die einfache Formel oben und setze die 100 ein. Selbst wenn jede Sekunde einen Scheibe gelegt werden würde, wäre das Ende der Erde lange vorm Erreichen der Lösung eingetreten. Einfach mal den Taschenrechner bemühen.

	konstantin	Fr, Dez 10, 2004 23:54 Antworten mit Zitat
oha

konstantin

Fr, Dez 10, 2004 23:54
Antworten mit Zitat

oha

	wunderkind	Fr, Dez 10, 2004 23:56 Antworten mit Zitat
Cooleres Problem dieser Art (inkl. Lösung): http://mathworld.wolfram.com/JosephusProblem.html

wunderkind

Fr, Dez 10, 2004 23:56
Antworten mit Zitat

Cooleres Problem dieser Art (inkl. Lösung): http://mathworld.wolfram.com/JosephusProblem.html

	Rallimen Sieger des 30-EUR-Wettbewerbs	Sa, Dez 11, 2004 9:37 Antworten mit Zitat
hier meine Lösung, hab zum vergleich noch die einfache dabeiBlitzBasic: [AUSKLAPPEN] [EINKLAPPEN] For t= 1 To 30 Print km(t) + \" \"+km1(t) Next WaitKey Function KM(n) For i=1 To n Moegl# = Moegl * 2 + 1 Next Return moegl End Function Function KM1(n) Return 2^n-1 End Function allerdings gehts nicht mehr richtig wenn ich moegl als integer deklariere! warum weis ich nicht! So jetzt habe ich mal eine Frage, bei 2^n -1 muß doch immer eine ungrade Zahl rauskommen, Oder? aber bei 2^25 -1 stimmt es nicht mehr
[BB2D \| BB3D \| BB+]

Rallimen

Sieger des 30-EUR-Wettbewerbs

Sa, Dez 11, 2004 9:37
Antworten mit Zitat

hier meine Lösung, hab zum vergleich noch die einfache dabeiBlitzBasic: [AUSKLAPPEN]

For t= 1 To 30
Print km(t) + \"     \"+km1(t)
Next
 WaitKey

Function KM(n)
	For  i=1 To n
        Moegl# =  Moegl * 2 + 1
	Next
    Return moegl
End Function

Function KM1(n)
	
    Return 2^n-1
End Function

allerdings gehts nicht mehr richtig wenn ich moegl als integer deklariere!
warum weis ich nicht!

So jetzt habe ich mal eine Frage, bei 2^n -1 muß doch immer eine ungrade Zahl rauskommen, Oder?

aber bei 2^25 -1 stimmt es nicht mehr

[BB2D | BB3D | BB+]

Zuletzt bearbeitet von Rallimen am Sa, Dez 11, 2004 10:24, insgesamt einmal bearbeitet

	stfighter01	Sa, Dez 11, 2004 10:18 Antworten mit Zitat
@rallimen wenn du als integer deklarierst und 30 scheiben verwendest bekommst du einen integeroverflow schau mal in der hilfe unter datentypen und sieh dir den bereich von interger an. mfg stfighter
Denken hilft!

stfighter01

Sa, Dez 11, 2004 10:18
Antworten mit Zitat

@rallimen

wenn du als integer deklarierst und 30 scheiben verwendest bekommst du einen integeroverflow
schau mal in der hilfe unter datentypen und sieh dir den bereich von interger an.

mfg stfighter

Denken hilft!

	Rallimen Sieger des 30-EUR-Wettbewerbs	Sa, Dez 11, 2004 17:10 Antworten mit Zitat
die Wertebereiche der einzelnen VarTypen sind mir bekannt! abgesehen davon kommt ein overflow erst bei 31 Scheiben! mit floats gehts ab 128 nicht mehr! da sollte man dann wenns genau sein soll auch eigene Routinen nehmen und BB nicht vertrauen, da bekannt ist das BB nicht sehr genau rechnen kann! an dem Beispiel kann man es sehr deutlich sehen... BlitzBasic: [AUSKLAPPEN] [EINKLAPPEN] For t#= 0.0 To 1.0 Step 0.01 Print T Next WaitKey versucht das mal...
[BB2D \| BB3D \| BB+]

Rallimen

Sieger des 30-EUR-Wettbewerbs

Sa, Dez 11, 2004 17:10
Antworten mit Zitat

die Wertebereiche der einzelnen VarTypen sind mir bekannt!

abgesehen davon kommt ein overflow erst bei 31 Scheiben!
mit floats gehts ab 128 nicht mehr!
da sollte man dann wenns genau sein soll auch eigene Routinen nehmen und BB nicht vertrauen, da bekannt ist das BB nicht sehr genau rechnen kann!
an dem Beispiel kann man es sehr deutlich sehen...
BlitzBasic: [AUSKLAPPEN]

For t#= 0.0 To 1.0 Step 0.01
Print T
Next
WaitKey

versucht das mal...

[BB2D | BB3D | BB+]

	Rallimen Sieger des 30-EUR-Wettbewerbs	Sa, Dez 11, 2004 23:14 Antworten mit Zitat
Hab jetzt mal ein proggi mit BB Plus erstellt! genaue Anzeige, keine Beschränkung auf integer oder Floats, da eigene Routinen! ca. 300kb http://people.freenet.de/ralli...vHanoi.exe Begrenzung eingebaut , max 9999 Ringe Speed auf jeden Fall schneller als 6 min bei 20 ringen BB kackt bei 25 Ringen ab (Version 2^n-1)
[BB2D \| BB3D \| BB+]

Rallimen

Sieger des 30-EUR-Wettbewerbs

Sa, Dez 11, 2004 23:14
Antworten mit Zitat

Hab jetzt mal ein proggi mit BB Plus erstellt!
genaue Anzeige, keine Beschränkung auf integer oder Floats, da eigene Routinen! Very Happy

ca. 300kb
http://people.freenet.de/ralli...vHanoi.exe

Begrenzung eingebaut , max 9999 Ringe

Speed auf jeden Fall schneller als 6 min bei 20 ringen Very Happy

BB kackt bei 25 Ringen ab (Version 2^n-1)

[BB2D | BB3D | BB+]

Übersicht

BlitzBasic

Beginners-Corner

Nach Oben

BlitzBasic Portal

Übungsaufgabe Nr. 3

Betreff: Übungsaufgabe Nr. 3