Hallo,
ich hätte mal eien Frage:
Mir ist beim Lesen einer anderen Frage hier (Die Frage mit dem links/rechts weg abweichen) dass ich eine bestimmte Art Aufgaben einfach nicht zu lösen im Stande bin:
Wenn ich bspw. wie bei der anderen Frage n Mal den Buchstaben "R" und n Mal den Buchstaben "L" habe
(n sei irgendeine ganze Zahl)
und alle Kombinationen dieser 2*n Buchstaben finden/auflsiten soll sodass aber bspw. wenn man von links nahc rechts diesen String durchgeht,
zu keinem Zeitpunkt mehr R als L gekommen sind.
Also mit n=3 wäre bspw. LLRLRR in Ordnung.
LRRLLR wäre hingegen nicht in Ordnung denn:
Gehen wir von links durch kommt erst ein L und dann aber 2 R.
wenn wir L +1 zuordnen , R -1 zuordnen und von links nach rechts durchgehen, stehen wir nahc 3 Zeichen bei
+1-1-1=-1 was <0 ist, also mehr R als L und das ist unzulässig.
Daher ist LRRLLR kein zulässiger String.
War jetzt ein Beispiel.
Frage wäre wie ich bspw. für n=3 die Kombinationen finde.
Primitive Vairante wäre, einfach ALLE Kombinationen aus 3 L und 3 R in nem Array oder so zu sammeln und dnan abr wieder alle zu kicken die die bedingung nicht erfüllen.
Kann man machen aber wenn wir bspw. n=50 haben, wird die Lsite schon extrem riesig.
was ja per se unnötig ist, so eine große Lsite zu haben um sie dann auf den bruchteil der "legalen" Strings wieder zusammenzuschrumpfen.
Aber wie findet man "klug" alle Strings?
Ich könnte mir da, bisher aber nur als grobe Idee, eine rekursive Funktion vorstellen, die das bewerkstelligen könnte irgendwie.
So in etwa, so grob der Gedanke (habe das gerade nach zig Woche nohne Javaprogrammieren gerade im Editor geschrieben, übernehme also null verantwortung für fehler)
Problem nur:
ist maxlength bspw. 2000 oder so, dann scheitert es, wie immer bei rekursion, an der relativ niedrigen maximalen rekursionstiefe.
rekursiv ist also nicht.
Explizit?
Aber wie?
fiele mir nur wieder ein, alle kombinationen der reihe nahc zu erzeugen, bei jeder ezreugten kombi zu gucken ob sie dne regeln entspricht und falls ja hinzufügen.
aber eine ecplizite variante, die erst gar nicht unnötig unzulässige kombinationen baut, die dann wieder geprüft und verworfen werden müssen, fällt mir nicht ein.
zumal mir auch kein guter Datentyp einfällt um überhaupt die "legalen" lösungen zu speichern, sodass da immer mehr dazu kommen können im laufe der suche.
Arraylist oder so vielleicht?
oder ein anderes Problem das im groben das selbe grundproblem für mich darstellt:
Es werde ein spiel gespielt wo jemand einen würfel wirft.
es wird so lange immer wieder gewürfelt bis derjenige (eine 5 würfelt oder die summe des letzten, 3.letzten und 5.letzten wurfes zusammen <7 ergibt).
es gäbe noch die einshcränkung dass maximal 20 mal gewürfelt wird, no matter what.
frage wäre nun alle möglichen würfelfolgen aufzulisten.
12345 wäre in der liste
162316 wäre da drin (weil hier 1+2+1<7 ist).
es gäbe auch sichelrich strings der länge 20 und auch kleinere, also alles bunt gemischt.
wie würde man das sinnvoll angehen?
ganz naiv könnte man, da ja maximal 20 würfe, ALLE komninationen aus zahlen 1-6 und bis zu 20 mal "ziehen" machen.
was aber eine unaussprechlich lange lsite werden würde (zu lang für java).
und dann würde man 95% der sachen rausschmeissen wieder.
also sehr ineffizient.
Wie würde man das klug lösen? (rekursion geht ja wegen rekursionstiefe nicht, wenns mal längere strings sein dürfen).
ich hätte mal eien Frage:
Mir ist beim Lesen einer anderen Frage hier (Die Frage mit dem links/rechts weg abweichen) dass ich eine bestimmte Art Aufgaben einfach nicht zu lösen im Stande bin:
Wenn ich bspw. wie bei der anderen Frage n Mal den Buchstaben "R" und n Mal den Buchstaben "L" habe
(n sei irgendeine ganze Zahl)
und alle Kombinationen dieser 2*n Buchstaben finden/auflsiten soll sodass aber bspw. wenn man von links nahc rechts diesen String durchgeht,
zu keinem Zeitpunkt mehr R als L gekommen sind.
Also mit n=3 wäre bspw. LLRLRR in Ordnung.
LRRLLR wäre hingegen nicht in Ordnung denn:
Gehen wir von links durch kommt erst ein L und dann aber 2 R.
wenn wir L +1 zuordnen , R -1 zuordnen und von links nach rechts durchgehen, stehen wir nahc 3 Zeichen bei
+1-1-1=-1 was <0 ist, also mehr R als L und das ist unzulässig.
Daher ist LRRLLR kein zulässiger String.
War jetzt ein Beispiel.
Frage wäre wie ich bspw. für n=3 die Kombinationen finde.
Primitive Vairante wäre, einfach ALLE Kombinationen aus 3 L und 3 R in nem Array oder so zu sammeln und dnan abr wieder alle zu kicken die die bedingung nicht erfüllen.
Kann man machen aber wenn wir bspw. n=50 haben, wird die Lsite schon extrem riesig.
was ja per se unnötig ist, so eine große Lsite zu haben um sie dann auf den bruchteil der "legalen" Strings wieder zusammenzuschrumpfen.
Aber wie findet man "klug" alle Strings?
Ich könnte mir da, bisher aber nur als grobe Idee, eine rekursive Funktion vorstellen, die das bewerkstelligen könnte irgendwie.
Java:
public class Test{
int maxlength=6;//=2*n
public String testmethode(String a){
if(a.length==6){
//a zu Ergebnisarray hinzufügen
}
if(/* a+"R" erfüllt Bedingung */){
testMethode(a+"R");
}
if(/* a+"L" erfüllt Bedingung */){
testMethode(a+"L");
}
}
}
So in etwa, so grob der Gedanke (habe das gerade nach zig Woche nohne Javaprogrammieren gerade im Editor geschrieben, übernehme also null verantwortung für fehler)
Problem nur:
ist maxlength bspw. 2000 oder so, dann scheitert es, wie immer bei rekursion, an der relativ niedrigen maximalen rekursionstiefe.
rekursiv ist also nicht.
Explizit?
Aber wie?
fiele mir nur wieder ein, alle kombinationen der reihe nahc zu erzeugen, bei jeder ezreugten kombi zu gucken ob sie dne regeln entspricht und falls ja hinzufügen.
aber eine ecplizite variante, die erst gar nicht unnötig unzulässige kombinationen baut, die dann wieder geprüft und verworfen werden müssen, fällt mir nicht ein.
zumal mir auch kein guter Datentyp einfällt um überhaupt die "legalen" lösungen zu speichern, sodass da immer mehr dazu kommen können im laufe der suche.
Arraylist oder so vielleicht?
oder ein anderes Problem das im groben das selbe grundproblem für mich darstellt:
Es werde ein spiel gespielt wo jemand einen würfel wirft.
es wird so lange immer wieder gewürfelt bis derjenige (eine 5 würfelt oder die summe des letzten, 3.letzten und 5.letzten wurfes zusammen <7 ergibt).
es gäbe noch die einshcränkung dass maximal 20 mal gewürfelt wird, no matter what.
frage wäre nun alle möglichen würfelfolgen aufzulisten.
12345 wäre in der liste
162316 wäre da drin (weil hier 1+2+1<7 ist).
es gäbe auch sichelrich strings der länge 20 und auch kleinere, also alles bunt gemischt.
wie würde man das sinnvoll angehen?
ganz naiv könnte man, da ja maximal 20 würfe, ALLE komninationen aus zahlen 1-6 und bis zu 20 mal "ziehen" machen.
was aber eine unaussprechlich lange lsite werden würde (zu lang für java).
und dann würde man 95% der sachen rausschmeissen wieder.
also sehr ineffizient.
Wie würde man das klug lösen? (rekursion geht ja wegen rekursionstiefe nicht, wenns mal längere strings sein dürfen).