So mal eine interessante Aufgabe zum Programmieren ;D

flybyray

flybyray

Vice Admiral Special
Mitglied seit
06.06.2008
Beiträge
509
Renomée
9
Standort
München
Weil hier ja in letzter Zeit nur noch Links über Programmierbücher ausgetauscht worden sind, dachte ich mir ich könnte mal wieder was praktischeres hier einfügen.
Es ist nichts großes für den Computer nur ein paar Schleifen Inkrements und Vergleiche.
Die Aufgabe habe ich aus der Newsgroup von der FernUniversität in Hagen (es handelt sich aber nicht um eine offizielle Aufgabe). Es geht um etwas kombinatorisches, dass man mittels Mathematischem Know-How kaum bewältigt bekommt. Aber ein Programm, das Ergebnis innerhalb weniger Sekunden ausspuckt.

Wie wird man Millionär – oder 6 Richtige mit Superzahl

Ich träumte mal wieder vom Lottojackpot als ich am Samstag Nachmittag nahe meines Lottoladens eine wunderbare, lieblich anzusehende Fee traf.

Nachdem wir uns ein wenig unterhielten, bat ich Sie, mir die Lottozahlen der kommenden Ziehung aufzuschreiben.

„Oh“, sagte die Fee, „ich kann jedem Menschen nur einen Wunsch erfüllen, du aber hast gleich 7 Wünsche: 6 Lottozahlen und die Superzahl.“

Trotzdem notierte mir dieses entzückende Wesen eine Zahl auf einem Zettel und sagte: „Addiere alle Zahlen der nächsten Ziehung zusammen, dann ist dies das Ergebnis“.

„Was soll ich nun damit anfangen?“ fragte ich verzweifelt.

„Nun Gut“, sprach die Fee, „ich gib Dir noch ein paar Tipps: Rechne genau aus, wie viele Möglichkeiten es gibt, die diese Summe ergeben. Wenn du dieses Ergebnis mit der von mir genannten Zahl multiplizierst, ist dies das gleiche Ergebnis das rauskommt, wenn man alle sechs Lottozahlen miteinander multipliziert. Die Superzahl ergibt sich aus der Quersumme der von mir aufgeschriebenen Zahl“

Ich ging nach Hause und rechnete und rechnete. Nach Stunden hatte ich das Ergebnis, fuhr zum Lottoladen und musste feststellen, dass dieser nun bereits geschlossen hatte.

Am Abend schaute ich die Lottoziehung: die Zahlen kamen. Vielleicht treffe ich ja noch einmal auf eine gute Fee.
Zum Vergrößern anklicken....

Viel Spass! ;D
 
Hätte mal ne Frage, wie berechnet man die Möglichkeiten, die es gibt die Summe zu erreichen?

mfg

elite.bl4ze
 
elite.bl4ze schrieb:
Hätte mal ne Frage, wie berechnet man die Möglichkeiten, die es gibt die Summe zu erreichen?
Zum Vergrößern anklicken....
WIe man das mathematisch korrekt ermittelt weiß ich nicht. Das ist ziemlich schwer in diesem Fall. Das gibt der Kurs auch vom Inhalt nicht her, dass ich mir das damit herleiten kann. Wie gesagt es war so eine zusätzliche Aufgabe.
Am schnellsten ist das Programmiert.
So weit ich das richtig ermittelt habe ist die Anzahl der Möglichkeiten
Code: 
85900584
.
EDIT :
.
Ich denke sogar, dass sehr gute Kombinatoriker/Statistiker sich bei der Berechnung der Möglichen Summen die Zähne ausbeißen. Ich habe vorhin mal die steigenden (fallenden) Sequenzen bei Number Sequences gesucht. Ein bisschen übereinstimmung gibt es. Aber es ist doch was ganz anderes.
 
häh, ich versteh des nicht ganz, wie man sowas machen soll.P

@TE:

Komm bitte mal icq, brauch deine hilfe .P
Und deine Zahl stimmt auch nicht immer... Denn wenn die Summe der Zahlen sich ändert, ändert sich auch die Anzahl der Warscheinlichkeiten die Summe der Zahlen zu erreichen...

mfg

elite.bl4ze
 
Zuletzt bearbeitet:
Die Aufgabe ist zu Schwammig formuliert, wie der TE und ich jetzt festgestellt haben...

mfg

elite.bl4ze
 
Ok die Aufgabe scheint mehr mals nicht eindeutig zu sein! irgendwie kommen da mehrere Lotto zahlen raus habe jetzt 2 verschiedene Ansätz genommen.
 
Erster Gedanke:

naiver Algorithmus, Brute Force
Laufzeit O(N^6).

Wobei N hier als 49 zu setzen ist.

13 841 287 201 Schleifendurchläufe.

Zweiter Gedanke:
da war ja mal was mit Kombinatorik - ziehen ohne Zurücklegen:

10 068 347 520 Durchläufe.


Dritter Gedanke:
das ist ja noch nicht richtig.. darin enthalten sind ja noch alle Permutationen die die selbe Summe ergeben.
[hier muss ich jetzt gerade erstmal eine Runde nachdenken]

Man kann sich wohl schön austoben mit rekursivem Algorithmus, einem DP-Algo, einem Greedy-Ansatz, vielleicht sogar einem Flussnetzwerk ;-)

Bei der Faktorisierung großer Zahlen versucht man diese ja aus Primzahlprodukten zusammenzusetzen. GGf. muss man hier also auch so vorgehen, nur eben mit der Generalisierung, dass statt Primzahlen eben alle natürlichen Zahlen mit n=1 ... 49 zugelassen sind.

Nächste Idee: man löst es durch ein ILP - allerdings hat man dann definitiv schon ein np-vollständiges Problem vorliegen, das muss auch einfacher gehen...

Nochmal nachgedacht und das Problem vereinfacht: 2 Zahlen zwischen 1-9 müssen in Summe die Zahl 15 ergeben wie viele Möglichkeiten gibt es?

9+6
8+7
7+8
6+9

--> 4 Möglichkeiten, wobei zwei davon doppelt vorkommen --> 2 Möglichkeiten

Generalisierung 1:
2 Zahlen zwischen 1-9 müssen in Summe die Zahl x ergeben wie viele Möglichkeiten gibt es? x liegt im Intervall [3,17].

Wie bekommt man nun die Anzahl raus, die für jede der Summen gilt?
 
Zuletzt bearbeitet:
Flussnetzwerk würde funktionieren, wäre allerdings zu groß zum handschrifltichen Rechnen. Allgemein müsste es mit Graphen lösbar sein.

Anderer Ansatz: Die Summe aller 6 Zahlen beträgt zwischen 21 und 279, da die Möglichkeiten wie eine gaußsche Glockenkurve aussieht, muss man "nur" zwischen 21 und 150 rechnen und das Ergebnis mit 2 multiplizieren
 
Zuletzt bearbeitet:
Wenn du dieses Ergebnis mit der von mir genannten Zahl multiplizierst, ist dies das gleiche Ergebnis das rauskommt, wenn man alle sechs Lottozahlen miteinander multipliziert.
Zum Vergrößern anklicken....

Bedeutet also: x * y = a*b*c*d*e*f
Im Umkehrschluss: die Anzahl der Möglichkeiten x bekommt man raus, wenn man die Formel umstellt und die Summe y durch das Produkt der Lottozahlen teilt.

Das dürfte sich mit einem Gleichungssystem lösen lassen.
.
EDIT :
.
Je länger ich drüber nachdenke desto intuitiver erscheint es mir, das Ganze einfach durch einen Standardalgorithmus zur Faktorisierung zu jagen - ein Zahlkörpersieb z.b.

Allerdings kenne ich mich da zu wenig aus, um den Algo von Primzahlen auf natürliche Zahlen umzustricken ;-)
 
Gut wenn das hier doch noch mal so heiß diskutiert wird. Mit was weiß ich was für Fantasien und Theorien! ;D
Wie ich schon mal meinte macht die Aufgabe auch geübten Leuten ziemlich Kopfzerbrechen.

„Addiere alle Zahlen der nächsten Ziehung zusammen, dann ist dies das Ergebnis“.
Zum Vergrößern anklicken....
Code: 
X = \sum_{i=1}^{6} x_i
Das ist die notierte Zahl der Fee.

Code: 
„ich gib Dir noch ein paar Tipps: Rechne genau aus, wie viele Möglichkeiten es gibt, die diese Summe ergeben.
Es ist also ein festes X. X liegt in einem festen Zahlenbereich
Code: 
1+2+3+4+5+6=21<=X<=279=49+48+47+46+45+44
Es müssen demnach
Code: 
279-21+1=259
Möglichichkeiten betrachtet werden.
Es müssen die Werte in einen Speicher A[259] berechnet werden.
Code: 
A[0]:=1 falls X=21
...
A[258]:=1 falls X=279
Wenn du dieses Ergebnis mit der von mir genannten Zahl multiplizierst, ist dies das gleiche Ergebnis das rauskommt, wenn man alle sechs Lottozahlen miteinander multipliziert.
Zum Vergrößern anklicken....
Code: 
A[j] * X == \prod_{i=1}^{6} x_i
Die Superzahl ergibt sich aus der Quersumme der von mir aufgeschriebenen Zahl“
Zum Vergrößern anklicken....
Das sollte woll das einfachste sein wenn man X einmal gefunden hat. ;D
.
EDIT :
.
QlX39k0tFGSI4d70vdZq schrieb:
Es müssen die Werte in einen Speicher A[259] berechnet werden.
Code: 
A[0]:=1 falls X=21
...
A[258]:=1 falls X=279
Zum Vergrößern anklicken....
Übrigens diese erst aufsteigende und dann absteigende Zahlenfolge sollte man sich mal bei The On-Line Encyclopedia of Integer Sequences ansehen.
 
Ich denke glaube ich zu kompliziert: die Summe der Lottozahlen ist ja maximal 279.

Man muss also nur alle Zahlen zwischen 21 (summe von 1-6) und 279 faktorisieren und auf die Nebenbedingungen überprüfen.

Und ich glaube es ist wichtig bei der Lösung, dass diese eindeutig sein muss...
 
@ QlX39k0tFGSI4d70vdZq
Du kannst dir den halben Speicher sparen ;D
Wieviele Möglichkeiten hat die Summe 21? Genau 1
Wieviele Möglichkeiten hat die Summe 279? Genau 1
Gaußsche Glockenkurve, somit hat die Zahl 150 die meißten Möglichkeiten, danach siehts wie die erste Hälfte aus.

Soviel steht fest: es ist kein NP-Problem, da in O(n^7) lösbar
 
Zuletzt bearbeitet:
JKuehl schrieb:
Und ich glaube es ist wichtig bei der Lösung, dass diese eindeutig sein muss...
Zum Vergrößern anklicken....
Jupp, aber dennoch ist das Problem nicht gerade einfach. Ich korrigiere gerade mal einen Code den ich vorher falsch geschrieben habe, weil ich es auch noch nicht so ganz geblickt hatte.
.
EDIT :
.
So ich habe mal das geschrieben.
Code: 
#include <iostream>                                                                     
#include <vector>                                                                       

using namespace std;
int static MAXLOTTO = 49;
int main(int argc, char** argv)
{                              
    vector<unsigned long long int> numvektor;
    vector<unsigned long long int>::iterator numiter;
    unsigned int x[6];
//    unsigned long long int counter=0;
    numvektor.resize(259);
    for(numiter = numvektor.begin(); numiter != numvektor.end(); numiter++) {
        *numiter = 0ULL;
    }
    for ( x[0] = 1 ; x[0] <= MAXLOTTO; x[0]++ )
    for ( x[1] = x[0]+ 1 ; x[1] <= MAXLOTTO; x[1]++ )
    for ( x[2] = x[1]+ 1 ; x[2] <= MAXLOTTO; x[2]++ )
    for ( x[3] = x[2]+ 1 ; x[3] <= MAXLOTTO; x[3]++ )
    for ( x[4] = x[3]+ 1 ; x[4] <= MAXLOTTO; x[4]++ )
    for ( x[5] = x[4]+ 1 ; x[5] <= MAXLOTTO; x[5]++ ) {
        unsigned long long int sum = 0;
        for (int i = 0; i < 6; i++ ) {
            sum += x[i];
        }
        numvektor[sum-21]++;
    }
    cout << "ANZAHL MÖGLICHKEITEN" << endl;

    for (unsigned int i = 0; i < 259; i++ ) {
        cout << "SUMME = " << i+21 << " ANZAHL = " << numvektor[i] << endl;
    }

    for ( x[0] = 1 ; x[0] <= MAXLOTTO; x[0]++ )
    for ( x[1] = x[0]+ 1 ; x[1] <= MAXLOTTO; x[1]++ )
    for ( x[2] = x[1]+ 1 ; x[2] <= MAXLOTTO; x[2]++ )
    for ( x[3] = x[2]+ 1 ; x[3] <= MAXLOTTO; x[3]++ )
    for ( x[4] = x[3]+ 1 ; x[4] <= MAXLOTTO; x[4]++ )
    for ( x[5] = x[4]+ 1 ; x[5] <= MAXLOTTO; x[5]++ ) {
        unsigned long long int sum = 0;
        unsigned long long int prod = 1;
        for (int i = 0; i < 6; i++ ) {
            sum += x[i];
            prod *= x[i];
        }
        for (unsigned int i = 0; i < 259; i++ ) {
            unsigned long long int temp;
            temp *= numvektor[i];
            if (temp == prod) {
                cout << "MÖGLICHE LOTTOZAHLEN fuer X = " << i+21 << endl << "| ";
                for (int i = 0; i < 6; i++ ) {
                    cout <<  x[i] << " | ";
                }
                cout << endl;
            }
        }
    }
    return 0;
}
Leider spuckt er mir keine Lottozahlen aus. ;D
Muss ich noch mal nachschauen wo da der Fehler ist.
.
EDIT :
.
ach das temp wahrscheinlich noch mit sum initialisieren. ;D mal sehen
.
EDIT :
.
So nochmal nachgelegt. Irgendwie findet er jetzt 1476 Kombinationen.
Code: 
#include <iostream>
#include <vector>

using namespace std;
int static MAXLOTTO = 49;
int main(int argc, char** argv)
{
    vector<unsigned long long int> numvektor;
    vector<unsigned long long int>::iterator numiter;
    unsigned int x[6];
    unsigned long long int counter=0;
    numvektor.resize(259);
    for(numiter = numvektor.begin(); numiter != numvektor.end(); numiter++) {
        *numiter = 0ULL;
    }
    for ( x[0] = 1 ; x[0] <= MAXLOTTO; x[0]++ )
    for ( x[1] = x[0]+ 1 ; x[1] <= MAXLOTTO; x[1]++ )
    for ( x[2] = x[1]+ 1 ; x[2] <= MAXLOTTO; x[2]++ )
    for ( x[3] = x[2]+ 1 ; x[3] <= MAXLOTTO; x[3]++ )
    for ( x[4] = x[3]+ 1 ; x[4] <= MAXLOTTO; x[4]++ )
    for ( x[5] = x[4]+ 1 ; x[5] <= MAXLOTTO; x[5]++ ) {
        unsigned long long int sum = 0;
        for (int i = 0; i < 6; i++ ) {
            sum += x[i];
        }
        numvektor[sum-21]++;
    }
    cout << "ANZAHL MÖGLICHKEITEN" << endl;

    for (unsigned int i = 0; i < 259; i++ ) {
        cout << "SUMME = " << i+21 << " ANZAHL = " << numvektor[i] << endl;
    }

    for ( x[0] = 1 ; x[0] <= MAXLOTTO; x[0]++ )
    for ( x[1] = x[0]+ 1 ; x[1] <= MAXLOTTO; x[1]++ )
    for ( x[2] = x[1]+ 1 ; x[2] <= MAXLOTTO; x[2]++ )
    for ( x[3] = x[2]+ 1 ; x[3] <= MAXLOTTO; x[3]++ )
    for ( x[4] = x[3]+ 1 ; x[4] <= MAXLOTTO; x[4]++ )
    for ( x[5] = x[4]+ 1 ; x[5] <= MAXLOTTO; x[5]++ ) {
        unsigned long long int sum = 0;
        unsigned long long int prod = 1;
        for (int i = 0; i < 6; i++ ) {
            sum += x[i];
            prod *= x[i];
        }
        for (unsigned int i = 0; i < 259; i++ ) {
            unsigned long long int temp = sum;
            temp *= numvektor[i];
            if (temp == prod) {
                cout << "MÖGLICHE LOTTOZAHLEN fuer X = " << i+21 << endl << "| ";
                for (int i = 0; i < 6; i++ ) {
                    cout <<  x[i] << " | ";
                }
                counter++;
                cout << endl;
            }
        }
    }
    cout << "Es wurden " << counter << " Lottozahlenkombinationen gefunden!" << endl;
    return 0;
}
.
EDIT :
.
shit immer noch irgendein fehler drin. ach menno!
.
EDIT :
.
So jetzt klappt es. Nur noch 4 Lottokombinationen und mit den Hinweisen die noch als ergänzung waren stimmt das scheinbar auch.
Dort hieß es noch am Ende:
Additional Hints

Zum Raetsel:
Es sind zwei einstellige Zahlen
eine Zahl zwischen 10 und 19
eine Zahl zwischen 20 und 29
eine Zahl zwischen 30 und 39
eine Zahl zwischen 40 und 49

Von den Sechs Lottozahlen sind zwei gerade und 4 ungerade.

Die Summe der ersten 3 Zahlen ist 24
Die Summe der Zahlen 2 bis 4 ist 45
Die Summe der Zahlen 5 und 6 ist 80

Die von der Fee aufgeschrieben Zahl liegt zwischen 100 und 199
Zum Vergrößern anklicken....
Code: 
#include <iostream>
#include <vector>

using namespace std;
int static MAXLOTTO = 49;
int main(int argc, char** argv)
{
    vector<unsigned long long int> numvektor;
    vector<unsigned long long int>::iterator numiter;
    unsigned int x[6];
    unsigned long long int counter=0;
    numvektor.resize(259);
    for(numiter = numvektor.begin(); numiter != numvektor.end(); numiter++) {
        *numiter = 0ULL;
    }
    for ( x[0] = 1 ; x[0] <= MAXLOTTO; x[0]++ )
    for ( x[1] = x[0]+ 1 ; x[1] <= MAXLOTTO; x[1]++ )
    for ( x[2] = x[1]+ 1 ; x[2] <= MAXLOTTO; x[2]++ )
    for ( x[3] = x[2]+ 1 ; x[3] <= MAXLOTTO; x[3]++ )
    for ( x[4] = x[3]+ 1 ; x[4] <= MAXLOTTO; x[4]++ )
    for ( x[5] = x[4]+ 1 ; x[5] <= MAXLOTTO; x[5]++ ) {
        unsigned long long int sum = 0;
        for (int i = 0; i < 6; i++ ) {
            sum += x[i];
        }
        numvektor[sum-21]++;
    }
    cout << "ANZAHL MÖGLICHKEITEN" << endl;

    for (unsigned int i = 0; i < 259; i++ ) {
        cout << "SUMME = " << i+21 << " ANZAHL = " << numvektor[i] << endl;
    }

    for ( x[0] = 1 ; x[0] <= MAXLOTTO; x[0]++ )
    for ( x[1] = x[0]+ 1 ; x[1] <= MAXLOTTO; x[1]++ )
    for ( x[2] = x[1]+ 1 ; x[2] <= MAXLOTTO; x[2]++ )
    for ( x[3] = x[2]+ 1 ; x[3] <= MAXLOTTO; x[3]++ )
    for ( x[4] = x[3]+ 1 ; x[4] <= MAXLOTTO; x[4]++ )
    for ( x[5] = x[4]+ 1 ; x[5] <= MAXLOTTO; x[5]++ ) {
        unsigned long long int sum = 0;
        unsigned long long int prod = 1;
        for (int i = 0; i < 6; i++ ) {
            sum += x[i];
            prod *= x[i];
        }
//        for (unsigned int i = 0; i < 259; i++ ) {
            unsigned long long int temp = sum;
            temp *= numvektor[sum-21];
            if (temp == prod) {
                cout << "MÖGLICHE LOTTOZAHLEN fuer X = " << sum /* i+21 */ << endl << "| ";
                for (int i = 0; i < 6; i++ ) {
                    cout <<  x[i] << " | ";
                }
                counter++;
                cout << endl;
            }
//        }
    }
    cout << "Es wurden " << counter << " Lottozahlenkombinationen gefunden!" << endl;
    return 0;
}
.
EDIT :
.
Lottokombinationen:
Code: 
MÖGLICHE LOTTOZAHLEN fuer X = 36
| 1 | 2 | 3 | 4 | 11 | 15 |
MÖGLICHE LOTTOZAHLEN fuer X = 45
| 1 | 4 | 5 | 7 | 9 | 19 |
MÖGLICHE LOTTOZAHLEN fuer X = 76
| 2 | 8 | 11 | 14 | 19 | 22 |
MÖGLICHE LOTTOZAHLEN fuer X = 130
| 5 | 8 | 11 | 26 | 37 | 43 |
 
Es gibt 140 008 Möglichkeiten ;-)
 
JKuehl schrieb:
Es gibt 140 008 Möglichkeiten ;-)
Zum Vergrößern anklicken....
Hehe hast du dafür eine Formel? Dann würde ich mich gleich mal bei The On-Line Encyclopedia of Integer Sequences als Erfinder eintragen lassen.
Ich habe mal die Möglichkeiten für die Summe als Suchfolge eingegeben.
Da konnte ich nur bis zu der Zahl 4935 eine übereinstimmung finden. The On-Line Encyclopedia of Integer Sequences!
.
EDIT :
.
Was ist das denn für eine Zahl die 140 008?
Für was braucht man die bei der Aufgabe?
.
EDIT :
.
neoda schrieb:
@ QlX39k0tFGSI4d70vdZq
Du kannst dir den halben Speicher sparen ;D
Wieviele Möglichkeiten hat die Summe 21? Genau 1
Wieviele Möglichkeiten hat die Summe 279? Genau 1
Gaußsche Glockenkurve, somit hat die Zahl 150 die meißten Möglichkeiten, danach siehts wie die erste Hälfte aus.

Soviel steht fest: es ist kein NP-Problem, da in O(n^7) lösbar
Zum Vergrößern anklicken....
Ja das was schon klar, dass ist wie mit dem Pascalschendreieck, da gibts auch ne symmetrie. Aber für die Berechnung selber ist es am umkompliziertesten einfach alles so zu lassen wie es ist. Ich denke für diese Aufgabe ist das noch kein Problem mit dem Speicher. ;D
Dieses Semester sollten aber noch ein paar fettere Brocken kommen.
 
Na die Zahl habe ich durch Einsetzen in die obige Formel durch Einsetzen der korrekten Lösung erhalten.

Und: Die Anzahl an Möglichkeiten muss natürlich auch GANZZAHLING sein, vielleicht bringt das ja den ein oder anderen noch auf weitere Ideen mit der von mir genannten Formel:

Bedeutet also: x * y = a*b*c*d*e*f
Im Umkehrschluss: die Anzahl der Möglichkeiten x bekommt man raus, wenn man die Formel umstellt und die Summe y durch das Produkt der Lottozahlen teilt.
Zum Vergrößern anklicken....
Dass man nicht selber programmieren muss, sondern Google hilft (und nein, man muss auch mal um die Ecke denken - es wäre ja total unlustig gewesen direkt nach der Lösung zu googlen) kann man dann auch hier unter folgendem Link sehen:

http://www.tipptreffer.de/lotto/lottosummen.htm
.
EDIT :
.
Um die Lösung selbst nachzuprogrammieren muss man also 3 Schritte durchführen

1) Summen tabellieren (21-279)
2) Man hat nur nur noch 258 Möglichkeiten für die korrekte Lösung. Das kann man notfalls noch per Hand ausrechnen - aber wir machen es natürlich weiter im Computer...
3) Wir multiplizieren alle Summen mit der zugehörigen Anzahl (trivial) von mir jetzt SUPERSUMME genannt
4) Wir Brute-Forcen jetzt einfach eine Faktorzerlegung für alle SUPERSUMMEN
4b) Wir wählen einen Backtrackingansatz (Spieltheorie) der alle unnötigen Teilbäume pruned wenn wir an einer Stelle merken, dass eine Kombination aus x Zahlen schon nicht mehr zum gewünschten Ergebnis führen kann
4c) Wir stellen ein Gleichungssystem mit 6 Unbekannten für jede Supersumme auf und lösen dies z.B. mit der LR-Zerlegung.
4d) Als Variante zu 4b definieren wir uns ein paar Regeln und lassen Prolog den Rest erledigen ;D Hab selbst seit 4 oder 5 Jahren nichts mehr in Prolog gemacht, aber ich schätze mal mit 20 Zeilen ist das Problem gelutscht...
 
Zuletzt bearbeitet:
JKuehl schrieb:
1) Summen tabellieren (21-279)
2) Man hat nur nur noch 258 Möglichkeiten für die korrekte Lösung. Das kann man notfalls noch per Hand ausrechnen - aber wir machen es natürlich weiter im Computer...
3) Wir multiplizieren alle Summen mit der zugehörigen Anzahl (trivial) von mir jetzt SUPERSUMME genannt
4) Wir Brute-Forcen jetzt einfach eine Faktorzerlegung für alle SUPERSUMMEN
4b) Wir wählen einen Backtrackingansatz (Spieltheorie) der alle unnötigen Teilbäume pruned wenn wir an einer Stelle merken, dass eine Kombination aus x Zahlen schon nicht mehr zum gewünschten Ergebnis führen kann
4c) Wir stellen ein Gleichungssystem mit 6 Unbekannten für jede Supersumme auf und lösen dies z.B. mit der LR-Zerlegung.
4d) Als Variante zu 4b definieren wir uns ein paar Regeln und lassen Prolog den Rest erledigen ;D Hab selbst seit 4 oder 5 Jahren nichts mehr in Prolog gemacht, aber ich schätze mal mit 20 Zeilen ist das Problem gelutscht...
Zum Vergrößern anklicken....
Ok ein paar Dinge (vor allem die ersten Punkte) sehe ich ähnlich.
Aber was muss hier angestellt werden:
4) Wir Brute-Forcen jetzt einfach eine Faktorzerlegung für alle SUPERSUMMEN
Zum Vergrößern anklicken....
???
Hört sich mächtig aufwändig an? Ich meine, der Code von mir läuft nicht mal 10 Sekunden. ;D
Aber ich habe nichts dagegen mal ein anderes Beispiel zu sehen wo sich Brutforcing und Backtracking gegenseitig einheitzen. ;D
.
EDIT :
.
Code: 
#include <iostream>
#include <vector>

using namespace std;
int static MAXLOTTO = 49;
int main(int argc, char** argv)
{
    vector<unsigned long long int> numvektor;
    vector<unsigned long long int>::iterator numiter;
    unsigned int x[6];
    unsigned long long int counter=0;
    numvektor.resize(259);
    for(numiter = numvektor.begin(); numiter != numvektor.end(); numiter++) {
        *numiter = 0ULL;
    }
    for ( x[0] = 1 ; x[0] <= MAXLOTTO; x[0]++ )
    for ( x[1] = x[0]+ 1 ; x[1] <= MAXLOTTO; x[1]++ )
    for ( x[2] = x[1]+ 1 ; x[2] <= MAXLOTTO; x[2]++ )
    for ( x[3] = x[2]+ 1 ; x[3] <= MAXLOTTO; x[3]++ )
    for ( x[4] = x[3]+ 1 ; x[4] <= MAXLOTTO; x[4]++ )
    for ( x[5] = x[4]+ 1 ; x[5] <= MAXLOTTO; x[5]++ ) {
        unsigned long long int sum = 0;
        for (int i = 0; i < 6; i++ ) {
            sum += x[i];
        }
        /* [B] 1) Summen tabellieren (21-279)[/B] */
        numvektor[sum-21]++;
    }
/* [B]2) Man hat nur nur noch 258 Möglichkeiten für die korrekte Lösung. Das kann man notfalls noch per Hand ausrechnen - aber wir machen es natürlich weiter im Computer...[/B]*/
    cout << "ANZAHL MÖGLICHKEITEN" << endl;

    for (unsigned int i = 0; i < 259; i++ ) {
        cout << "SUMME = " << i+21 << " ANZAHL = " << numvektor[i] << endl;
    }

    for ( x[0] = 1 ; x[0] <= MAXLOTTO; x[0]++ )
    for ( x[1] = x[0]+ 1 ; x[1] <= MAXLOTTO; x[1]++ )
    for ( x[2] = x[1]+ 1 ; x[2] <= MAXLOTTO; x[2]++ )
    for ( x[3] = x[2]+ 1 ; x[3] <= MAXLOTTO; x[3]++ )
    for ( x[4] = x[3]+ 1 ; x[4] <= MAXLOTTO; x[4]++ )
    for ( x[5] = x[4]+ 1 ; x[5] <= MAXLOTTO; x[5]++ ) {
        unsigned long long int sum = 0;
        unsigned long long int prod = 1;
        for (int i = 0; i < 6; i++ ) {
            sum += x[i];
            prod *= x[i];
        }
            unsigned long long int temp = sum;
/* [B]3) Wir multiplizieren alle Summen mit der zugehörigen Anzahl (trivial) von mir jetzt SUPERSUMME genannt[/B] */
            temp *= numvektor[sum-21];
            if (temp == prod) {
                cout << "MÖGLICHE LOTTOZAHLEN fuer X = " << sum /* i+21 */ << endl << "| ";
                for (int i = 0; i < 6; i++ ) {
                    cout <<  x[i] << " | ";
                }
                counter++;
                cout << endl;
            }
    }
    cout << "Es wurden " << counter << " Lottozahlenkombinationen gefunden!" << endl;
    return 0;
}

So habe mal deine Beschreibung dem Code hinzugefügt.
Für den Rest muss dann noch was programmiert werden. ;D
JKuehl schrieb:
4) Wir Brute-Forcen jetzt einfach eine Faktorzerlegung für alle SUPERSUMMEN
4b) Wir wählen einen Backtrackingansatz (Spieltheorie) der alle unnötigen Teilbäume pruned wenn wir an einer Stelle merken, dass eine Kombination aus x Zahlen schon nicht mehr zum gewünschten Ergebnis führen kann
4c) Wir stellen ein Gleichungssystem mit 6 Unbekannten für jede Supersumme auf und lösen dies z.B. mit der LR-Zerlegung.
4d) Als Variante zu 4b definieren wir uns ein paar Regeln und lassen Prolog den Rest erledigen ;D Hab selbst seit 4 oder 5 Jahren nichts mehr in Prolog gemacht, aber ich schätze mal mit 20 Zeilen ist das Problem gelutscht...
Zum Vergrößern anklicken....
 
Das Brute Forcen heißt nichts anderes, als dass du für diese Supersummen alle Möglichkeiten von (1,2,3,4,5,6) bis hin zu (44,45,46,47,48,49) ausprobierst.

viele Möglichkeiten kannst du dabei natürlich ausschließen.

soviel sei verraten: dein obiger Ansatz ist super, und die korrekten Zahlen sind dabei ;-)
 
Zurück
Oben Unten