Methoden Methodenaufrufe zählen

[ErdmannWimmer]

Hallo Leute,
ich habe gerade ein Methode geschrieben die rekursiv ist, sich also immer wieder selber aufruft. Mein Problem ist, das ich einen Zähler einbauen möchte, der zählt ,wie oft der Algorithmus angewendet wurde:

[Java]
public class Tuerme {
public static void main(String[] args){
(...)
}

private static void bewege(int i,HanoiTurm a,HanoiTurm b,HanoiTurm c) {
if(i>0){
bewege(i-1,a,c,b);
c.push(a.top()); //das soll gezählt
a.pop(); //werden
bewege(i-1,b,a,c);
}
}
}
[/Java]

mit einer einfachen Variable geht das nicht, da sie ja bei jedem Aufruf initialisiert wird. Muss ich einen Zähler als Parameter mit übergeben? Oder What?

 

[rme]

Das mit dem Parameter wäre eine Möglichkeit, ja. Du könntest aber auch eine Klassenvariabe einführen und außerhalb zählen, d.h. eine static-Variable in der Klasse anlegen und diese hochzählen.

 

[ErdmannWimmer]

also mit der Klassenvariable kriege ich das irgendwie nicht hin, könntest du da ein Beispiel formulieren? Und wenn ich den Zaehler als Parameter übergebe, wie kann ich ihn dann ausgeben? in der Methode selber würde er dann ja bei jedem Aufruf ausgegeben werden, und in der main Methode ist er immer noch auf den Startwert gesetzt.

 

[rme]

Zur Verwendung von Klassenvariablen siehe hier: http://www.java-forum.org/java-basi...856-zugriff-package-struktur.html#post1001604

Bei der Variante mit Parametern: Du könntest der Methode einen Rückgabewert gegeben, d.h. sie könnte die Anzahl der Rekursionen zurückgeben, sodass du in main darauf zugreifen kannst. Dabei müsstest du allerdings darauf achten, dass du die Rückgaben der beiden Rekursionen speicherst und dann die Summe zurückgibst.

 

[ErdmannWimmer]

Da die Methode sich aber immer wieder selbst aufruft, kann ich darin doch gar nichts summieren, sie gibt ja dann bei jedem Aufruf etwas zurück und wird bei jedem Aufruf neu initialisiert.

 

[rme]

Sie gibt es an den Aufrufer zurück, der zählt zusammen und addiert 1 (für den eigenen Aufruf), gibt das wiederum an den Aufrufer zurück, der wieder 1 hinzuzählt ... bis irgendeiner die Gesamtsumme an main zurückgibt

 

[ErdmannWimmer]

Tut mir leid, wenn ich grade etwas schwer von Begriff bin:autsch: Mir brennt nur gerade der Helm, ich sitze da schon so lange vor und muss bald fertig werden :-D
Wenn ich den Zähler so als Parameter einbaue bekomme ich nur 1 zurück in die main-Methode...

private static int bewege(int i,HanoiTurm a,HanoiTurm b,HanoiTurm c,int zaehler) {
       if(i>0){
	   bewege(i-1,a,c,b,zaehler);
	   c.push(a.top());  
	   a.pop();          
	   bewege(i-1,b,a,c,zaehler);	   
       }
       return ++zaehler; //der Methodenaufrufzaehler wird um einen erhöht
    }

 

[rme]

Jeder Aufruf von bewege (du hast 2 davon) erzeugt eine Kette an rekursiven Aufrufen. Du nutzt die Anzahl der dort gemachten Aufrufe aber nicht. Die beiden Aufrufe von bewege geben auch jeweils eine Zahl von Unteraufrufen zurück, die musst du beide addieren, dann noch 1 hinzu und zurückgeben.

 

[ErdmannWimmer]

private static int bewege(int i,HanoiTurm a,HanoiTurm b,HanoiTurm c,int zaehler) {
	
       if(i>0){
	   zaehler=zaehler+bewege(i-1,a,c,b,zaehler);  
	   c.push(a.top());  //auf Stab c wird die oberste Scheibe von a gesetzt
	   a.pop();          //die oberste Scheibe wird gelöscht
	   zaehler=zaehler+bewege(i-1,b,a,c,zaehler);
       }
       return ++zaehler;
    }

da kommt -387008604(hab bestimmt nen überlauf der int Variable) raus. Das kann nicht stimmen. Ich weiß nicht, wie ich sonst die Rückgabewerte der rekursiven Methoden summieren soll:noe:

 

[rme]

Mit was startest du denn in main? Zeig mal das ganze, ausführbare Programm

 

[ErdmannWimmer]

Das ist das ganze Ding. Ich möchte, dass er mir einfach nur die benütigten Züge ausgibt, das kann doch nicht so kompliziert sein:rtfm::rtfm::rtfm::bloed:

class HanoiTurm {
    /*
     * jede Scheibe wird durch einen String dargestellt je laenger der String,
     * derst groesser ist die Scheibe in values werden somit die Scheiben
     * abgelegt
     */
    private String[] values;
//   position gibt die Position der obersten Scheibe an
    private int position;

//   Konstruktor(keine Scheibe vorhanden, Stabgroeße ist 1)
    public HanoiTurm() {
	position = -1;
	values = new String[1];
    }

//   Konstruktor(keine Scheibe vorhanden, Stabgroesse wird gesetzt)
    public HanoiTurm(int groesse) {
	position = -1;
	values = new String[groesse];
    }

//   gibt die max Anzahl an Scheiben auf dem Stab zurueck.
    public int maxSize() {
	return values.length;
    }

//   Gibt die oberste Scheibe zurück, falls sie nicht vorhanden ist
//   wird eine Fehlermeldung und null ausgegeben.
    public String top() {
	if (position != -1){
	    return values[position];
	}
	else {
	    System.out.println("Der Stab ist leer!");
	    return null;
	}
    }	
//    Die position wird um eins verringert, und stellt somit die verbleibende
//    oberste Scheibe da. Der zu entfernende String wird = null gesetzt.   
    public void pop() {
	if (position==-1) {
	    System.out.println("Keine Scheibe vorhanden");
	}
	else{
	    values[position]= "";
	    position--;
	}
    }
/*
      Es wird geprüft ob der Stab voll ist oder die Scheibe zu
      groß und eine entsprechende Fehlermeldung ausgegeben
      Ist die Scheibe kleiner als die vorhendene oder keine vor
      handen, wird eine neue eingefuegt.
*/      
    public void push(String neu) {
	if (position==values.length-1){
	    System.out.println("Der Stab ist voll");
	}
	if (position != -1 && neu.length() > values[position].length()){
	    System.out.println("Die Scheibe ist zu groß");
	}
	if(position ==-1||neu.length()<values[position].length()){
	    values[position+1]=neu;
	    position++;
	    
	}
    }
    
//   gibt die Position um eins erhöht wieder um die
//   Anzahl an vorhandenen Scheiben zu erhalten. 
    public int size() {
	return position+1;
    }
}

public class TuermeVonHanoi {
    public static void main(String[] args) {
	int groesse; 
	int a=0;
	int zaehler=0;
	groesse = Integer.parseInt(args[0]);
	
//	 Es werden drei neue staebe erzeugt.
	HanoiTurm stab1 = new HanoiTurm(groesse);
	HanoiTurm stab2 = new HanoiTurm(groesse);
	HanoiTurm stab3 = new HanoiTurm(groesse);
	System.out.println("Stabgroesse: " + stab1.maxSize());
	StringBuilder scheibe = new StringBuilder();
	
//	 Die erste Scheibe wird erzeugt und an stab1 uebergeben.
	for (int i = 0; i < groesse; i++) {
	    scheibe.append("/\\");    
	}	
	String scheibeReady =new String(scheibe);
	stab1.push(scheibeReady);
	
//       Die restlichen Scheiben werden erzeugt und an stab1 uebergeben.
	for (int i = 0; i < groesse - 1; i++) {  
	    int ende = (groesse*2)-a;
            int start = (groesse*2-2)-a;
	    scheibe.delete(start, ende);
	    a= a+2;
	    String scheibeReady2 =new String(scheibe);
	    stab1.push(scheibeReady2);    
	}
	zaehler= bewege(groesse, stab1, stab2, stab3,zaehler);
	System.out.println(zaehler);
	
    }
//   Der aus Wikipedia stammende rekursive Algorithmus wird in einer eigenen
//   Methode formuliert. Der Methode werden die Parameter der Scheibenanzahl 
//   und die drei staebe der Klasse HanoiTurm uebergeben.
    private static int bewege(int i,HanoiTurm a,HanoiTurm b,HanoiTurm c,int zaehler) {
	
       if(i>0){
	   zaehler=zaehler+bewege(i-1,a,c,b,zaehler);  
	   c.push(a.top());  //auf Stab c wird die oberste Scheibe von a gesetzt
	   a.pop();          //die oberste Scheibe wird gelöscht
	   zaehler=zaehler+bewege(i-1,b,a,c,zaehler);
       }
       return ++zaehler;
    } 
}

 

[rme]

Du zählst momentan jeden rekursiven Aufruf sehr oft mehrfach, weil du in jeder Rekursion erneut zum Zähler hinzuzählst.. man kann das recht leicht beheben, aber ich will dir nicht die Lösung verraten, weil du sonst das Prinzip der Rekursion nicht lernst. Mal dir mal auf, was die Rekursion macht und dann überleg dir, wie man das behebt