Türme von Hanoi mit Visualisierung
-
Guten Tag zusammen,
ich habe die Aufgabe bekommen ein Programm zur Lösung des Problems die Türme von Hanoi zu programmieren. Ich denke viele kennen die Aufgabe:
http://de.wikipedia.org/wiki/Türme_von_Hanoi#Zugfolgen_f.C3.BCr_kleine_T.C3.BCrmeDas ganze soll bis max. 12 Scheiben funktionieren und das ganze soll auch visualisiert werden. Also ich hab mir mal 3 Türmchen als char array erstellt und dargestellt. Dabei ist I einfach nur ein Strich und mit mehreren X werden die scheiben dargstellt.
Danach hab ich mich ein bisschen mit der Rekursion beschäftigt und mal probiert die Lösung mit dem Radoffschen Algorithmus durchzuführen.So die erste Visualisierung klappt. Das Aufrufen der Rekursion bewege() ebenfalls. Wenn ich die Türme danach anzeigen lasse sind auch alle Scheiben schön der größe nach auf dem rechten Stapel gelandet.
Jetzt zum Problem: Es ist auch gefordert, dass man jeden Schritt einzeln nachvollziehen können muss. Also: Eine Scheibe verschieben, warten bis eine Taste gedrückt wird und dann die nächste Scheibe verschieben. Ich hab versucht das ganze mal innerhalb der Rekursion auszugeben, allerdings klappt das nicht. Die Scheiben werden nicht richtig verschoben. Ich weis allerdings nicht genau woran das liegen könnte?
Ist eine Ausgabe innerhalb der Rekursion so einfach überhaupt möglich?
Es verwirrt mich halt, das es ohne Ausgabe nach jedem Schritt ja anscheinend Funktioniert. Vielleicht hat ja jemand eine Idee was der Fehler / die Fehler sein könnten oder worauf ich achten muss.
Ich stell den Code mal unten an und zwar so wie es den anschein hat, als würde es Funktionieren.
Danke für eure Tipps
Gruß Sven
#include <stdio.h> #include <stdlib.h> #include <conio.h> #include <string.h> #include "Utilities.h" void turmerzeugen(char *turm[], int anzscheiben); void zeigeturmlinks(char *turm[]); void zeigeturmmitte(char *turm[]); void zeigeturmrechts(char *turm[]); void verschiebe (char *von[], char *nach[]); void bewege(int anzscheiben, char *turmL[], char *turmM[], char*turmR[]); int main () { char *turml[15]; char *turmm[15]; char *turmr[15]; int i,k; int anzscheiben=3; char in; for(i=0;i!=15;i++) { turml[i]="I"; turmm[i]="I"; turmr[i]="I"; } turmerzeugen(turml,anzscheiben); system("cls"); zeigeturmlinks(turml); zeigeturmmitte(turmm); zeigeturmrechts(turmr); getch(); bewege(anzscheiben,turml, turmm, turmr); system("cls"); zeigeturmlinks(turml); zeigeturmmitte(turmm); zeigeturmrechts(turmr); getch(); getch(); return 0; } void turmerzeugen(char *turm[], int anzscheiben) { int i; for(i=14;i!=14-anzscheiben;i--) { if(i==14) turm[i]="XXXXXXXXXXXXXXXXXXXXXXXXX"; if(i==13) turm[i]="XXXXXXXXXXXXXXXXXXXXXXX"; if(i==12) turm[i]="XXXXXXXXXXXXXXXXXXXXX"; if(i==11) turm[i]="XXXXXXXXXXXXXXXXXXX"; if(i==10) turm[i]="XXXXXXXXXXXXXXXXX"; if(i==9) turm[i]="XXXXXXXXXXXXXXX"; if(i==8) turm[i]="XXXXXXXXXXXXX"; if(i==7) turm[i]="XXXXXXXXXXX"; if(i==6) turm[i]="XXXXXXXXX"; if(i==5) turm[i]="XXXXXXX"; if(i==4) turm[i]="XXXXX"; if(i==3) turm[i]="XXX"; } } void zeigeturmlinks(char *turm[]) { int i; for(i=0;i!=15;i++) { if(strlen(turm[i])==1) { _gotoxy(0,3+i); printf(" %s\n",turm[i]); } if(strlen(turm[i])==3) { _gotoxy(0,3+i); printf(" %s\n",turm[i]); } if(strlen(turm[i])==5) { _gotoxy(0,3+i); printf(" %s\n",turm[i]); } if(strlen(turm[i])==7) { _gotoxy(0,3+i); printf(" %s\n",turm[i]); } if(strlen(turm[i])==9) { _gotoxy(0,3+i); printf(" %s\n",turm[i]); } if(strlen(turm[i])==11) { _gotoxy(0,3+i); printf(" %s\n",turm[i]); } if(strlen(turm[i])==13) { _gotoxy(0,3+i); printf(" %s\n",turm[i]); } if(strlen(turm[i])==15) { _gotoxy(0,3+i); printf(" %s\n",turm[i]); } if(strlen(turm[i])==17) { _gotoxy(0,3+i); printf(" %s\n",turm[i]); } if(strlen(turm[i])==19) { _gotoxy(0,3+i); printf(" %s\n",turm[i]); } if(strlen(turm[i])==21) { _gotoxy(0,3+i); printf(" %s\n",turm[i]); } if(strlen(turm[i])==23) { _gotoxy(0,3+i); printf(" %s\n",turm[i]); } if(strlen(turm[i])==25) { _gotoxy(0,3+i); printf("%s\n",turm[i]); } } } void zeigeturmmitte(char *turm[]) { int i; for(i=0;i!=15;i++) { if(strlen(turm[i])==1) { _gotoxy(30,3+i); printf(" %s\n",turm[i]); } if(strlen(turm[i])==3) { _gotoxy(30,3+i); printf(" %s\n",turm[i]); } if(strlen(turm[i])==5) { _gotoxy(30,3+i); printf(" %s\n",turm[i]); } if(strlen(turm[i])==7) { _gotoxy(30,3+i); printf(" %s\n",turm[i]); } if(strlen(turm[i])==9) { _gotoxy(30,3+i); printf(" %s\n",turm[i]); } if(strlen(turm[i])==11) { _gotoxy(30,3+i); printf(" %s\n",turm[i]); } if(strlen(turm[i])==13) { _gotoxy(30,3+i); printf(" %s\n",turm[i]); } if(strlen(turm[i])==15) { _gotoxy(30,3+i); printf(" %s\n",turm[i]); } if(strlen(turm[i])==17) { _gotoxy(30,3+i); printf(" %s\n",turm[i]); } if(strlen(turm[i])==19) { _gotoxy(30,3+i); printf(" %s\n",turm[i]); } if(strlen(turm[i])==21) { _gotoxy(30,3+i); printf(" %s\n",turm[i]); } if(strlen(turm[i])==23) { _gotoxy(30,3+i); printf(" %s\n",turm[i]); } if(strlen(turm[i])==25) { _gotoxy(30,3+i); printf("%s\n",turm[i]); } } } void zeigeturmrechts(char *turm[]) { int i; for(i=0;i!=15;i++) { if(strlen(turm[i])==1) { _gotoxy(60,3+i); printf(" %s\n",turm[i]); } if(strlen(turm[i])==3) { _gotoxy(60,3+i); printf(" %s\n",turm[i]); } if(strlen(turm[i])==5) { _gotoxy(60,3+i); printf(" %s\n",turm[i]); } if(strlen(turm[i])==7) { _gotoxy(60,3+i); printf(" %s\n",turm[i]); } if(strlen(turm[i])==9) { _gotoxy(60,3+i); printf(" %s\n",turm[i]); } if(strlen(turm[i])==11) { _gotoxy(60,3+i); printf(" %s\n",turm[i]); } if(strlen(turm[i])==13) { _gotoxy(60,3+i); printf(" %s\n",turm[i]); } if(strlen(turm[i])==15) { _gotoxy(60,3+i); printf(" %s\n",turm[i]); } if(strlen(turm[i])==17) { _gotoxy(60,3+i); printf(" %s\n",turm[i]); } if(strlen(turm[i])==19) { _gotoxy(60,3+i); printf(" %s\n",turm[i]); } if(strlen(turm[i])==21) { _gotoxy(60,3+i); printf(" %s\n",turm[i]); } if(strlen(turm[i])==23) { _gotoxy(60,3+i); printf(" %s\n",turm[i]); } if(strlen(turm[i])==25) { _gotoxy(60,3+i); printf("%s\n",turm[i]); } } } void verschiebe (char *von[], char *nach[]) { int i,k; for(i=0;i!=15;i++) { if(strlen(von[i])>2) { for(k=14;k!=0;k--) { if(nach[k]=="I") { nach[k]=von[i]; von[i]="I"; k=1; } } i=14; } } } void bewege(int anzscheiben, char *turmL[], char *turmM[], char*turmR[]) { if(anzscheiben>0) { bewege(anzscheiben-1, turmL, turmR, turmM); verschiebe(turmL, turmR); bewege(anzscheiben-1, turmM, turmL, turmR); } }
-
Funktioniert das auch mit 1, 2 oder 4 Scheiben?
Ich steig da nicht ganz durch, aber ich vermute dass du einfach zweimal den kompletten Turm verschiebst.
Du musst zumindest überprüfen ob du die erste Scheibe zuerst auf den mittleren oder den rechten Stapel packst und ob du versuchst ein große Scheibe auf eine kleine zu packen.
Zudem solltest du dein ganzes Konzept nochmal überdenken. Du arbeitest mit Pointern auf char-Arrays. Die Pointer zeigen auf die Texte in der Funktion turmerzeugen.
Ist es nicht einfacher nur mit Zahlenwerten zu arbeiten? Dann entfällt das ganz strlen()-Geraffel.Reicht nicht eine zeigeturm(char *turm[], int pos) Funktion. Mit pos = 0 oder 30 oder 60?
-
Danke für die Atwort
Hab grad mit den Kumpel geschrieben und hat mir auch gesagt das vieles mist ist^^
Ich werde das mit den Funktionen mit zeigeturm mal nach deinem Vorschlag abändern, das spart schon jede Menge Zeilen. Er hat mir auch noch ein paar andere Tipps gegeben was ich verbessern könnte.
Das ganze Funktoniert bis jetzt aber auch mit 1,2 oder 4 Scheiben um deine Frage zu beantworten.
Vielleicht sollte ich erst mal etwas optimieren, damit das ganze für andere verständlicher wird und das ganze dann später nochmal posten?
Gruß Sven
-
Versuch mal die Scheiben erst bei der Ausgabe zu erzeugen.
Im ersten Versuch auch linksbündig. Also in einer Schleife soviel X oder XX drucken wie die Scheibe groß ist.XX
XXXX
XXXXXXDann kannst du in der Verschieb und Rechen-Funktion mit den Werten im Array arbeiten. Und nimm bitte kein *Turm[]
In main() nimmst du Turm[] und in den Funktionen *Turm.
-
Hey,
danke für die Tipps.
So bald ich Zeit habe werde ich versuchen das ganze mal umzusetzen und dann später einen etwas "besseren" und übersichtlicheren Code zu posten.
Gruß Sven
-
Du hast einen haufen doppelten Code. Das kannst du alles ziemlich vereinfachen, was maßgäblich zur Lesbarkeit deines Codes beiträgt. Z.b. die zeigeturmlinks Funktion kann so aussehen:
void zeigeturmlinks(char *turm[]) { int i; for(i=0;i!=15;i++) { int len = strlen(turm[i]); if(len <= 25 && len % 2) { char fmt[100]; _gotoxy(0,3+i); sprintf(fmt, "%%%ds%%s\n", (25-len)/2); printf(fmt, "", turm[i]); } } }edit: deine ganze zeige* Fktionen kannst du so schreiben:
void zeigeturm(char *turm[], int x) { int i; for(i=0;i!=15;i++) { int len = strlen(turm[i]); if(len <= 25 && len % 2) { char fmt[100]; _gotoxy(x,3+i); sprintf(fmt, "%%%ds%%s\n", (25-len)/2); printf(fmt, "", turm[i]); } } } void zeigeturmlinks(char *turm[]) { zeigerturm(turm, 0); } void zeigeturmmitte(char *turm[]) { zeigerturm(turm, 30); } void zeigeturmrechts(char *turm[]) { zeigerturm(turm, 60); }und wuups hast du dir 200 Zeilen Code erspart
-
Hallo zusammen,
ich bin jetzt mal dazu gekommen die Vorschläge umzusetzen.
Der Quellcode ist jetzt wirklich viel kürzer geworden.
thx@supertux wär nie auf die Idee gekommen die Formatierung so zu machen ^^
So nun wieder zu meinem eigentlichen Problem. Ich habe versucht das Problem rekursiv mit der Funktion bewege zu lösen. Wenn ich den Turm zeichne sind Anfangs alle Scheiben links. Nach dem Aufruf der Funktion und erneuter Ausgabe der Türme sind alle Scheiben der Größe nach in der Mitte(sie könnten auch auf dem rechten Turm landen, das ist egal).
Die Idee hinter bewege wurde uns vom Prof vorgegeben:
/// --------------------------------------------------------- /// /// A B C /// /// | | | /// # | | /// ### | | /// ##### | | /// ####### | | /// ######### | | /// ___________________________________________ /// /// -------------------------------------------------------- void towersOfHanoi(int rings,char cA,char cC,char cB) { if (rings == 1) { printf("Move from %c to %c\n",cA, cC); } else { towersOfHanoi( rings-1, cA, cB, cC ); towersOfHanoi( 1, cA, cC, cB ); towersOfHanoi( rings-1, cB, cC, cA ); } }Ich habe einfach mal versucht das ganze auf meinen Quellcode anzuwenden.
Scheinbar funktioniert es auch wenn ich die Türme anzeige, dann die Funktion bewege aufrufe und die Türme anschließend wieder anzeige.
Jetzt würde ich aber gerne das Bild jedes mal anzeigen, nachdem eine Scheibe verschoben wurde, damit die Schritte nachvollziehbar sind. Leider funktoniert das nicht so ganz wie ich mir das Vorstelle.
Mein Versuch war in Zeile 138/139 nochmals die türme mit showtowers anzuzeigen und das Programm mit getch() anzuhalten. Das klappt zwar, nur stimmen die Bilder die ich sehe nicht. Sprich es werden mal 2 Scheiben auf einmal verschoben, zumindest sieht es so aus.
Hat jemand eine Idee wie ich die einzelnen Schritte richig anzeigen kann?
Die Lösung muss auch nicht unbedingt rekursiv sein, falls jemand ne andere Idee hat.
Dir Türme sind übrigends zu einer Struktur geworden, da dies auch so gewünscht wird. Zusätzliche Variablen im Bezug auf die Türme sollte also kein Problem sein.
Danke für die Tipps
Gruß Sven
#include <stdio.h> #include <stdlib.h> #include <conio.h> #include <string.h> #include "Utilities.h" void turmerzeugen(char *turm[], int anzscheiben); void zeigeturm(char *turm[], int x); void showtowers(char *turmlinks[], char *turmmitte[], char *turmrechts[]); void verschiebe (char *von[], char *nach[]); void bewege (int anzscheiben,char *turmlinks[], char *turmrechts[], char *turmmitte[]); struct Tower { char *scheiben[15]; }; int main () { struct Tower towerA; struct Tower towerB; struct Tower towerC; int i,k; int anzscheiben=3; for(i=0;i!=15;i++) { towerA.scheiben[i]="I"; towerB.scheiben[i]="I"; towerC.scheiben[i]="I"; } turmerzeugen(towerA.scheiben, anzscheiben); showtowers(towerA.scheiben, towerB.scheiben, towerC.scheiben); getch(); bewege(anzscheiben,towerA.scheiben,towerB.scheiben,towerC.scheiben); getch(); return 0; } void turmerzeugen(char *turm[], int anzscheiben) { int i; for(i=14;i!=14-anzscheiben;i--) { if(i==14) turm[i]="XXXXXXXXXXXXXXXXXXXXXXXXX"; if(i==13) turm[i]="XXXXXXXXXXXXXXXXXXXXXXX"; if(i==12) turm[i]="XXXXXXXXXXXXXXXXXXXXX"; if(i==11) turm[i]="XXXXXXXXXXXXXXXXXXX"; if(i==10) turm[i]="XXXXXXXXXXXXXXXXX"; if(i==9) turm[i]="XXXXXXXXXXXXXXX"; if(i==8) turm[i]="XXXXXXXXXXXXX"; if(i==7) turm[i]="XXXXXXXXXXX"; if(i==6) turm[i]="XXXXXXXXX"; if(i==5) turm[i]="XXXXXXX"; if(i==4) turm[i]="XXXXX"; if(i==3) turm[i]="XXX"; } } void zeigeturm(char *turm[], int x) { int i; for(i=0;i!=15;i++) { int len = strlen(turm[i]); if(len <= 25 && len % 2) { char fmt[100]; _gotoxy(x,3+i); sprintf(fmt, "%%%ds%%s\n", (25-len)/2); //Bildet das Format für prtintf un berechnet die Leerzeichen von links printf(fmt, "", turm[i]); //Schreibt von links Leerzeichen und ab der passenden Stelle den string } } } void showtowers(char *turmlinks[], char *turmmitte[], char *turmrechts[]) { system("cls"); zeigeturm(turmlinks, 0); zeigeturm(turmmitte, 27); zeigeturm(turmrechts, 54); } void verschiebe (char *von[], char *nach[]) { int i,k; for(i=0;i!=15;i++) { if(strlen(von[i])>2) { for(k=14;k!=0;k--) { if(nach[k]=="I") { nach[k]=von[i]; von[i]="I"; k=1; } } i=14; } } } void bewege (int anzscheiben,char *turmlinks[], char *turmrechts[], char *turmmitte[]) { if(anzscheiben==1) { verschiebe(turmlinks,turmrechts); } else { bewege(anzscheiben-1,turmlinks,turmmitte,turmrechts); bewege(1,turmlinks,turmrechts,turmmitte); bewege(anzscheiben-1,turmmitte,turmrechts,turmlinks); } }
-
Da du unter Windows arbeitest, käme vielleicht eine plattformabhängige Lösung in Betracht:
#ifdef _WIN32 #include <windows.h> #endif .. #ifdef _WIN32 void Wait() { while(1) { if(GetAsyncKeyState(VK_SPACE)) return; Sleep(300); // Thread z.B. 300 ms schlafen legen, CPU entlasten } } #else void Wait() { // anders implementieren } #endifWait() kann zwischen den Aufrufen von bewege(..) aufgerufen werden und wartet so lange, bis die Leertaste (virtueller Tastencode VK_SPACE) gedrückt wurde.
-
Wo hast du denn die Parameter für showtowers() in 138/139 her?
Aus bewege() kannst du sie nicht nehmen, da beim rekursiven Aufruf die Parameter zyklisch vertauscht werden.
Aber an die Daten der Türme kommst du sonst nicht dran, da sie nicht global sind.
-
Hi,
also ich dachte da an so was:
void bewege (int anzscheiben,char *turmlinks[], char *turmrechts[], char *turmmitte[]) { if(anzscheiben==1) { verschiebe(turmlinks,turmrechts); showtowers(turmlinks, turmmitte, turmrechts); getch(); } else { bewege(anzscheiben-1,turmlinks,turmmitte,turmrechts); bewege(1,turmlinks,turmrechts,turmmitte); bewege(anzscheiben-1,turmmitte,turmrechts,turmlinks); } }allerdings leuchten mir deine Argumente ein. Ich bin das ganze nochmals Durchgegangen. Die Anzahl der Züge ist ja (2^n)-1, bei drei Scheiben also 7 Züge. Bei 3 Scheiben seh ich auch 7 Schritte nur durch das zyklische vertauschen landen bei der Ausgabe die Stapel an der falschen stelle.
Hat jemand ne Idee wie ich diese zyklische Vertauschung bei der Ausgabe umgehen kann oder sollte ich mich mal nach einer nicht rekursiven Lösung umschauen?
Ach ja: Globale Variablen wurden uns von unserem Prof verboten.
Danke für Tipps
Gruß Sven
-
Dann mach doch eine echte struct mit allen Türmen:
struct Tower { char *links[15]; char *mitte[15]; char *rechts[15]; };Die musst du dann aber an bewege() übergeben (am besten als Zeiger) und den übergibst du dann an zeigeturm().
Aber abgesehen davon ist deine Lösung eher ungewöhnlich.
Du arbeitest mit einem Array von Zeigern auf Strings.
Sinnvoller wäre es die Türme als einfaches Array zu bauen, unabhängig von der Ausgabe.
Also hast du pro Turm ein Feld. Der Inhalt wäre dann 0, 1, 2, ... für die Scheibengröße. Dann kannst du ohne dieses ganze strlen auskommen.
Zu Ausgabe:
sprintf(fmt, "%%%ds%%s\n", (25-len)/2); //Bildet das Format für printf und berechnet die Leerzeichen von links printf(fmt, "", turm[i]); //Schreibt von links Leerzeichen und ab der passenden Stelle den stringmacht bei len=10 : "%7s%s\n" das gibt einen Text mit der Mindestlänge 7 und danach einen beliebig langen Text (turm[i]) aus
bei %s geht aber auch "%7.7s": Das gibt einen Text mit Mindest- und Maximallänge 7 aus.
char xxx[] = "################################################################" printf("%7.7s%10.10s", "", xxx);ergibt " ##########"
Der entsprechende Formatstring wird dann so zusammengebaut:
sprintf(fmt, ""%%%d.%ds%%%d.%ds\n", (25-len)/2, (25-len)/2,len,len); //Bildet das Format printf(fmt, "", xxx);
-
Hallo zusammen,
danke für den Tipp Dirk. Ich hab das ganze mal kurz ausprobiert und funktioniert sehr gut. Allerdings hätte ich gerne an der "Spitze" des Turmes ein anderes Zeichen z.B. I
Werd mich aber nochmal genauer mit deinem Vorschlag auseinander setzen, sobald ich diese Woche mehr Zeit habe.
Mir ist auch etwas zu meinem Rekursionsproblem eingefallen.
void bewege (int anzscheiben,char *turmlinks[], char *turmrechts[], char *turmmitte[]) { if(anzscheiben==1) { verschiebe(turmlinks,turmrechts); } else { bewege(anzscheiben-1,turmlinks,turmmitte,turmrechts); bewege(1,turmlinks,turmrechts,turmmitte); bewege(anzscheiben-1,turmmitte,turmrechts,turmlinks); } }Normalerweise steht an der Stelle von verschiebe eine printf Anweisung.
printf("Verschiebe oberste Scheibe von %c nach %c!" , a ,c)
Wobei a der Stab links und c der Stab rechts ist und diese ja durch den zyklischen rekursiven Aufruf durchgetauscht werden. Ich könnte ja anstatt auf den Bildschirm wieder in ein array schreiben. Die Funktion würde dann alle Züge berechnen und die Lösung wäre in dem Array gespeichert. Anschließend gebe ich die einzelnen Schritte wieder aus mit Hilfe des Arrays.
Dafür würde Beispielsweise wieder ein string Array in Frage kommen und ich müsste dann nach den Buchstaben an den entsprechenden Stellen schauen. Je nach dem was dann dort steht rufe ich die Funktion verschiebe auf und verschiebe die Scheiben entsprechend.
Das ganze würde wohl auch mit einem 2 Diemsionalen int array gehen, wenn ich mein Programm auf "Zahlen" anpasse. Für Scheibengröße würde ich dann entsprechende Werte verwenden. z.b. keine scheibe=0, kleinste scheibe=1, größte Scheibe=12
Die Arrays müssten antürlich entsprechend groß sein da das ganze ja mit bis zu 12 Scheiben funktionieren soll. Damit ergeben sich ja (2^12)-1 = 4095 Züge.
Ich hoffe das ich diese/s Woche / Wochenende Zeit habe und weiter machen kann.
Ich werden den Beitrag, dann mit den neuen Resultaten aktualisieren, wenn ich so weit bin.
Vielen Dank für die bis jetzt eingegangenen Hilfestellungen
Gruß Sven
-
Allerdings hätte ich gerne an der "Spitze" des Turmes ein anderes Zeichen z.B. I
Da du schon selber was gemacht hast, hier mein 'quick and dirty' Versuch.
Da ist jetzt nicht elegant, aber vielleicht durchschaubar#define ANZAHL_SCHEIBEN 15 struct Tower { int l[ANZAHL_SCHEIBEN], m[ANZAHL_SCHEIBEN], r[ANZAHL_SCHEIBEN]; } Turm; void showtowers(struct Tower *turm) { // Gibt die 3Türme auf einmal aus // da ich kein gotoxy habe ;) int i; char fmt[200]; char xxx[] = "###############################################################"; char iii[] = "I"; // oder | char *s, *s1, *s2, *s3; // system("cls"); // system("clear"); for(i=ANZAHL_SCHEIBEN-1;i>=0;i--) // Bei mir ist die Ebene 0 unten { int len1 = turm->l[i]*2+1; // Scheibenbreite aufhübschen int len2 = turm->m[i]*2+1; // macht aus 1 -> 3, 2 -> 5 int len3 = turm->r[i]*2+1; s1 = s2 = s3 = xxx; if (len1 < 2) s1 = iii; // Spitze der Tuerme if (len2 < 2) s2 = iii; if (len3 < 2) s3 = iii; s = fmt; // Erklaerung siehe frueheres Post s += sprintf(s, "%%%d.%ds%%%d.%ds%%%d.%ds ", (25-len1)/2, (25-len1)/2,len1,len1, (25-len1)/2, (25-len1)/2 ); //Bildet das Format für prtintf un berechnet die Leerzeichen von links s += sprintf(s, "%%-%d.%ds%%-%d.%ds%%-%d.%ds ", (25-len2)/2, (25-len2)/2,len2,len2, (25-len2)/2, (25-len2)/2 ); //Bildet das Format für prtintf un berechnet die Leerzeichen von links s += sprintf(s, "%%-%d.%ds%%-%d.%ds\n", (25-len3)/2, (25-len3)/2,len3,len3 ); //Bildet das Format für prtintf un berechnet die Leerzeichen von links printf(fmt, "", s1, "", "", s2, "", "", s3); //Schreibt von links Leerzeichen und ab der passenden Stelle den string // printf("%s", fmt); //Schreibt von links Leerzeichen und ab der passenden Stelle den string } printf("\n\n\n"); // sleep(1); }
-
Hallo zusammen,
ich hatte heute Zeit mal ein paar hier vorgeschlagene Verbesserungen auszuprobieren und zu testen.
Ich habe auch einige Komentare eingefügt sodass ihr meine oft verwirrten Gedanken eventuell besser Verstehen könnt ^^
Hier der momentan aktuelle Code:
#include <stdio.h> #include <stdlib.h> #include <conio.h> #include <string.h> #include "Utilities.h" void zeigeturm(int *turm, int x);//zeigt einen Turm an un verschiebt ihn um x nach rechts void showtowers(int *turmlinks, int *turmmitte, int *turmrechts);//zeigt alle Türme nebeneinander an void verschiebe (int *von, int *nach);//verschiebt eine "Scheibe" von einem Turm auf einen anderen void bewege(int anzscheiben, int von, int nach, int ueber, char* loesung);//Soll Rekursiv die Schritte berechnen und un loesung speichern //struktur turm mit einem int array //kleinste scheibe = 1, größte scheibe=12, keine scheibe=0 //von oben nach unten z.B. 0 0 0 1 2 3 4 5 6 7 8 9 10 11 12 struct Tower { int wertigkeit[15]; }; int main () { //erstellen der Türme A B C von links nach rechts struct Tower towerA; struct Tower towerB; struct Tower towerC; //hier sollen die Lösungsschritte gespeichert werden char loesung[20][25]; int i,k,r; int anzscheiben=3; //anzahl der Scheieb noch fest eingegeben //in die gesamten Türme Nullen schreiben for(i=0;i!=15;i++) { towerA.wertigkeit[i]=0; towerB.wertigkeit[i]=0; towerC.wertigkeit[i]=0; } //Erzeugt einen turm A bei dem die unterste Scheibe immer die Größe 12 hat und die Göße //nach oben um -1 abnimmt for(i=14;i>14-anzscheiben;i--) { towerA.wertigkeit[i]=i-2; } /*Zur Array Konrolle ob die Werte richtig eingetragen wurden for(i=0;i<=14;i++) { printf("%i\n",towerA.wertigkeit[i]); } getch();*/ //Zeigt die Türme erstmals an showtowers(towerA.wertigkeit, towerB.wertigkeit, towerC.wertigkeit); getch(); //loesung mit "Leerzeichen" füllen for(i=0;i<=10;i++) { sprintf(loesung[i],""); } //Aufruf von bewege, die Lösungsschritte sollen in loesung gespeichert werden bewege(anzscheiben,1,3,2,&loesung[0][0]); //Ausgabe der einzelnen Lösungsschritte for(i=0;i<=10;i++) { printf("%s\n",loesung[i]); } getch(); return 0; } void zeigeturm(int *turm, int x) { int i; for(i=0;i!=15;i++) { int len = turm[i]*2+1; if(len <= 25 ) { char fmt[100]; char xxx[] = "################################################################"; _gotoxy(x,3+i); sprintf(fmt, "%%%d.%ds%%%d.%ds\n", (25-len)/2, (25-len)/2,len,len); printf(fmt, "", xxx); } } } void showtowers(int *turmlinks, int *turmmitte, int *turmrechts) { system("cls"); zeigeturm(turmlinks, 0); zeigeturm(turmmitte, 27); zeigeturm(turmrechts, 54); } void verschiebe (int *von, int *nach) { //sucht im turm "von" von oben nach unten nach einer Scheibe (Wert größer 0) //scht dann in turm "nach" von unten nach oben nach der ersten Stelle an der keine Scheibe mehr ist (Wert=0) //falls diese Stelle gefunden wurde, werden diese beiden Werte getauscht int i,k; for(i=0;i!=15;i++) { if(von[i]>0) { for(k=14;k!=0;k--) { if(nach[k]==0) { nach[k]=von[i]; von[i]=0; k=1; } } i=14; } } } //Soll die Lösungschritte "errechnen" und in loesung speichern void bewege(int anzscheiben, int von, int nach, int ueber, char* loesung) { if (anzscheiben > 0) { bewege(anzscheiben-1, von, ueber, nach, loesung); //Der Zeiger loesung müsste noch in der Rekursion verbogen werden sprintf(loesung,"Verschiebe %d --> %d !\n",von,nach); //damit jedes mal an eine Stelle von loesung geschrieben wird //printf ("verschiebe %d --> %d\n", von, nach); Leider weiß ich nicht genau wie ich das anstellen soll?? bewege(anzscheiben-1, ueber, nach, von, loesung); } } /*void bewege(int anzscheiben, int von, int nach, int ueber) { if (anzscheiben > 0) { bewege(anzscheiben-1, von, ueber, nach); So werden die Richtigen Schritte nacheinander printf ("verschiebe %d --> %d\n", von, nach); auf dem Bildschirm ausgegeben bewege(anzscheiben-1, ueber, nach, von); } }*/Die größte Veränderung ist das die Türme jetzt int arrays sind und keine char arrays mehr. Es können jetzt also direkt die Werte der einzelnen Scheiben verwendet werden. Dabei hat die Größte Scheibe den Wert 12, die kleinste den Wert 1 und keine Scheibe den Wert 0.
Ein Turm mit 4 Scheiben sieht also so aus (von oben nach unten):
0 0 0 0 0 0 0 0 0 0 0 9 10 11 12So weit dazu.
Jetzt habe möchte ich die Lösung mit Rekursion durchführen so wie in Zeile 153 bis 161. Jedoch möchte ich das ganze noch nicht auf dem Bildschirm ausgeben sondern in ein char array speichern. Nach dem Aufruf möchte ich dann das char array auswerten, also die Stellen(ist ja bekannt durch den index []) an denen steht welche Scheibe von wo nach wo und das mit der Funktion verschiebe anschließend druchführen.
Danach kann ich dann das Neue Bild der Türme ausgeben und zusätzlich den String, damit man sieht von wo nach wo eine Scheibe verschoben wurde und das ganze auch noch als Text lesen kann. Anschließend würde dann der nächste Schritt folgen.
Dachte dazu an so was wie ein array von zeigern die jeweils auf eine Zeichenkette zeigen. In dem sollen dann die einzelnen Schritte gespeichert werden.
Hier wieder zu meinem Problem:
Leider weis ich jetzt nicht genau wie ich den Zeiger loesung den ich an die Funktion bewege übergebe innerhalb der Rekursion verbiegen muss, sodass ich alle Schritte in der richtigen Reihenfolge erhalte. Der Funktion bewege Übergebe ich den ersten Zeiger der auf eine Zeichenkette zeigt (&loesung[0][0]).
Für weitere Tipps und Hinweise bin ich wie immer dankbar
Gruß Sven
-
Du kannst die Türme ja 16 Ebenen hoch machen. Diese 16. Ebene benutzt du aber nicht für deine Scheiben, sondern schreibst dort die Turmnummer oder 'A' 'B' 'C' oder 'L' 'M 'R'. Dann kannst du die auch nach bei der Ausgabe richtig zuordnen.
towerA.wertigkeit[15]=-1; //Negativ, damit von Scheibe unterscheidbar towerB.wertigkeit[15]=-2; towerC.wertigkeit[15]=-3;Für dein Protokoll: char loesung[20][25];
du brauchst bei n Scheiben 2n-1 Züge.Scheiben : Züge 1 : 1 2 : 3 3 : 7 4 : 15 5 : 31 14 : 16383Da kommst du mit 20 Zeilen nicht weit.
Da müsstes du dann aber wieder mit Zeigern auf Zeiger arbeiten.
Du kannst das aber auch in eine Datei schreiben oder mit
tvh.exe > tvh.login eine Datei Umleiten.
PS. Die übliche Schleifenbedingung in C ist nicht != sonder < oder >.
Bei for(i=0;i**!=15;i++) ist auch 16 != 15, aber auf 16, 17,... willst du ja auch nicht zugreifen. Sollte nicht vorkommen, aber ...
Daher for(i=0;i<**15;i++)
-
Hi Dirk,
danke für die schnelle Antwort.
Also ich denke ich hab verstaden was du mit den negativen Werten meinst. Der Wert an der 15 Stelle soll dann den Turm identifizieren.
z.B.
-1 = A
-2 = B
-3 = CNur wo soll ich dann die Funktion verschiebe aufrufen und wie wird das dann in die Rekursion eingebaut bzw. wo halte ich das Programm an für die einzelnen Schritte an?
Da die Funktion ja rekursiv ist und einmal aufgerufen sich immer wieder selbst aufruft und das anschließend von "innen" nach "außen" komplett aufgelößt wird.
Deswegen versteh ich halt (noch) nicht wie ich an meine Lösungsschritte ran komme bzw. wie ich diese in meinem array speichern kann?
Das mir ein Feld mit 20 Lösungschritten nicht weit reicht weis ich. Das sollte nur für den Anfang als Beispiel mit 3 Scheiben dienen, da reichen 20 schritte.
Das maximale in meinem Fall wären (2^12)-1 Schritte.Wenn du Zeit hast könntest du deinen Vorschlag nochmals etwas genauer erleutern.
Vielen Dank
Gruß Sven
PS: Das mit den for Schleifen weiß ich eigentlich, hab mir das aber leider mal am anfang so angewöhnt und jetzt ists etwas schwierig abzustellen^^
-
Du hattest doch die Vorgabe: (Bei mir funktioniert das)
void towersOfHanoi(int rings,char cA,char cC,char cB) { if (rings == 1) { // verschiebe(cC, cA); // ZeigeTurm(cA, cC, cB); printf("Move from %c to %c\n",cA, cC); } else { towersOfHanoi( rings-1, cA, cB, cC ); towersOfHanoi( 1, cA, cC, cB ); towersOfHanoi( rings-1, cB, cC, cA ); } }Vor dem printf rufst du dein verschiebe und showtowers auf.
(Davor, weil dein showtowers ein CLS macht.void showtowers(int *turmlinks, int *turmmitte, int *turmrechts) { // Jetzt ist egal wo links wirklich ist (und darum auch Zahlen) system("cls"); zeigeturm(turmlinks, (turmlinks[15]+1) * -27 ); // (-1 +1) * -27 = 0 zeigeturm(turmmitte, (turmmitte[15]+1) * -27 ); // (-2 +1) * -27 = 27 zeigeturm(turmrechts,(turmrechts[15]+1) * -27 ); // (-3 +1) * -27 = 54 // sleep(1); // Warten }Und wenn du das immer noch als Text aufheben willst musst du das mit der Verschiebe-Funktion machen. Kann auch eine neue Funktion sein.
Es gibt static Variablen. Diese verlieren den Wert nicht, wenn man ein Funktion verlässt.
void verschiebeText(von,nach) { static int akt_Zeile=0; printf("akt_Zeile = %d\n",q); akt_Zeile++; }
-
Hallo zusammen,
Hallo dirk,sorry das ich etwas länger nicht gemeldet habe, aber leider komm ich aus Zeitgründen immer nur ab und zu dazu, die hier gemachten Vorschlage auszuprobieren.
@ dirk also denk ich hab theoretisch verstanden wie die das Problem lösen willst, allerdings hat das bei mir nicht so richtig hin gehauen.
Deshalb hab ich nochmals meine Idee versucht, die ganzen Lösungsschritte in einem array zu speichern. Ich konnte auch einen kleinen Erfolg verbuchen. Allerdings hab ich momentan eine globale Variable in meiner Lösung(Z23).
Unterm Quellcode komme ich dann zu meinem Problem.
#include <stdio.h> #include <stdlib.h> #include <conio.h> #include <string.h> #include "Utilities.h" void zeigeturm(int *turm, int x);//zeigt einen Turm an un verschiebt ihn um x nach rechts void showtowers(int *turmlinks, int *turmmitte, int *turmrechts);//zeigt alle Türme nebeneinander an void verschiebe (int *von, int *nach);//verschiebt eine "Scheibe" von einem Turm auf einen anderen void bewege(int anzscheiben, int von, int nach, int ueber, char *loesung);//Soll Rekursiv die Schritte berechnen und un loesung speichern //struktur turm mit einem int array //kleinste scheibe = 1, größte scheibe=12, keine scheibe=0 //von oben nach unten z.B. 0 0 0 1 2 3 4 5 6 7 8 9 10 11 12 struct Tower { int wertigkeit[15]; }; char globloesung[20][25]; int main () { //erstellen der Türme A B C von links nach rechts struct Tower towerA; struct Tower towerB; struct Tower towerC; //hier sollen die Lösungsschritte gespeichert werden char loesung[20][25]; int i,k,r; int anzscheiben=3; //anzahl der Scheieb noch fest eingegeben //in die gesamten Türme Nullen schreiben for(i=0;i!=15;i++) { towerA.wertigkeit[i]=0; towerB.wertigkeit[i]=0; towerC.wertigkeit[i]=0; } //Erzeugt einen turm A bei dem die unterste Scheibe immer die Größe 12 hat und die Göße //nach oben um -1 abnimmt for(i=14;i>14-anzscheiben;i--) { towerA.wertigkeit[i]=i-2; } /*Zur Array Konrolle ob die Werte richtig eingetragen wurden for(i=0;i<=14;i++) { printf("%i\n",towerA.wertigkeit[i]); } getch();*/ //Zeigt die Türme erstmals an showtowers(towerA.wertigkeit, towerB.wertigkeit, towerC.wertigkeit); getch(); //loesung mit "Leerzeichen" füllen for(i=0;i<=10;i++) { sprintf(loesung[i],"test"); } //Aufruf von bewege, die Lösungsschritte sollen in loesung gespeichert werden bewege(anzscheiben,1,3,2,&loesung[0][0]); //Ausgabe der einzelnen Lösungsschritte for(i=0;i<=10;i++) { printf("%s\n",loesung[i]); } getch(); return 0; } void zeigeturm(int *turm, int x) { int i; for(i=0;i!=15;i++) { int len = turm[i]*2+1; if(len <= 25 ) { char fmt[100]; char xxx[] = "################################################################"; _gotoxy(x,3+i); sprintf(fmt, "%%%d.%ds%%%d.%ds\n", (25-len)/2, (25-len)/2,len,len); printf(fmt, "", xxx); } } } void showtowers(int *turmlinks, int *turmmitte, int *turmrechts) { system("cls"); zeigeturm(turmlinks, 0); zeigeturm(turmmitte, 27); zeigeturm(turmrechts, 54); } void verschiebe (int *von, int *nach) { //sucht im turm "von" von oben nach unten nach einer Scheibe (Wert größer 0) //scht dann in turm "nach" von unten nach oben nach der ersten Stelle an der keine Scheibe mehr ist (Wert=0) //falls diese Stelle gefunden wurde, werden diese beiden Werte getauscht int i,k; for(i=0;i!=15;i++) { if(von[i]>0) { for(k=14;k!=0;k--) { if(nach[k]==0) { nach[k]=von[i]; von[i]=0; k=1; } } i=14; } } } //Soll die Lösungschritte "errechnen" und in loesung speichern void bewege(int anzscheiben, int von, int nach, int ueber, char *loesung) { static int count=0; if (anzscheiben == 1) { //printf("Move from %i to %i\n",von, nach); sprintf(loesung[count],"Verschiebe %d --> %d !\n",von,nach); //Wenn ich hier globloesung[count] verwende gehts count++; } else { bewege(anzscheiben-1, von, ueber, nach,loesung); bewege( 1, von, nach, ueber, loesung ); bewege(anzscheiben-1, ueber, nach, von,loesung ); } }Wenn ich in Zeile 151 globloesung[count] verwende kann ich in main in der Zeile 81 mit globloesung[count] die einzelnen Schritte ausgeben. Damit habe ich die Lösung und kann diese Zeichenketten auswerten und demnach die Funktion verschiebe aufrufen.
Allerdings sind globale Variablen ja verboten.
Ich habe versucht das ganze als Zeiger zu übergeben, aber bekomme eine Fehlermeldung das ich an irgendeine Stelle (wohl ausserhalb des arrays) schreiben will.
Ich hab bei der Übergabe schon so ziemlich alles ausprobiert, aber ich komm einfach nicht drauf wie ich das ganze übergeben muss?
In der Funktion soll der Übergeben Parameter dann auch wieder mit loesung[count] verwendet werden können, da es so ja auch mit der globloesung[count] funktioniert hat.
Die Variable in main (Zeile 34) könnte auch verändert werden, wenn das erfoderlich ist. Ich müsste dann halt die Ausgabe (Zeile 81) und die Auswertung(noch nicht vorhanden) entsprechend anpassen.
Info: Ich benutze Visual Studio 2010 von Microsoft. Da geht so was in der Art nicht: void bewege(....; in x; int y; char loesung[int x][in y])
Das Array muss als Konstante übergeben werden.Falls jemand Ideen / Vorschläge hat wie ich die Parameterübergabe realisieren könnte danke ich schon mal für eine Antwort.
Gruß Sven
-
Da Problem ist die Übergabe des 2D Arrays loesung.
In bewege ist es ein 1D-Array und mit sprintf(loesung[count], ... sprichst du halt nur das count'e Zeichen an
Info: Ich benutze Visual Studio 2010 von Microsoft. Da geht so was in der Art nicht: void bewege(....; in x; int y; char loesung[int x][in y])
Das Array muss als Konstante übergeben werden.schon mal
void bewege(....; int x; int y; char loesung[20][25])probiert?
Ansonsten bist du doch gar nicht auf den Text "Verschiebe %d...." angewiesen.
Also pack nur die Zahlen in ein Array.int main () { .... //hier sollen die Lösungsschritte gespeichert werden char loesung[20]; .... //Aufruf von bewege, die Lösungsschritte sollen in loesung gespeichert werden bewege(anzscheiben,1,3,2,loesung); .. } void bewege(int anzscheiben, int von, int nach, int ueber, char *loesung) { static int count=0; if (anzscheiben == 1) { //printf("Move from %i to %i\n",von, nach); // sprintf(loesung[count],"Verschiebe %d --> %d !\n",von,nach); //Wenn ich hier globloesung[count] verwende gehts loesung[count] = von * 16 + nach; count++; } ...Bei der Auswertung kommst du mit
von = loesung[count] / 16; nach = loesung[count] % 16;an die Werte.
Dabei werden im Augenblick deine Structs aber nicht verändert.
Und zur Info: &loesung[0][0] ist das gleiche wie loesung
-
Hallo zusammen,
oh mann wieso komm ich denn nie auf die einfachen Lösungen??
Ich bin schon fast dran verzweifelt.
Das mit char loesung[20][25] funktioniert tatsächlich
Die Funktion sieht jetzt so aus:
void bewege(int anzscheiben, int von, int nach, int ueber, char loesung[20][25]) { static int count=0; if (anzscheiben == 1) { //printf("Move from %i to %i\n",von, nach); sprintf(loesung[count],"Verschiebe %d --> %d !\n",von,nach); //Wenn ich hier globloesung[count] verwende gehts count++; } else { bewege(anzscheiben-1, von, ueber, nach,loesung); bewege( 1, von, nach, ueber, loesung ); bewege(anzscheiben-1, ueber, nach, von,loesung ); } }und ich übergebe leosung in main.
Nochmals Vielen Dank DirkB für die tolle Hilfe!
Ich werde versuchen das Projekt bis nächste Woche weiter zu bringen, da noch verschiedene Funktinalitäten fehlen, wie ein kleines menue um verschiedene Optionen auszuwählen.
Ich denke allerdings das ich das weitgehend alleine schaffe
Ich werde, wenn ich brauchbare Resultate habe, den Quellcode nochmals posten, dann können es sich diejenigen die es interessiert mal anschauen was draus geworden ist.
Viele Grüße
Sven