Wie ändere ich eine Variable in jedem Schleifendurchlauf?

[Guest]

Hallo,

ich hätte da ein Problem. Aber zuerst füge ich besser an, dass ich ein ziemlicher Programmierneuling bin, also bitte nicht gleich kaputtlachen!

Es geht um die Implementierung eines Algorithmus, den ich mit Rekursion lösen wollte – das Problem ist nur, dass ich deren Zwischenschritte später wieder brauche.
Nun war meine Idee – aber ich habe nicht wirklich Ahnung, ob so was überhaupt geht – in der Rekursionsschleife immer eine neue Variable zu initialisieren. Und das wollte ich so bewerkstelligen (aber wie gesagt, ich weiß nicht, ob das geht), dass ich eine feste Variable, nennen wir sie mal q, mit meiner Zählvariable i konkateniere und die dann als neue Variable nehme. Geht das, und wenn ja, wie?
Meine zweite Idee war, erst einen Array zu deklarieren, bei dem ich dann in jeder Schleife den Zeiger um 1 erhöhe und da dann immer wieder eine neue Variable steht. Aber ich habe keine Ahnung, wie ich den machen soll.
Kann mir vielleicht jemand helfen?
Danke

Ines

 

[SlaterB]

> Und das wollte ich so bewerkstelligen (aber wie gesagt, ich weiß nicht, ob das geht), dass ich eine feste Variable, nennen wir sie mal q, mit meiner Zählvariable i konkateniere und die dann als neue Variable nehme. Geht das, und wenn ja, wie?

'eine feste Variable nehmen' geht in Java, was immer du damit meinst
'irgendwas mir irgendwas konkatenieren' düfrte auch gehen
'die dann als neue Variable nehmen' klingt auch nicht schlecht

was das ganze dann aber praktisch machen soll, was das mit Schleifen oder Rekursion zu tun haben könne, kann man aus deinem Kauderwelsch leider nicht rauslesen,
Beispiel, Ablauf?!

> und wenn ja, wie?
int q = 3
int i= 1;
q += i;
int neueVariable = q;

 

[Leroy42]

dass ich eine feste Variable, nennen wir sie mal q, mit meiner Zählvariable i konkateniere und die dann als neue Variable nehme. Geht das, und wenn ja, wie?

So, wie du dir das vorstellst, geht es nicht. Es können keine neuen
Variablennamen zur Laufzeit erstellt werden.

Ein Array zu benutzen ist eine Möglichkeit aber da hast du
die Schwierigkeit, dass du bereits vor dem Rekursionsaufruf
die Größe des Arrays wissen mußt. 🙁

Am besten du nimmst hierfür eine ArrayList die
dynamisch wachsen kann. Hier mal ein lauffähiges
Programm, das als Ergebnis eine rekursive Lösung des Türme von Hanoi - Problems auf der Konsole ausgibt.

import java.util.*;

public class Hanoi {
	private List<String> ergebnis;

	public void hanoi(int scheiben, int von, int nach, int hilfe) {
		if (scheiben > 0) {
			hanoi(scheiben-1, von, hilfe, nach);
			ergebnis.add("Scheibe "+scheiben+" von Stange "+von+" nach Stange "+nach);
			hanoi(scheiben-1, hilfe, nach, von);
		}
	}
	public void hanoi(int scheiben) {
		ergebnis = new ArrayList<String>();
		hanoi(scheiben, 1, 2, 3);
		for (String s : ergebnis)
			System.out.println(s);
	}
	public static void main(String[] args) {
		new Hanoi().hanoi(3);
	}
}

Ausgabe:

Scheibe 1 von Stange 1 nach Stange 2
Scheibe 2 von Stange 1 nach Stange 3
Scheibe 1 von Stange 2 nach Stange 3
Scheibe 3 von Stange 1 nach Stange 2
Scheibe 1 von Stange 3 nach Stange 1
Scheibe 2 von Stange 3 nach Stange 2
Scheibe 1 von Stange 1 nach Stange 2

Die ArrayList kannst du auch wahlweise als Parameter der
rekursiven Methode durchschleifen.

 

[Guest]

vielleicht sollte ich doch mal konkreter werden – dann hat evtl auch jemand noch eine andere idee, wie ich das lösen kann.
das programm soll den erweiterten euklidischen algorithmus beschreiben – der den größten gemeinsamen teiler zweier zahlen berechnet und zudem noch zwei zahlen s und t, die folgende gleichung erfüllen:
ggt(a,b) = s*a + t*b

das ganze kann man laut http://de.wikipedia.org/wiki/Erweiterter_Euklidischer_Algorithmus rekursiv lösen; in meinem horrormäßigen pseudo-c-java-mischmasch würde das in etwa so aussehen:

a=...;	// benutzerdefiniert bzw. random
b=...;
x=a;
y=b;
int i =1 ;
int r=1 ;
int q;

for (b!=0, i++){
q=a div b;
r= a mod b;
a=b;
b=r;
// hier sollte die neue variable – wie auch immer – deklariert werden
}

int s=1;
int t=0;
int u=0;

for (q != q0){ 	//q ist hier immer die jeweilige aktuelle variable der rekursion
		//q0 meint die anfangsvariable der schleife s.o.
q=q&(i--);	//persönlicher pseudocode für aktuelles q auf vorheriges q setzen
u=t;
t=s-q*t;
s=u ;
}
System.out.println("ggt:"++a++"="++s++"*"++x++"+"++t++"*"++y)

und noch etwas: auch wenn es euch nach diesem kauderwelsch wahrscheinlich in den fingern juckt, dieser “quellcode” dient nur dazu, euch zu zeigen, was ich meine – ich hoffe dazu ist er auch gut – er ist nicht zum korrigieren da. ich weiß, dass er völlig falsch im sinne jeder programmiersprache ist.

was den array angeht: sehe ich das richtig, dass du diesen dynamischen array in den zeilen 4,14 und 19 beschreibst? aber irgendwie kann ich das nicht ganz auf mein „programm“ übertragen...

 

[Leroy42]

horrormäßigen pseudo-c-java-mischmasch

Da hast du Recht! 😎

Poste doch mal ein Beispiel. Welche Ausgaben erwartest du denn
beispielsweise bei der Berechnung von ggT(8, 12);?

 

[Marco13]

Jo, eine angemessene Problembeschreibung wäre hier schonmal viel wert. Aber mal als Tipp ins blaue: Wenn du irgendwelche Werte aus der Rekursionstiefe n noch in Rekursionsstufe n+1 brauchst, kannst du sie einfach mit übergeben.

void rekursion(int n)
{
    if (n==0) return operation(n, 0);
    return operation(n, rekursion(n-1));
}

wird damit zu

void rekursion(int n, int prevResult)
{
    if (n==0) return operation(n, 0);
    int prevResult = computeResult(n);
    return operation(n, rekursion(n-1, prevResult));
}

Notfalls ist "prevResult" auch eine ArrayList, wo in jedem Schritt neue Werte eingefügt werden.

 

[Guest]

Bevor ich anfange, vergesst bitte, was ich vorhin verwirrenderweise über Rekursion geschrieben habe. Das Programm ist ganz und gar keine Rekursion - ich habe das fälschlicherweise behauptet, weil sich die Art des Algorithmus "Rekursive Variante" nennt. Es wird wohl vielmehr eine Iteration.

So, also jetzt mal ein Beispiel. Es fällt ein wenig größer aus, weil wenn ich 8 und 12 genommen hätte, könnte man mein Problem wohl eher schlecht erkennen - und ein Mittelding hab ich auf die Schnelle nicht gefunden. Ich hoffe, es ist diesmal verständlich.

Ich arbeite mit Schritten, damit man es besser nachvollziehen kann.

Normaler ggT nach Euklid: ggT(210,76)

(0)
a=210
b=76
q0=a div b= 210 div 76 = 2 => q0=2
r= a mod b= 210 mod 76=58
a=b=76
b=r=58

(1)
a=76
b=58
q1=76 div 58=1 => q1=1
r=76 mod 58=18
a=58
b=18

(2)
a=58
b=18
q2=3 =>q2=3
r=4
a=18
b=4

(3)
a=18
b=4
q3=4 =>q3=4
r=2
a=4
b=2

(4)
a=4
b=2
q4=2 =>q4=2
r=0
a=2
b=0

(5)
a=2
b=0

So, das wäre erst einmal der ggT - und zwar ist der im letzten von 0 verschiedenen Rest zu finden - das wäre r=2 in Schritt (3). Dann bestimmt man mit dem erweiterten Euklidischen Algorithmus die sog. Vielfachsummendarstellung, d.h. welche s und t die folgende Gleichung erfüllen:
ggT(a,b)=s*a+t*b
Dabei arbeitet man die Schritte immer genau rückwärts auf:
Hier wird mit dem Finden von s und t immer die Gleichung siehe oben gelöst. Das geschieht (außer im ersten Schritt - also (5)) immer folgendermaßen:
s=t(alt)
t=s(alt)-q(aktuell)*t(alt)
(alt) meint dabei das s bzw. t aus dem vorangegangenen Schritt, (aktuell) das q aus dem gerade bearbeiteten Schritt.

(5)
=> s=1, t=0
denn ggT(a,b)=2=s*a+t*b=2*1+0*0

(4)
s=t(alt)=0
t=s(alt)-q4*t(alt)=1-2*0=1
=>s=0, t=1

(3)
s=1
t=s(alt)-q3*t(alt)=0-4*1=-4
=>s=1, t=-4

(2)
s=-4
t=1-3(q2)*-4=13
=>s=-4, t=13

(1)
s=13
t=-4-1(q1)*13=-17
=>s=13, t=-17

(0)
s=-17
t=13-2(q0)*-17=47
=>s=-17, t=47


Aus den s und t von Schritt 0 erhält man nun:
2=ggT(210,76)=-17*210+47*76

Wie man hoffentlich sehen konnte, benötige ich, wenn ich den erweiterten EA ausführen will (also das unten), die q0 bis q4 von oben - allerdings weiß ich ja natürlich bei beliebigen a und b nicht, wie viele q ich brauche. Und genau das ist mein Problem. Deshalb wollte ich auch z.B. in jedem Schritt die Schrittnummer an das q "drankonkatenieren", was aber wohl nicht geht. Also wäre das mit dem dynamischen Array wohl die einzige realisierbare Möglichkeit und es wäre sehr nett, wenn mir mal jemand genau sagen könnte, wie das hierfür ungefähr auszusehen hat.

 

[SlaterB]

List q = new ArrayList();

q.add(irgendwas); // hat dann Index 0
q.add(irgendwas); // hat dann Index 1
q.add(irgendwas); // hat dann Index 2
q.add(irgendwas); // hat dann Index 3
q.add(irgendwas); // hat dann Index 4


während des ggt fügst du die Elemente ein wie sie kommen,
dann kannst du später darauf zugreifen,
a la q.get(4) // was bei dir q4 ist

mit Zahlen und Indexen solltest du bei einem dynamischen Verfahren wohl kaum arbeiten,
q.get(q.size()-1)
liefert das letzte, welches du dann entfernen solltest, um immer nur das letzte zu verwenden,

 

[Leroy42]

Das Programm ist ganz und gar keine Rekursion - ich habe das fälschlicherweise behauptet, weil sich die Art des Algorithmus "Rekursive Variante" nennt. Es wird wohl vielmehr eine Iteration.

Nein!
Ich habe den Artikel bei Wikipedia mal überflogen und sehe, dass die
rekursive Lösung wesentlich kürzer, eleganter und auch verständlicher wäre.

Leider habe ich jetzt keine Zeit, den rekursiven Algorithmus
selbst zu coden(*).

Ansonsten stimme ich dem vorherigen Post von SlaterB voll zu.

(*) Frei nach dem Spruch von Fermat: google: "wirklich wundervollen beweis" fermat
( 😎 )

 

[Gast]

ja danke das mit dem array dürfte wohl funktionieren. vielen dank für die hilfe!
ich sollte vllt anfügen, dass alle programme, die ich schreibe, normalerweise sehr kompliziert werden, wie man vllt schon sehen kann 😉
ich wette, man kann das problem sehr viel einfacher lösen, aber ich kann es eben nicht. irgendwann werde ich schon noch lernen, effizientere programme zu schreiben.

 

[Gast]

... und da ich wohl richtig vermute, dass ich als gast kein thema abhaken kann, darf irgendein moderator das thema jetzt abhaken 🙂

 

[Wildcard]

... und da ich wohl richtig vermute, dass ich als gast kein thema abhaken kann, darf irgendein moderator das thema jetzt abhaken 🙂

Wird prompt erledigt :wink:

 

[Leroy42]

irgendwann werde ich schon noch lernen, effizientere programme zu schreiben.

... und elegantere!

SCNR 😎

 

[krueml]

[...das jetzt angemeldet ist]

dümdümdüm.... 🙂

effizient geht ja meist mit elegant einher...

 

[krueml]

gut, eine frage, die mir gerade noch beim "programmieren" (oder was ich dafür halte) gekommen ist:

wenn ich das mit dem q.add() so mache - kann ich da mein i (welches den Schritt angibt) da so einsetzen, also
q.add(i)? oder muss ich da mein aktuelles q reinschreiben, also
q.add(q)?
das ist mir doch noch nicht ganz klar, wie ich das mache. letzteres gibt für mich noch mehr sinn, aber ich halte es auch nicht wirklich für richtig ???:L
irgendwie wird mir alles gerade wieder sehr viel unklarer....

 

[SlaterB]

q.add(q)
auf keinen Fall,

wenn du schon eine Variable q mit ner Zahl drin hast,
dann muss die Liste ebwn qList oder anders heißen,

qList.add(q)
klingt gar nicht schlecht,
bei int gibts noch das Problem, dass int nicht als Objekt in die Liste eingetragen wird,
falls du kein Autoboxing aktiv fast

wenn int also Probleme macht, dann speichere Integer.valueOf(int)

-----

was
q.add(i)
soll verstehe ich nicht,
genauso gut könntest du fragen, ob du eine Kartoffel in die Liste speichern kannst,
das ist so abwegig, da musst du erstmal das WARUM näher erklären