+2 Daumen
193 Aufrufe
Hallo,

für diese Frage darf man Computer als Unterstützung nehmen. Ausprobieren funktioniert aber bei weitem nicht, dauert viel zu lange. Hat jemand ein paar Ansätze oder Tipps?

P.S.: Die ersten Werte sind:

3 Ziffern: 165 Möglichkeiten

4 Ziffern: 990 Möglichkeiten

5 Ziffern: 5445 Möglichkeiten

6 Ziffern: 27588 Möglichkeiten

7 Ziffern: 146586 Möglichkeiten

8 Ziffern: 783057 Möglichkeiten

9 Ziffern: 4129851 Möglichkeiten

Von mehr als 9 Ziffern an würde es zu lange dauern, mit dem Computer einfach auszuprobieren..

Danke,

Thilo
geschlossen: erledigt
von 4,3 k
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 <iostream>
#include <ttmath\ttmath.h>
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

Grüße, Thilo

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage sofort und kostenfrei

x
Made by a lovely community
...