Knobelt mal schön los… ist nicht sooo schwer, wenn man die Lösung mal herausgefunden hat…
**Wieviele Zahlen zwischen 1 und 1'000'000 inklusive haben die Quersumme 13?**
( Quersumme(724) = 7 + 2 + 4 = 13 )
Knobelt mal schön los… ist nicht sooo schwer, wenn man die
Lösung mal herausgefunden hat…Wieviele Zahlen zwischen 1 und 1’000’000 inklusive
haben die Quersumme 13?
Einen wunderschönen guten Morgen!
–> 8232
warum? QSums (100001,13)=8232
int QSums (int limit,int value)
{ int i,k,sum,cnt;
char s[20];
for (i=0,cnt=0;i
Erst mal Brute Force
Hallo,
zunächst ist die Anzahl der Zahlen zwischen 1 und 1.000.000, die als Quersumme 13 haben, identisch mit der Anzahl der Zahlen zwischen 0 und 999.999, die als Quersumme 13 haben, denn weder 1.000.000 noch 0 hat die Quersumme 13 (es kommt also nichts hinzu und es geht nichts verloren). Damit wird das Problem „handlicher“. Eine Zahl zwischen 0 und 999.999 läßt sich als:
100.000*a5+10.000*a4+1.000*a3+100*a2+10*a1+a0
darstellen mit ai Element aus {0,…,9}. Eine Lsg. muß der Nebenbedingung
a5+a4+a3+a2+a1+a0=13
genügen. Wir untersuchen jetzt auf wieviel Arten man die 13 als Summe von 2,3,4,5,6 Summanden darstellen kann, wobei Summen, die durch Vertauschung von Summanden ineinander übergehen durch einen Repräsentanten dargestellt und Summanden mit Wert 0 ausgelassen werden:
9+4, 8+5, 7+6: 3*(6*5)= 90 Moeglichkeiten
9+3+1, 8+4+1, 8+3+2, 7+5+1, 7+4+2, 6+5+2, 6+4+3: 7*(6*5*4)= 840 Moeglichkeiten
9+2+2, 7+3+3, 6+6+1, 5+5+3, 5+4+4: 5*(6*5*4/2)= 300 Moeglichkeiten
7+3+2+1, 6+4+2+1, 5+4+3+1: 3*(6*5*4*3)= 1080 Moeglichkeiten
9+2+1+1, 8+3+1+1, 8+2+2+1, 7+4+1+1, 6+5+1+1, 6+3+3+1, 6+3+2+2, 5+5+2+1, 5+4+2+2, 5+3+3+2, 4+4+3+2: 11*(6*5*4*3/2)= 1980 Moeglichkeiten
7+2+2+2, 4+3+3+3, 4+4+4+1: 3*(6*5*4*3/2/3)= 180 Moeglichkeiten
6+3+2+1+1, 5+4+2+1+1, 5+3+2+2+1, 4+3+3+2+1: 4*(6*5*4*3*2/2)= 1440 Moeglichkeiten
7+2+2+1+1, 5+3+3+1+1, 4+4+3+1+1, 4+4+2+2+1: 4*(6*5*4*3*2/2/2)= 720 Moeglichkeiten
8+2+1+1+1, 7+3+1+1+1, 6+4+1+1+1, 6+2+2+2+1, 4+3+2+2+2: 5*(6*5*4*3*2/2/3)= 600 Moeglichkeiten
5+5+1+1+1, 3+3+3+2+2: 2*(6*5*4*3*2/2/2/3)= 120 Moeglichkeiten
9+1+1+1+1, 3+3+3+3+1, 5+2+2+2+2: 3*(6*5*4*3*2/2/3/4)= 90 Moeglichkeiten
4+3+2+2+1+1: 6*5*4*3*2*1/2/2= 180 Moeglichkeiten
5+3+2+1+1+1: 2*(6*5*4*3*2*1/3/2)= 120 Moeglichkeiten
6+2+2+1+1+1, 5+2+2+2+1+1, 4+4+2+1+1+1, 4+3+3+1+1+1, 3+3+2+2+2+1, 3+3+3+2+1+1: 6*(6*5*4*3*2*1/2/3/2)= 360 Moeglichkeiten
7+2+1+1+1+1, 6+3+1+1+1+1, 5+4+1+1+1+1, 4+2+2+2+2+1: 4*(6*5*4*3*2*1/4/3/2)= 120 Moeglichkeiten
8+1+1+1+1+1, 3+2+2+2+2+2: 2*(6*5*4*3*2*1/5/4/3/2)= 12 Moeglichkeiten
also ingesamt 8232 Moeglichkeiten.
Gruss
Enno
Jetzt ein wenig geschickter …
Hallo,
man kann die Anzahl der Möglichkeiten auch über folgende (rekursiv definierte) Folge bestimmen:
f(0,k)=1 falls k>=0
f(n,k)=0 falls n0 f(n-i,k-1) falls n>0 und k>0
Dabei ist n die Summe (im Bsp. 13) und k die max. Anzahl der Summanden (im Bsp. 6). Für f(13,6) ergibt sich gerade 8232.
Zur Erklärung: Die Möglichkeiten 0 als Summe von irgendeiner Anzahl an Summanden (>=0) zu schreiben ist immer 1, nämlich genau ein Summand mit dem Wert 0. Es gibt keine Möglichkeiten für den Fall, daß die Zahl kleiner 0 ist (da die Summanden natürliche Zahlen sind) oder keine Summanden mehr zur Verfügung stehen. Ansonsten drückt die Summe f(n,k-1)+f(n-1,k-1)+f(n-2,k-1)+…+f(n-9,k-1) aus, daß die Anzahl der Möglichkeiten n als Summe von max. k Summanden mit Werten von 0-9 zu schreiben, gerade in die Anzahl der Möglichkeiten zerfällt, den ersten Summand als 0,1,…,9 zu wählen und das analoge Problem für das verbleibende n,n-1,…,n-9 mit k-1 Summanden zu betrachten.
Anm: Wer sich im weitergehenden Sinne an Fibonacci erinnert fühlt, liegt nicht völlig falsch. Es gilt nämlich, daß fibn+1, die Anzahl der Möglichkeiten ist, die Zahl n als Summe von 1ern und 2ern zu schreiben (ohne Begrenzung der Summanden).
Gruss
Enno