Ui, habs gelöst. Und zwar in wenigen Millisekunden :D (also mit dem Computer)
Man kann ja nach dem Schema vorgehen:
- die erste Ziffer d1 kann jede Ziffer von 1 bis 9 sein ( da führend keine 0 erlaubt ist )
- die zweite Ziffer d2 kann jede Ziffer von 0 bis 10 - d1 sein
- die dritte Ziffer d3 kann jede Ziffer von 0 bis 10 - d1 - d2 sein
- die vierte Ziffer d4 kann jede Ziffer von 0 bis 10 - d2 - d3 sein
- die fünfte Ziffer d5 kann jede Ziffer von 0 bis 10 - d3 - d4 sein
usw.
Dafür könnte man einfach verschachtelte For-Schleifen programmieren, die genau das umsetzen und in der innersten Schleife die Möglichkeiten hochzählen. Das Problem ist, dass es ab ca. 11-13 Ziffern schon sehr lange braucht und mit 20 Ziffern wahrscheinlich mehrere Wochen.
Und die Lösung nennt sich "Memoisation". Da in Abhängigkeit von zwei Zahlen d1, d2 und der Position der Schleife das Zählergebnis immer dasselbe ist, kann man, sofern das Zählergebnis noch nicht gespeichert wurde, es in einer Tabelle speichern. Wurde es schon gespeichert, muss man nicht neu berechnen, sondern einfach nur den gespeicherten Wert addieren. Der Vorteil liegt klar auf der Hand: Der PC braucht viel weniger zu berechnen. Das ist ein tolles Hilfsmittel, was ich noch nicht kannte. Ist auch total leicht anzuwenden. Voraussetzung ist natürlich, dass eine Funktion bei gleichen Eingaben immer dieselben Ergebnisse zurückgibt.
Die zweite Sache ist, dass man BigInteger braucht, also Variablen mit mehr als 64 bit, da das Ergebnis auch in etwa 20 Ziffern haben wird, also größer als 2^63 - 1 ist ( was die maximal große natürliche Zahl in C++-Standardvariablen ist ). Dafür habe ich die Library "ttmath" verwendet.
Also hier der Code, falls es jemanden interessiert:
#include
#include
using namespace std ;
typedef unsigned long long uint64 ;
typedef ttmath::Int< 10 > BigInteger ;
BigInteger moeglichkeiten( int& k, int d1, int d2, int i ) ;
BigInteger moeglichkeiten( int k ) ;
BigInteger tabelle[ 10 ][ 10 ][ 20 ] ;
BigInteger moeglichkeiten( int k )
{
BigInteger N = 0 ;
int& kn = k ;
for ( int d = 1 ; d <= 9 ; ++d )
N += moeglichkeiten( kn, d, 0, 1 ) ;
return N ;
}
BigInteger moeglichkeiten( int& k, int d1, int d2, int i )
{
if ( i == k )
return 0 ;
BigInteger N = 0 ;
if ( i == k - 1 )
return 10 - d1 - d2 ;
else
for ( int d = 0 ; d < 10 - d1 - d2 ; ++d )
if ( tabelle[ d ][ d1 ][ i ] != -1 ) // wenn die tabelle diesen Eintrag schon enthält
N += tabelle[ d ][ d1 ][ i ] ;
else // ansonsten berechnen
{
tabelle[ d ][ d1 ][ i ] = moeglichkeiten( k, d, d1, i + 1 ) ;
N += moeglichkeiten( k, d, d1, i + 1 ) ;
}
return N ;
}
int main()
{
// tabelle mit "undefiniert" füllen
for ( int i = 0 ; i < 10 ; ++i )
for ( int j = 0 ; j < 10 ; ++j )
for ( int k = 0 ; k < 20 ; ++k )
tabelle[ i ][ j ][ k ] = -1 ;
BigInteger N = moeglichkeiten( 20 ) ;
cout << N << endl ;
return 0 ;
}
Ergebnis: 378158756814587
