Alle Kombinationsmöglichkeiten berechnen (180 Punkte auf 4 Felder aufteilen)

Diese Seite verwendet Cookies. Durch die Nutzung unserer Seite erklären Sie sich damit einverstanden, dass wir Cookies setzen. Weitere Informationen

  • Alle Kombinationsmöglichkeiten berechnen (180 Punkte auf 4 Felder aufteilen)

    Guten Abend Easy Coding :)

    Bein Kopf streikt gerade ein wenig. Ich habe insgesamt 180 Punkte auf 4 Felder zu verteilen. Nun brauch ich eine Möglichkeit alle der möglichen Aufteilungen zu berechnen. Habt ihr eine Idee, wie ich das ganze anstellen kann? (Programmiersprache ist egal. Ich brauch nur einen Ansatz, um das in C++ zu schreiben. ;))

    Mögliche Ergebnisse:

    180 - 0 - 0 - 0
    179 - 0 - 0 - 1
    179 - 0 - 1 - 0
    0 - 1 - 0 - 179
    50 - 130 - 0 0

    .
    .
    .

    Habe mir überlegt für [0 - 180] alle Permutation für die 4 Felder berechnen und dann prüfen, welche 180 ergeben. Da das nicht sehr performant ist und ich den selben Algorithmus auf ein Beispiel mit 20 Feldern und 600 Punkten anwenden muss, fällt die Möglichkeit definitiv weg. (Edit hat bemerkt, dass das Schwachsinn ist ^^)

    Schonmal vielen Dank :)

    Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von Active Record ()

  • Nach mehrstündigem Tüfteln mit einem Mathematiker, sind wir auf ein Ergebnis gekommen (falls es interessiert ;)):

    Noch in unschönem Stil:

    Quellcode

    1. #include <iostream>
    2. #include <string>
    3. #include <vector>
    4. #include <sstream>
    6. template <typename T>
    7. std::string numberToString (T Number)
    8. {
    9. std::ostringstream ss;
    10. ss << Number;
    11. return ss.str();
    12. }
    14. void showCategories(unsigned int categories[]) {
    16. std::string tmp = numberToString(categories[0]);
    18. for(unsigned int i = 1; i <= 3; i++) {
    20. tmp += ("-" + numberToString(categories[i]));
    21. }
    25. std::cout << tmp << " ";
    26. }
    28. int main(int argument_count, char* argv[]) {
    30. /*
    31. * Initalisierung
    32. */
    34. const unsigned int sum = 180;
    35. const unsigned int rows = 3;
    37. unsigned int categories[rows];
    39. // Füllen des Kategorien Arrays mit 0-Werten
    40. for(unsigned int i = 0; i <= rows; i++)
    41. {
    42. categories[i] = 0;
    43. }
    45. categories[0] = sum;
    48. /*
    49. * Berechnung der möglichen Kombinationen
    50. */
    52. unsigned int n = 0;
    53. unsigned int tmp_sum = 0;
    55. unsigned int counter = 0;
    57. while(categories[rows] != sum)
    58. {
    59. counter++;
    61. tmp_sum = 0;
    63. for(int i = 0; i <= rows; i++)
    64. {
    65. tmp_sum += categories[i];
    67. if(tmp_sum == sum) {
    69. n = i;
    70. break;
    71. }
    72. }
    74. if(n < rows)
    75. {
    76. --categories[n];
    77. ++categories[n + 1];
    78. }
    80. else if(n == rows)
    81. {
    82. if(categories[rows - 1] != 0)
    83. {
    84. ++categories[rows];
    85. --categories[rows - 1];
    86. }
    88. else
    89. {
    90. categories[rows] = 0;
    92. unsigned int lastIndex = 0;
    94. for(int i = 0; i <= rows; i++)
    95. {
    96. if(categories[i] > 0) {
    98. lastIndex = i;
    99. }
    100. }
    102. --categories[lastIndex];
    104. unsigned int sum_t = 0;
    106. for(int i = 0; i <= lastIndex; i++)
    107. {
    108. sum_t += categories[i];
    109. }
    111. categories[lastIndex + 1] = (sum - sum_t);
    113. }
    114. }
    116. showCategories(categories);
    117. std::cout << std::endl;
    119. }
    121. std::cout << std::endl << "Gesamte Durchläufe: " << counter;
    124. std::cin.ignore();
    125. return 0;
    126. }
    Alles anzeigen