Anzahl Lösungen=6.017.023 Anzahl Iterationen=7.302.334

[Vinzenz Mai]

Hallo,

meine völlig unelegante iterative Vorgehensweise kommt auf:
7302334 Iterationen durch die innerste Schleife und
6017023 Lösungen, die letzte ist

[1, 2, 4, 8, 16, 32, 64, 124, 124, 125]

Mein Code, alles andere als beispielhaft, die Wahl fiel deswegen auf Python,
weil es an der Konsole gerade verfügbar war:

  
# Belege die Saecke mit der Mindestanzahl von Muenzen vor  
sack  = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]  
summe = [1, 0, 0, 0, 0, 0, 0, 0, 0, 0]  
  
# Wir muellen das Wurzelverzeichnis von C: voll :-)  
namepart = 'c:/martin.'  
  
# Brute-Force mit nur wenig Ueberlegungen:  
# Grenzen  
# Index  Sack     Untergrenze   Obergrenze  
#   0      1        1             1          - trivial  
#   1      2        1             2          - trivial  
#   2      3        1             4          - trivial  
#   3      4        2             8          - Obergrenze trivial, Untergrenze, da sonst max. moegliche Zahl nicht erreichbar  
#   4      5        4            16          - Obergrenze trivial, Untergrenze, siehe Sack 4  
#   5      6        8            32          - Obergrenze trivial, Untergrenze, siehe vorher  
#   6      7       16            64          - Obergrenze trivial, Untergrenze wie gehabt  
#   7      8       32           128          - Obergrenze trivial, Untergrenze wie gehabt  
#   8      9       63           167          - Untergrenze wie gehabt, Obergrenze: 1/3 unterhalb, 1/3 oberhalb und 1/3 fuer Sack 9  
#   9     10      125           250          - aber Sack 10 = 500 - Summe(Saecke 1 bis 9)  
  
  
filename = namepart + '0'  
f = file(filename, "w")  
iter  = 0  
count = 0  
for sack[1] in range(1,3):  
  # der naechste Sack muss mindestens soviel enthalten, wie der vorhergehende  
  summe[1] = sack[0] + sack[1]  
  for sack[2] in range(max(1, sack[1]), min(summe[1] + 2, 5)):  
    summe[2] = summe[1] + sack[2]  
    for sack[3] in range(max(2, sack[2]), min(summe[2] + 2, 9)):  
      summe[3] = summe[2] + sack[3]  
      for sack[4] in range(max(4, sack[3]), min(summe[3] + 2, 17)):  
        summe[4] = summe[3] + sack[4]  
        for sack[5] in range(max(8, sack[4]), min(summe[4] + 2, 33)):  
          summe[5] = summe[4] + sack[5]  
          for sack[6] in range(max(16, sack[5]), min(summe[5] + 2, 65)):  
            summe[6] = summe[5] + sack[6]  
            for sack[7] in range(max(32, sack[6]), min(summe[6] + 2, 128)):  
              summe[7] = summe[6] + sack[7]  
              for sack[8] in range(max(63, sack[7]), min(summe[7] + 2, 168)):  
                # zaehle die Iterationen  
                iter = iter + 1  
                summe[8] = summe[7] + sack[8]  
                # 1. Bedingung erfuellt: Summe der Inhalte ist 500 durch  
                sack[9] = 500 - summe[8]  
  
                if ((sack[9] > 250) or (sack[9] < 125) or sack[9] < sack[8]):  
                  # Sack 10 nicht im richtigen Intervall, oder kleiner als vorhergehender  
                  # passt nicht  
                  break;  
  
                # Hier angelangt, haben wir eine richtige Loesung  
                # zaehle die Treffer  
                count = count + 1  
  
                # Ausgabevorbereitung  
                line = str(sack) + "\n"  
  
                # Dateihandling  
                # Nur 100.000 Eintraege je Datei - und auch nur dann eine Ausgabe auf die Konsole  
                if ((count % 100000 == 0) and (count / 100000 > 0)):  
                  f.close()  
                  filename = namepart + str((count / 100000))  
                  f = file(filename, "w")  
                  print iter, " - ", count, ":", line,  
  
                # Schreibe sie weg  
                f.write(line)  
  
# Fertig, Gesamtzahl noch ausgeben:  
print iter, " - ", count, ":", line,  
f.close()  

Freundliche Grüße

Vinzenz