[JAVA]/[C++] Würfel Kombinatorik Problem! Alle hilfe gerne gesehen!

[thradriel]

[JAVA]/[C++] Würfel Kombinatorik Problem! Alle hilfe gerne gesehen!

Hi ich hab eine Aufgabe, bei der mir der funktionierende Gedanke fehlt.

Aufgabe:

-ich soll ein programm realisieren in java (c++ würde auch gehen.oder auch pseudo code)ich will es halt verstehen!
- n wird eingelesen n>=0 positive ganze zahl --> also int
- n beschreibt die Anzahl von gleichen Würfeln mit drei unterschiedlichen Seiten : Grün, Blau, Rot (ja es gibt keinen drei seiten würfel aber das ist nicht relevant)
-ich soll alle kombinationen ausgeben die es gibt. Reihenfolge spielt eine Rolle
-wichtiger Punkt es soll über eine rekursive methode realisiert und keine Schleifen verwendet werden


Am ende soll so etwas rauskommen:
Bsp. 2 Würfel:

Grün Grün
Grün Blau
Grün Rot
Blau Grün
Blau Blau
Blau Rot
Rot Grün
Rot Blau
Rot Rot

ich verrenne mich in sinnlosen aufrufen.

Das ganze soll natürlich auch für einen oder 3 oder mehr würfel funtionieren.

so ich hoffe ihr habt schlauere ideen als ich und könnt mir helfen

 

[bonzebonze]

AW: [JAVA]/[C++] Würfel Kombinatorik Problem! Alle hilfe gerne gesehen!

Und die Funktion darf nur den einen Parameter n haben?

Hier eine Idee, die aber 2 Parameter benötigt. Programmiersprache ist C++/CLI.
Die Methode ruft sich immer wieder selbst auf und verlängert die übergebenen Strings und gibt sie letztendlich aus.
Man könnte Show() noch überladen, dass man am Anfang keinen leeren String übergeben muss.

#include "stdafx.h"
using namespace System;

void Show(String^ farbe, int n)
{
	if(n > 0)
	{
		Show(farbe+"Gruen,", n-1);
		Show(farbe+"Blau,", n-1);
		Show(farbe+"Rot,", n-1);
	}
	else Console::WriteLine(farbe);
}

int main()
{
    Show("",3);
    Console::ReadKey(); //dass die Konsole erst auf Tastendruck schließt
}

Hier mit der Überladung:

#include "stdafx.h"
using namespace System;

void Show(String^ farbe, int n)
{
	if(n > 0)
	{
		Show(farbe+"Gruen,", n-1);
		Show(farbe+"Blau,", n-1);
		Show(farbe+"Rot,", n-1);
	}
	else Console::WriteLine(farbe);
}

void Show(int n)
{
	Show("", n);
}

int main()
{
    Show(3);
    Console::ReadKey(); //dass die Konsole erst auf Tastendruck schließt
}

 

[thradriel]

AW: [JAVA]/[C++] Würfel Kombinatorik Problem! Alle hilfe gerne gesehen!

also so wie ich es verstanden hab können es mehrere parameter sein. es wird halt nur n eingelesen!

 

[bonzebonze]

AW: [JAVA]/[C++] Würfel Kombinatorik Problem! Alle hilfe gerne gesehen!

Habe meinen Post aktualisiert.

 

[thradriel]

AW: [JAVA]/[C++] Würfel Kombinatorik Problem! Alle hilfe gerne gesehen!

wow danke! das über ein string zu machen war einfach nich in meinem kopf. Hab es super in Java bringen können.
Jetzt hab ich das auch besser mit den rekursiven methoden verstanden!

 

[joffal]

AW: [JAVA]/[C++] Würfel Kombinatorik Problem! Alle hilfe gerne gesehen!

Mal eine Frage, funktioniert das auch für große Werte von n? Würde nämlich vermuten, dass bei der rekursiven Methode irgendwann ein Stackoverflow kommt, was bei einer Schleife eigentlich nicht passieren sollte

 

[bingo88]

AW: [JAVA]/[C++] Würfel Kombinatorik Problem! Alle hilfe gerne gesehen!

Da vermutest du richtig. Wird n groß genug, knallt es bei rekursiven Aufrufen irgendwann.

 

[DarkMo]

AW: [JAVA]/[C++] Würfel Kombinatorik Problem! Alle hilfe gerne gesehen!

kann man auch gut "simulieren", indem man einfach mal ne abbruch bedingung vergisst

 

[bonzebonze]

AW: [JAVA]/[C++] Würfel Kombinatorik Problem! Alle hilfe gerne gesehen!

Mal eine Frage, funktioniert das auch für große Werte von n? Würde nämlich vermuten, dass bei der rekursiven Methode irgendwann ein Stackoverflow kommt, was bei einer Schleife eigentlich nicht passieren sollte

Groß ist relativ.

Die Funktion Show(int n) ruft sich im günstigsten Fall (n < 1) viermal selbst auf. Verallgemeinert ruft sie sich 3^n + 3^(n-1) mal auf.

Wenn es bei n<10 noch wenige KB sind, wächst der Speicherbedarf bei n<20 schon auf fast 1GB an.

Hier die Aufrufe (mit globaler Variable gezählt):

Anzahl Aufrufe bei n=1: 4
Anzahl Aufrufe bei n=2: 13
Anzahl Aufrufe bei n=3: 40
Anzahl Aufrufe bei n=4: 121
Anzahl Aufrufe bei n=5: 364
Anzahl Aufrufe bei n=6: 1093
Anzahl Aufrufe bei n=7: 3280
Anzahl Aufrufe bei n=8: 9841
Anzahl Aufrufe bei n=9: 29524
Anzahl Aufrufe bei n=10: 88573
Anzahl Aufrufe bei n=11: 265720
Anzahl Aufrufe bei n=12: 797161
Anzahl Aufrufe bei n=13: 2391484
Anzahl Aufrufe bei n=14: 7174453
Anzahl Aufrufe bei n=15: 21523360
Anzahl Aufrufe bei n=16: 64570081
Anzahl Aufrufe bei n=17: 193710244
Anzahl Aufrufe bei n=18: 581130733
Anzahl Aufrufe bei n=19: 1743392200

Bei n=20 hat es mir zu lange gedauert.