Türme von Hanoi

Indi · Jun 9, 2003

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.

Die Programmiersprache kann natürlich frei gewählt werden. Zu Programmieren ist ein Programm, das ein Spiel mit einstellbar vielen Steinen (zwischen 2 und 10) erlaubt. Dabei sollen die Anzahl der Bewegungen angezeigt und die einzelnen Bewegungen aufgelistet werden.

Viel Spaß beim Coden!

Flou · Jun 9, 2003

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

Tec · Jun 9, 2003

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;
}

Nornagest · Jun 10, 2003

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\";
<>;

Vielleicht setz ich mich ja mal hin und machs grafisch...

JoBbE · Jun 16, 2003

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;
}

Chris · Jun 16, 2003

Original von Jobbe
wir machen das thema rekursion grad in der schule

Bin auch in dem Kurs...

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.

Nornagest · Jun 21, 2003

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) ;
}

Nornagest · Jun 21, 2003

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) ;
}

edit: list dürfte für ablauf effizienter sein
nochma edit: kleiner Fehler behoben

Matzeone · Jun 28, 2003

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));

Thief · Dez 7, 2003

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

fwp · Jun 15, 2004

Version in Java

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 + "!");
	}
}

Cyber_Puma · Apr 23, 2008

Delphi lösung

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

Elderan · Apr 23, 2008

Hallo,
ihr müsst mal versuchen es Iterativ zu lösen:

#include <iostream>
using namespace std;
int main()
{
int n, x;

cout << "Anzahl scheiben: " << endl;
cin >> n;

for (x=1; x < (1 << n); x++)
cout << "Lege Scheibe von " << (x&x-1)%3 << " nach " << (((x|x-1)+1)%3) << endl;
}

Cyber_Puma · Apr 23, 2008

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....

lightsaver · Apr 23, 2008

Original von Cyber_Puma
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....

http://de.wikipedia.org/wiki/Rekursion

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

Cyber_Puma · Apr 23, 2008

Ok danke hab den Unterschied bemerkt.

Trotzdem ist es in dem fall richtig weil die Aufgabenstellung es hier so verlangt, aber ich hab kapiert was du meinst.

LG

CDW · Apr 23, 2008

programmiere nur mal z.b. die fibonacci-zahlen rekursiv und iterativ, dann siehst du ganz schnell den unterschied

Immer dieses Rekursionbashing

. Es gibt genug Algorithmen, die entweder gar nicht (dabei wird der Stack "mit in die Prozedur" genommen oder anders simuliert) oder nur mit viel Mühe auf iterativ umgeschrieben werden können - Parsing, Baumoperationen (Balansierung, Suche(?) ) Backtracking usw. Ist leider schon ein Jährchen her, so dass ich nicht mehr die Beispiele im Kopf habe - das Problem ist nur, dass Rekursion "ganz doof" beigebracht wird (sinnloser Einsatz wie z.B die naive Fibonacci Berechnung) und daher immer etwas negatives daran haftet.

Bps Fibonacci: nur weil die mathematische Definition rekursiv ist, muss man die ja nicht 1:1 übernehmen. Denn

Code:

public static long fib(int a){
  if (a==1||a==2) return 1;
  else return fib(a-1)+fib(a-2);
}

wird 2^a mal aufgerufen (ok, besser gesagt, Fibonacci Wachstum ist expoteniell und lässt sich glaube ich für größere Sachen recht gut mit n^k vorhersagen, hab jetzt aber keine Lust danach zu suchen

). Bei der iterativen Umsetzung hat man aber einen komplett anderen Ansatz - man beginnt am Anfang der Folge und geht immer Zahl um Zahl durch - wohl weil die andere Methode iterativ schwer umsetzbar wäre

)
Man vergleicht also Äpfel mit Birnen um dann festzustellen, dass Rekursion schlecht ist.

jedenfalls, Fibonacci rekursiv:

Code:

static  long fib(int a, long aktuell, long vorher)
	{   
	   long temp=aktuell;
	   aktuell=aktuell+vorher;
	   vorher=temp;
	   if (a>3) return fib(a-1, aktuell, vorher);
	   return aktuell+vorher;
	}

(Sonderfall für die erste Fibonaccizahl wurde nicht berücksichtigt

)
definiert man vorher/aktuell so:

Code:

{
long aktuell=0; long vorher=1;

static  long fib(int a)
	{   
	   long temp=aktuell;
	   aktuell=aktuell+vorher;
	   vorher=temp;
	   if (a>3) return fib(a-1);
	   return aktuell+vorher;
	}
}

ist vielleicht nicht so ganz elegant, der Overhead gegenüber der iterativer Umsetzung ist aber minimal

Elderan · Apr 23, 2008

Hallo,
Die iterative Lösung der Fib.-Zahlen ist schon besser. Möchte man große Fibonacci Zahlen rekursiv berechnen, selbst mit einer verbesserten rekursiven Formeln, kann dies zu erheblichen Problemen führen. Vermutlich erhält man dann irgendwann die Meldung, dass der Stack voll sei (+Programm bricht), da bei jedem Funktionsaufruf die entsprechenden Zeiger auf den Stack gelegt werden müssen.

Verwendet man stattdessen eine normale Schleife, lassen sich eigentlich problemlos beliebig große Fibonacci-Zahlen berechnen, ohne gefahr zu laufen, dass einem der Stack explodiert.

Auch wenn der Speicher/Stack u.ä. vernachlässigt werden könnte, wäre die iterative Variante schneller.
Bei der rekursive Funktion habe ich min. zwei Sprünge, einmal in die Funktion und einmal wieder heraus.
Bei der iterativen Formel habe ich aber pro Durchlauf nur einen Sprung + 1 Sprung für die Abbruchbedingung.
D.h., rekursiv muss ich doppelt so oft springen wie bei der iterativen Variante, und Sprünge verbrauchen extrem viel Zeit.

Aber ansonsten stimmt es, viele Algorithmen lassen sich extrem schön rekursiv lösen (z.B. alle Dateien in einem Ordner inkl. Unterordner auflisten (also Bäume durchlaufen)) und die iterative Variante macht bei diesen kaum/keinen Sinn und wirkt nur unheimlich aufbeläht. Kommt immer drauf an.

das Problem ist nur, dass Rekursion "ganz doof" beigebracht wird (sinnloser Einsatz wie z.B die naive Fibonacci Berechnung) und daher immer etwas negatives daran haftet.

Oder das Standardbeispiel Fakultät berechnen: n!

Code:

int fak(int n) {
  if(n <= 0) return 1;
  else  return n*fak(n-1)
}

Da fragt man sich auch, warum man sowas nicht per Schleife macht.

CDW · Apr 23, 2008

Mir ist beim Essen eine viel schönere rekursive Fibonacciform eingefallen

:

static long fib(int a, long aktuell, long vorher)
{
if (a>2) return fib(a-1, aktuell+vorher, aktuell);
return aktuell+vorher;
}

aufruf: fib(10,0,1);

Ansonsten - meistens geht es doch darum, den Code lesbar zu lassen und nicht die letzen ns rauskitzeln und dafür irgendwelche Fehler in der Umsetzun zu übersehen

z.B hier bei Fibonacci: bevor der Stack abraucht, bekommt man schon zig mal einen Überlauf von long&Co - ist also immer eine Abwägungssache.

BTW: ich muss gerade an eine Mathestudentin denken, die in ihrem Zulassungsprojekt (DBS), um an das vorletze Datum mit einem zugehörigen Eintrag zu kommen sich rekursiv durch die ganze Tabelle gehangelt hat (die SQL Anfrage+bisschen Javacode sahen dafür ganz elegant aus

) - und den armen, schwächlichen (und wohl etwas mies konfigurierten) DB2 "Versuchsserver" ganz alleine blockierte. Ärgerlich für alle, die ihre Projekte vor der Abgabe noch testen wollten

nuki · Jun 21, 2011

Hey leute
kann mir jemand sagen wie ich das auf C programmieren kann?? :-S
ich verzweifle schon seit über ner Woche... ich komm einfach nicht weiter...

Türme von Hanoi

Member of Honour

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0