Formel für alle Teilzahlen, die in Summe eine andere Zahl ergeben?

Hallo,

ich arbeite gerade an einer Programmier-Challenge, bei der es folgendes herauszufinden gilt:

Gegeben ist eine Zahl X. Finde heraus, welche positiven ganzen Zahlen (ohne Null) alle addiert werden können, damit (bei insgesamt vier Additionen) X herauskommt.

Beispiel:
X=100
Welche a+b+c+d ergeben X?
97+1+1+1 = 100, aber zb auch 33+33+33+1 = 100

Gibt es für diese Aufgabe eine bestimmte Formel? Mein aktueller Pseudo-Code probiert einfach alle Möglichkeiten durch, aber eventuell ist das nicht sehr effizient bei großen Zahlen bzw. scheint es so noch nicht zu funktionieren:

for (i=1;i<X;i++){
  for (e=1;e<X;e++){
    for (f=1;f<X;f++){
      for (g=1;g<X;g++){
        if ((i+f+g+h)==X){
          print "i+e+f+g = X"
        }
      }
    }
  }
}

Soweit ich das beurteilen kann, würde das aber so vermutlich nicht ganz funktionieren? Zudem, wie könnte man es am besten lösen, wenn man mit der Anzahl der Additionen, die ermittelt werden sollen (also beispielsweise anstatt von 4, möchte ich alle Kombinationen von 6 Zahlen herausfinden), variabel sein möchte? In meinem Beispielcode habe ich nun eine Hauptschleife und drei weitere Schleifen geschachtelt, sodass ich auf vier Additionen komme. Wie könnte man es am besten lösen, wenn man vorher die Anzahl der gesuchten Additionen nicht weiß (beispielsweise wenn dieser als Parameter übergeben wird)?
Soweit ich das bei meinem bisherigen Lösungsansatz beurteilen konnte, werden zudem auch gleiche Kombinationen ermittelt, also beispielsweise:
97+1+1+1, 1+97+1+1, usw. -> das sollte im Endeffekt ignoriert werden und nur einmal ausgegeben bzw. gespeichert.

Bin für jede Hilfe dankbar!

Stihwort Partitionsfunktion und ergezigende Funktionen

Du kannst Dir schonmal die innerste Schleife sparen. Drei verschachtelte Schleifen reichen aus, weil sich der vierte Wert dann automatisch aus der Randbedingunge (Summe = 100) ergibt.
Außerdem kannst Du die äußeren Schleifen optimieren. Beispiel: i+e > 100. Dann kannst Du die weitere Prüfung abbrechen.

pumuckl

Brauchst du Permutationen? D.h. ist 1,1,1,97 das Selbe wie 1,1,97,1 oder müssen beide Zahlenfolgen gesondert ausgegeben werden? Falls eine geordnete Folge (z.B. kleinere Zalen zuerst) ausreichend ist, dann kannst du dir überlegen, dass die Schleifen andere Randbedingungen haben können.

Jester

Mußt du die wirklich alle erzeugen? Oder ist die Aufgabe nur zu sagen wieviele es sind?

Helfer in der Not schrieb:

Stihwort Partitionsfunktion und ergezigende Funktionen

Danke! Scheint genau mein Problem zu beschreiben.

Trollolololoo schrieb:

Du kannst Dir schonmal die innerste Schleife sparen. Drei verschachtelte Schleifen reichen aus, weil sich der vierte Wert dann automatisch aus der Randbedingunge (Summe = 100) ergibt.
Außerdem kannst Du die äußeren Schleifen optimieren. Beispiel: i+e > 100. Dann kannst Du die weitere Prüfung abbrechen.

Danke für den Tipp!

pumuckl schrieb:

Brauchst du Permutationen? D.h. ist 1,1,1,97 das Selbe wie 1,1,97,1 oder müssen beide Zahlenfolgen gesondert ausgegeben werden?

Permutationen benötige ich nicht. D.h. für mich ist es ausreichend, wenn ich einmal die Folge von zb 1+1+1+97 habe, egal in welcher Reihenfolge.

Jester schrieb:

Mußt du die wirklich alle erzeugen? Oder ist die Aufgabe nur zu sagen wieviele es sind?

Ich muss sie tatsächlich erzeugen, da ich sie dann weiter verwenden möchte (deshalb muss ich sie dann auch noch geeignet zwischenspeichern). Der geplante Wertebereich liegt zwischen 1-4 Byte.

pumuckl

So in etwa:

#include <vector>

void print(std::vector<unsigned> const& sequence);

void partitionSum(std::vector<unsigned>& sequence, unsigned count, unsigned rest, unsigned min =1)
{
  assert(count > 0);
  if (count == 1)
  {
    sequence.push_back(rest);
    print(sequence);
    sequence.pop_back();
    return;
  }

  for (unsigned i = min; i <= rest/count; ++i)
  {
    sequence.push_back(i);
    partitionSum(sequence, count-1, rest-i, i);
    sequence.pop_back();
  }
}

Aufruf kannste dir ja denken

Danke pumuckl!

Gibt es dafür auch eine implementierung in c?

Ralph_ schrieb:

Ich muss sie tatsächlich erzeugen, da ich sie dann weiter verwenden möchte (deshalb muss ich sie dann auch noch geeignet zwischenspeichern). Der geplante Wertebereich liegt zwischen 1-4 Byte.

bist du dir sicher, dass du das willst? Schau dir mal an, wie viele Zahlen das sind. Wir lösen das mal schrittwise:

Sei N die Zeilsumme (in deiner Frage N=100) und K_k(N) die Anzahl der Kombinationen mit k Zahlen auf N aufzusummieren.

für k=2 ohne Permuationen ist dies einfach:
K_2(N) = N-1
Für K = 3 kann man das berechnen indem man einfach eine Zahl k wählt und dann die Anzahl der Kombinationen der restlichen N-k Zahlen angibt:
K_3(N) = N-1 K_2(N-1) = \sum_{k=1}^{N-1} K_2(N-k)
= \sum_{k=1}^{N-1} N-k-1 =N^2/2 -...

und K_4(N) = \sum_{k=1}^{N-1} K_3(N-k)

das kannst du dir selbst ausrechnen, aber du kommst darauf, dass K_4(N) ein Polynom der Ordnung 3 in N ist.

Nun sagst du, dass dein Wertbereich 1-4 Bytes = 32 Bits ist. Das heißt du kannst K_3(N) mit der Anzahl der bits b abschätzen durch 2^(3b)
für b = 10 (also =1024) erhälst du also schon irgendwas um 2^30 Kombinationen, und 16 Bit sollten dir schon lange deinen Speicher sprengen. An deiner Stelle würde ich mir eine andere Lösungsstrategie suchen.

Sorry, das war mit Permutationen

@pumuckl: Deine Lösung scheint gut zu funktionieren, Danke nochmals!

@jkio2: Ich versuche gerade das ganze in C zu realisieren. Falls jemand mehr Erfahrung in C hat, würde ich mich über Hilfe freuen.

@otze_logout: Ja, beim Testen habe ich bereits festgestellt, dass es mit dem Speicher etwas knapp wird. Der Wertebereich von einem Byte würde mir demnach wohl auch reichen (0-255).