| Programmieraufgaben Hier wird regelmäßig eine neue Programmieraufgabe gestellt, die dann gelöst werden soll und in Zusammenarbeit mit den Moderatoren auch besprochen werden kann. |
Diskussion: Türme von Hanoi im Forum Programmieraufgaben, in der Kategorie Code Kitchen; Anzeige Die Türme von Hanoi sind ein Spiel, welches vermutlich die meisten von euch schon kennen. Nun geht es darum, ...
![]() |
| | #1 (permalink) |
| Member of Honour ![]() Registriert seit: 02.10.01 ![]() Likes: 0 | Anzeige Die Türme von Hanoi sind ein Spiel, welches vermutlich die meisten von euch schon kennen. Nun geht es darum, ein Programm zu programmieren, welches dieses Spiel simuliert. Die Regeln des Spiels: Das Spiel "Türme von Hanoi" ist mit wenigen Sätzen beschrieben: Es gibt links einen Turm, der aus mehreren Scheiben besteht. Diese Scheiben sind unterschiedlich groß, die unterste ist am größten, die oberste am kleinsten. Ziel ist es nun, den Turm umzubauen, wobei keine große Scheibe auf einer kleinen liegen darf. Dazu gibt es neben dem Platz, an dem der Turm zum Schluss stehen soll, noch einen Ablageplatz: Code: [---]
[-----]
[-------]
[---------]
Startplatz Ablageplatz Ziel. Viel Spaß beim Coden! |
| | |
| | #2 (permalink) |
| Senior Member Registriert seit: 02.10.01 ![]() Likes: 0 | Falls dies einer Hinbekommt grafisch zu realisieren, dann würde ich das Programm gerne unter Habosoft.de.vu zum Download anbieten. Sehe nämlich leider keine möglichkeit das ich es selbst unter vb realisieren könnte. mfg. Flou |
| | |
| HaBOT | - Anzeige - |
| |
| | #3 (permalink) |
| Senior Member Registriert seit: 02.10.01 ![]() Likes: 1 | Ich hatte mal ne Grafische Variante unter VC++. Muss ich mal schaun wo die ist... Und dies ist die Sparvariante: Code: #include <unistd.h>
#include <iostream.h>
float counter=0;
void turmbewegung(char q, char a, char z,int n)
{
if (n==1)
{
cout<<\"Bewege die Scheibe von Turm \"<<q<<\" nach Turm \"<<z<<\".\n\";
sleep(1);
counter++;
}
else
{
turmbewegung(q,z,a,n-1);
turmbewegung(q,a,z,1);
turmbewegung(a,q,z,n-1);
}
}
void main (void)
{
// (c) 2003 by Tec
int n;
cout<<\"\nBitte geben Sie die gew\x81nschte H\x94he des Turms ein:\t\";
cin>>n;
turmbewegung('1','2','3',n);
cout<<\"\nDie Anzahl der ben\x94tigten Durchl\x84ufe betr\x84gt:\t\"<<counter<<\"!\n\n\";
return 0;
} |
| | |
| | #4 (permalink) |
| Registriert seit: 02.10.01 ![]() Likes: 0 | Hier mal meine Perl Version (dürfte sich in allen Sprachen sehr ähneln ):Code: $schritte=0;
$aufrufe=0;
sub hanoi{
++$aufrufe;
my($zahl,$S,$P,$Z)=@_;
if($zahl>0)
{
hanoi($zahl-1,$S,$Z,$P);
print \"Scheibe $zahl $S -> $Z\n\";
hanoi($zahl-1,$P,$S,$Z);
++$schritte;
}
}
print \"\n\tTurm von Hanoi\n\nS-Start P-Parkplatz Z-Ziel\n\";
print \"\nZahl der Scheiben eingeben:\";
$zahl=<>;
chomp $zahl;
hanoi($zahl,'S','P','Z');
print \"\nGeloest in $schritte Schritten\n$aufrufe Funktionsaufrufe\n\nEnter fuer weiter...\n\";
<>; |
| | |
| | #5 (permalink) |
| Registriert seit: 27.01.02 ![]() Likes: 0 | ok, meine variante, auch c++ aber n bissel bonziger ;P dazu muss ich noch sagen, dass ich den code zufälligerweise ohne wissen über diesen thread heut geschrieben hab, wir machen das thema rekursion grad in der schule. hab also nich einfach abgetippt oder so ;P Code: /* The Towers of Hanoi
**
** - | |
** --- | |
** ----- | |
** ------- | |
**
** A B C
**
**
** The goal of this game is to move the tower on A, which
** consists of n rings, to place B.
** Only one ring can be moved at a time.
** Only a smaller ring can be placed on a larger ring.
** C can be used as a 'buffer'
**
** The following program solves this problem in a recursive way.
**
** THERE IS NO COPYRIGHT OR OTHER CLAIMS WHATSOEVER
** FEEL FREE TO CHANGE, DISTRUBUTE, DO WHATEVER YOU LIKE
*/
#include <iostream.h>
// enum
enum site{ A='A', B='B', C='C'};
// function declarations
void MoveTower(int Height, site Start, site Target, site Helper);
int GetHeight();
// main function
int main()
{
MoveTower(GetHeight(), A, B, C);
return 0;
}
// recursive Move_Tower function
void MoveTower(int Height, site Start, site Target, site Helper)
{
if( Height == 1 )
cout << (char)Start << \" --> \" << (char)Target << \"\n\";
else
{
MoveTower(Height-1, Start, Helper, Target);
MoveTower(1, Start, Target, Helper);
MoveTower(Height-1, Helper, Target, Start);
}
}
// user input (tower height)
int GetHeight()
{
char cbuf[4];
long ibuf = 1;
cout << \"Please input a height [1..100] : \";
// repeat until a valid input was made
do
{
if( ibuf != 1 )
cout << \"Invalid Input, try again: \";
cin >> cbuf;
ibuf = atol(cbuf);
} while( ibuf < 1 || ibuf > 100 );
// just for cosmetic reasons
cout << endl;
return ibuf;
} |
| | |
| | #6 (permalink) | |
| Senior Member Registriert seit: 27.01.02 ![]() Likes: 1 | Zitat:
Code: program Hanoi;
uses crt;
var n:integer;
procedure Move(n:integer; Start,Ziel,Hilf:char);
begin
if n=1 then writeln(Start,'--->',Ziel);
else begin
Move(n-1,Start,Hilf,Ziel);
Move(1,Start,Ziel,Hilf);
Move(n-1,Hilf,Ziel,Start);
end;
end;
begin
write('WIeviele Scheiben? :');
readln(n);
Move(n,A,B,C);
end. | |
| | |
| | #7 (permalink) |
| Registriert seit: 02.10.01 ![]() Likes: 0 | Hab mich mal kurz hingesetzt und eine erste grafische Version (Windows) gemacht. Sie ist aber noch mit Vorsicht zu genießen (werde es vielleicht heut noch verbessern), denn sie kann während der Abarbeitung nicht unterbrochen werden und nimmt keine Nachrichten entgegen. Hier also die Rohfassung: Code: #include <windows.h>
#include <vector>
#include <string>
HWND hwnd;
using namespace std;
void hanoi(int zahl,vector<int>& start, vector<int> &platz, vector<int> &ziel)
{
if(zahl>0)
{
hanoi(zahl-1, start, ziel, platz);
int tmp=start.back();
start.pop_back();
ziel.push_back(tmp);
InvalidateRect(hwnd, NULL, TRUE);
UpdateWindow(hwnd);
Sleep(500);
hanoi(zahl-1, platz, start, ziel);
}
}
LRESULT CALLBACK WndProc (HWND, UINT, WPARAM, LPARAM) ;
int WINAPI WinMain (HINSTANCE hInstance, HINSTANCE hPrevInstance,
PSTR szCmdLine, int iCmdShow)
{
static TCHAR szAppName[] = TEXT ("Hanoi") ;
MSG msg ;
WNDCLASS wndclass ;
wndclass.style = CS_HREDRAW | CS_VREDRAW ;
wndclass.lpfnWndProc = WndProc ;
wndclass.cbClsExtra = 0 ;
wndclass.cbWndExtra = 0 ;
wndclass.hInstance = hInstance ;
wndclass.hIcon = LoadIcon (NULL, IDI_APPLICATION) ;
wndclass.hCursor = LoadCursor (NULL, IDC_ARROW) ;
wndclass.hbrBackground = (HBRUSH) GetStockObject (WHITE_BRUSH) ;
wndclass.lpszMenuName = NULL ;
wndclass.lpszClassName = szAppName ;
if (!RegisterClass (&wndclass))
{ // UNICODE-Compilierung ist die einzige realistische Fehlermöglichkeit
MessageBox (NULL, TEXT ("Programm arbeitet mit Unicode und setzt Windows NT voraus!"),
szAppName, MB_ICONERROR) ;
return 0 ;
}
hwnd = CreateWindow (szAppName, TEXT ("Turm von Hanoi by Nornagest"),
WS_OVERLAPPEDWINDOW,
CW_USEDEFAULT, CW_USEDEFAULT,
CW_USEDEFAULT, CW_USEDEFAULT,
NULL, NULL, hInstance, NULL) ;
ShowWindow (hwnd, iCmdShow) ;
UpdateWindow (hwnd) ;
while (GetMessage (&msg, NULL, 0, 0))
{
TranslateMessage (&msg) ;
DispatchMessage (&msg) ;
}
return msg.wParam ;
}
LRESULT CALLBACK WndProc (HWND hwnd, UINT message, WPARAM wParam, LPARAM lParam)
{
HDC hdc ;
static HWND hwndEdit, hwndStart;
PAINTSTRUCT ps ;
static vector<int> S,P,Z;
static char buf[4]={3,0,0,0};
static char* tmp=buf;
static int ges;
switch (message)
{
case WM_CREATE:
hwndEdit=CreateWindow(TEXT("edit"), NULL, WS_CHILD|WS_VISIBLE|WS_BORDER|ES_RIGHT,
0,0,30, 20,hwnd, (HMENU) 2, ((LPCREATESTRUCT) lParam)->hInstance, NULL);
hwndStart=CreateWindow(TEXT("button"), TEXT("Start"), WS_CHILD|WS_VISIBLE|BS_PUSHBUTTON,
35,0,100,20, hwnd, (HMENU) 3, ((LPCREATESTRUCT) lParam)->hInstance, NULL);
return 0 ;
case WM_COMMAND:
if(LOWORD(wParam)==3 && HIWORD(wParam)==BN_CLICKED)
{
if(!SendMessage(hwndEdit, EM_GETLINE, 0,(LPARAM)(LPCSTR) tmp))
MessageBox(hwnd, TEXT("Fehler"),TEXT("Hanoi"), MB_OK);
ges=atoi(tmp);
while(!S.empty())
S.pop_back();
while(!P.empty())
P.pop_back();
while(!Z.empty())
Z.pop_back();
for(int n=ges;n>0;n--)
S.push_back(n);
InvalidateRect(hwnd, NULL, TRUE);
UpdateWindow(hwnd);
Sleep(500);
hanoi(ges, S, P, Z);
}
return 0;
case WM_PAINT :
{
hdc = BeginPaint (hwnd, &ps) ;
vector<int>::iterator it=S.begin();
int i=0;
while(it!=S.end())
{
int tmp=*it;
Rectangle(hdc, 10+5*ges-5*tmp,30+10*ges-10*i, 10+5*ges+5*tmp, 20+10*ges-10*i);
i++;
it++;
}
i=0;
it=P.begin();
while(it!=P.end())
{
int tmp=*it;
Rectangle(hdc, 20+15*ges-5*tmp,30+10*ges-10*i, 20+15*ges+5*tmp, 20+10*ges-10*i);
i++;
it++;
}
i=0;
it=Z.begin();
while(it!=Z.end())
{
int tmp=*it;
Rectangle(hdc, 30+25*ges-5*tmp,30+10*ges-10*i, 30+25*ges+5*tmp, 20+10*ges-10*i);
i++;
it++;
}
EndPaint (hwnd, &ps) ;
return 0 ;
}
case WM_DESTROY :
PostQuitMessage (0) ;
return 0 ;
}
return DefWindowProc (hwnd, message, wParam, lParam) ;
} |
| | |
| | #8 (permalink) |
| Registriert seit: 02.10.01 ![]() Likes: 0 | ok hab nochn bissl gebastelt, is zwar nich perfekt, aber besser. Nun berechnet er den ablauf gleich zu Beginn. Deshalb ist das Program nur in dieser (relativ kurzen) Zeit nicht ansprechbar. Code: #include <windows.h>
#include <vector>
#include <list>
#include <string>
using namespace std;
HWND hwnd;
list<int> ablauf;
void hanoi(int zahl,int start, int platz, int ziel)
{
if(zahl>0)
{
hanoi(zahl-1, start, ziel, platz);
ablauf.push_back(start);
ablauf.push_back(ziel);
hanoi(zahl-1, platz, start, ziel);
}
}
LRESULT CALLBACK WndProc (HWND, UINT, WPARAM, LPARAM) ;
int WINAPI WinMain (HINSTANCE hInstance, HINSTANCE hPrevInstance,
PSTR szCmdLine, int iCmdShow)
{
static TCHAR szAppName[] = TEXT ("Hanoi") ;
MSG msg ;
WNDCLASS wndclass ;
wndclass.style = CS_HREDRAW | CS_VREDRAW ;
wndclass.lpfnWndProc = WndProc ;
wndclass.cbClsExtra = 0 ;
wndclass.cbWndExtra = 0 ;
wndclass.hInstance = hInstance ;
wndclass.hIcon = LoadIcon (NULL, IDI_APPLICATION) ;
wndclass.hCursor = LoadCursor (NULL, IDC_ARROW) ;
wndclass.hbrBackground = (HBRUSH) GetStockObject (WHITE_BRUSH) ;
wndclass.lpszMenuName = NULL ;
wndclass.lpszClassName = szAppName ;
if (!RegisterClass (&wndclass))
{ // UNICODE-Compilierung ist die einzige realistische Fehlermöglichkeit
MessageBox (NULL, TEXT ("Programm arbeitet mit Unicode und setzt Windows NT voraus!"),
szAppName, MB_ICONERROR) ;
return 0 ;
}
hwnd = CreateWindow (szAppName, TEXT ("Turm von Hanoi by Nornagest"),
WS_OVERLAPPEDWINDOW,
CW_USEDEFAULT, CW_USEDEFAULT,
CW_USEDEFAULT, CW_USEDEFAULT,
NULL, NULL, hInstance, NULL) ;
ShowWindow (hwnd, iCmdShow) ;
UpdateWindow (hwnd) ;
while (GetMessage (&msg, NULL, 0, 0))
{
TranslateMessage (&msg) ;
DispatchMessage (&msg) ;
}
return msg.wParam ;
}
LRESULT CALLBACK WndProc (HWND hwnd, UINT message, WPARAM wParam, LPARAM lParam)
{
HDC hdc ;
static HWND hwndEdit, hwndStart;
PAINTSTRUCT ps ;
static vector<int> P[3];
static char buf[4]={3,0,0,0};
static char* tmp=buf;
static int ges;
static list<int>::iterator sit;
switch (message)
{
case WM_CREATE:
hwndEdit=CreateWindow(TEXT("edit"), NULL, WS_CHILD|WS_VISIBLE|WS_BORDER|ES_RIGHT,
0,0,30, 20,hwnd, (HMENU) 2, ((LPCREATESTRUCT) lParam)->hInstance, NULL);
hwndStart=CreateWindow(TEXT("button"), TEXT("Start"), WS_CHILD|WS_VISIBLE|BS_PUSHBUTTON,
35,0,100,20, hwnd, (HMENU) 3, ((LPCREATESTRUCT) lParam)->hInstance, NULL);
return 0 ;
case WM_COMMAND:
if(LOWORD(wParam)==3 && HIWORD(wParam)==BN_CLICKED)
{
if(SendMessage(hwndEdit, EM_GETLINE, 0,(LPARAM)(LPCSTR) tmp))
{
ges=atoi(tmp);
while(!ablauf.empty())
ablauf.pop_back();
for(int i=0;i<3;++i)
while(!P[i].empty())
P[i].pop_back();
for(int n=ges;n>0;n--)
P[0].push_back(n);
InvalidateRect(hwnd, NULL, TRUE);
UpdateWindow(hwnd);
hanoi(ges, 0, 1, 2);
sit=ablauf.begin();
SetTimer(hwnd, 1, 500, NULL);
}
else
{
MessageBox(hwnd, TEXT("Fehler"),TEXT("Hanoi"), MB_OK);
buf[0]=3;
}
}
return 0;
case WM_TIMER:
{
if(sit!=ablauf.end())
{
int start=*sit;
sit++;
int ziel=*sit;
sit++;
int tmp=P[start].back();
P[start].pop_back();
P[ziel].push_back(tmp);
InvalidateRect(hwnd, NULL, TRUE);
UpdateWindow(hwnd);
}
else
{
while(!ablauf.empty())
ablauf.pop_back();
KillTimer(hwnd, 1);
}
return 0;
}
case WM_PAINT :
{
hdc = BeginPaint (hwnd, &ps) ;
for(int n=0;n<3;++n)
{
vector<int>::iterator it;
it=P[n].begin();
int i=0;
while(it!=P[n].end())
{
int tmp=*it;
Rectangle(hdc, 10+10*n+(5+10*n)*ges-5*tmp,30+10*ges-10*i, 10+10*n+(5+10*n)*ges+5*tmp, 20+10*ges-10*i);
i++;
it++;
}
}
EndPaint (hwnd, &ps) ;
return 0 ;
}
case WM_DESTROY :
PostQuitMessage (0) ;
return 0 ;
}
return DefWindowProc (hwnd, message, wParam, lParam) ;
} nochma edit: kleiner Fehler behoben |
| | |
| | #9 (permalink) |
| Hi. Diese Aufgabe war letztes Semester ne Übungsaufgabe bei uns... Hier also mal der SML-Code (falls SML überhaupt jemandem was sagt) Code: exception identity
datatype Stab = Eins | Zwei | Drei;
(* bestimmt den Stapel, der zur Zwischenablage verwendet wird *)
fun third(Eins,Zwei) = Drei |
third(Eins,Drei) = Zwei |
third(Zwei,Eins) = Drei |
third(Zwei,Drei) = Eins |
third(Drei,Eins) = Zwei |
third(Drei,Zwei) = Eins |
third(_,_) = raise identity;
(* Textuelle Darstellung der Stapel *)
fun toString(Eins) = "1" |
toString(Zwei) = "2" |
toString(Drei)= "3";
(* Textuelle Darstellung der Spielzuege *)
fun move2string(n,a:Stab,b:Stab) =
"Bringe Scheibe "^ Int.toString(n)^
" von Stapel "^(toString a)^
" nach Stapel "^(toString b)^".\n";
(* Hier sind die Typen links noetig, da evtl. mehrere toString
im Kontext vorhanden sind. *)
(* Idee: Um einen Stapel mit n Scheiben von a nach b zu
transportieren, verschiebe ich zun"achst die ersten n-1 Scheiben
auf eine Zwischenablage (siehe third), bringe die unterste Scheibe
(dh. Scheibe n) von Stapel a nach Stapel b. Anschliessend werden
die auf der Zwischenablage geparkten Scheiben auf Stab c gelegt *)
fun hanoiString(0,a,b) = "" |
hanoiString(n,a,b) = hanoiString(n-1,a,third(a,b))^
move2string(n,a,b)^
hanoiString (n-1,third(a,b),b);
(* Loesung der Aufgabe: Erzeugen des Textes und anschliessendes
Ausgeben *)
fun hanoi(n,a,b) = print (hanoiString(n,a,b)); | |
| | |
| | #10 (permalink) |
| Registriert seit: 04.12.03 ![]() Likes: 0 | Hoi, hab die Türme mal als Java-Applet schreiben müssen. Ist also auch grafisch ;-) Wenn Interesse besteht kann ichs anbieten. Ist aber sicher nicht perfekt, da es noch in meiner Anfängerzeit war. Gruß Thief |
| | |
| | #11 (permalink) |
| Registriert seit: 04.06.04 ![]() Likes: 0 | Hier noch eine einfache Version in JAVA Code: package Uebungen.u2004_06_04;
import com.herdt.util.*;
/**
* @author Prussak
*
*/
public class TuermeVonHanoi {
static long counter=0;
static void turmbewegung(char q, char a, char z, int n)
{
if (n==1)
{
System.out.println("Bewege die Scheibe von Turm " + q + " nach Turm " + z + ".");
counter++;
}
else
{
turmbewegung(q,z,a,n-1);
turmbewegung(q,a,z,1);
turmbewegung(a,q,z,n-1);
}
}
public static void main(String[] args) {
int n;
n=StdInput.readInt("Bitte geben Sie die gewünschte Höhe des Turms ein: ");
turmbewegung('1','2','3',n);
System.out.print("Die Anzahl der benötigten Durchläufe beträgt: " + counter + "!");
}
} |
| | |
| | #12 (permalink) |
| Registriert seit: 14.11.07 ![]() Likes: 0 | Hi leute hab das ganze mal probiert mit delphi zu lösen sieht bei mir so aus(siehe Anhang). Hab das ganze natürlich grafisch dargestellt, wer lust hat kann es ja mal ausprobieren und mir tipps geben. HAb auch das .exe Angehengt. Konnte das ganze Programm leider nicht angängen es ist viel zu groß, es hat 6 units, weil ich auch die steine und Ihre bewegungen grafisch dargestellt habe. Wenn ich Zeit habe werd ich das ganze auch in C++ Programieren. LG |
| | |
| | #13 (permalink) |
| Moderator ![]() Registriert seit: 30.03.04 ![]() Likes: 14 | Hallo, ihr müsst mal versuchen es Iterativ zu lösen: C++ Lösung nicht rekursiv |
| | |
| | #14 (permalink) |
| Registriert seit: 14.11.07 ![]() Likes: 0 | Entschuldigung aber was meinst du mit Iterativ ist das nicht das geliche oder ähnlich wie bei der Rekursion wo man wiederholt auf Datenstrukturen(Objekten, Datentypen) zugreift z.b. mit einer Schleife.... |
| | |
| | #15 (permalink) | |
| Moderator ![]() Registriert seit: 19.06.06 ![]() ![]() ![]() Likes: 52 | Zitat:
wenn möglich solltest du immer auf rekursion verzichten, da es bei größeren datenmengen sehr langsam wird. programmiere nur mal z.b. die fibonacci-zahlen rekursiv und iterativ, dann siehst du ganz schnell den unterschied | |
| | |
![]() |
| - Anzeige - | |
| |
| Themen-Optionen | |
| Ansicht | |
| |
Ähnliche Themen | ||||
| Thema | Autor | Forum | Antworten | Letzter Beitrag |
| Türme von Hanoi (grafisch) in Java | Olli Kern | Code Kitchen | 2 | 24.06.04 12:42 |