Rekursion Wortlänge?
Es gibt Mengen A und B, wobei A alle lateinischen Kleinbuchstaben und B Zahlen von 0 bis 9 enthält. Es soll eine Rekursion aufgestellt werden, die die Anzahl der Wörter fn der Länge n >= 0 berechnet, wobei keine Ziffern aufeinanderfolgen dürfen. Ich hab irgendwie keine Idee wie ich das machen soll, indem ich auf vorherige Werte zugreife. Weiß jemand weiter?
3 Antworten
Die Anzahl von kürzeren Wörtern hilft allein nicht weiter. Wenn Du sie in
- a(n) := Anzahl der Wörter, die mit einem A enden
- b(n) := Anzahl der Wörter, die mit einem B enden
aufteilst, geht es einfacher. Und wenn man die Definition von a() in „die nicht mit einem B enden“ änderst, ist auch der Fall n==0 sauber definiert.
die Rekursion geht dann so:
- a(0)=1; a(n+1)=( a(n)+b(n) )*26 (alle Wörter können mit einem A erweitert werden)
- b(0)=0; b(n+1)=a(n) *10 (nur Wörter, die nicht mit einem B enden, können mit einem B erweitert werden)
In Python sieht das dann so aus:
def ab(n):
if n<=0:
assert n==0
return 1, 0
else:
a, b = ab(n-1)
return (a+b)*26, a*10
for i in range(10):
print( i, sum(ab(i)) )
Ausgabe:
0 1
1 36
2 1196
3 40456
4 1362816
5 45951776
6 1549078336
7 52223498496
8 1760571328256
9 59352964143616
wenn du alle Wörter suchst, die genau n (z. B. 5) Zeichen lang sind, dann geht das so:
int C;
int n; // vorgegebene Länge
void next(int i, bool wasZ) {
if (i==n) { C++; return; }
for (char j='a'; j<='z'; j++) next(i+1,false);
if (!wasZ) for (char j='1'; j<='9'; j++) next(i+1,true);
}
int main() {
n=5; C=0; next(0,false); printf("%d\n",C);
return 0;
}
Keine Ziffer ... also keine Zahl oder auch Buchstaben nicht aufeinanderfolgen?
Dann 2 Dinge
Erstens: die menge der möglichen Zeichen sind A + B + <nul> wobei <nul> bedeutet kein Zeichen.
Zweitens: die Rekursionsfunktion hat einen Aufrufparameter = gerade hinzugefügtes Zeichen (dieses darf dann nicht hinzugefügt werden wenn es eine Ziffer ist).
Das bisherige Wort muss natürlich auch übermittelt werden. Außerdem natürlich n, damit keine Wörter entstehen mit mehr Zeichen als n.