3. Hilfe Zahlenkombination

Hilfe Zahlenkombination

  • S

    Hallo,
    ich bin neu hier im Forum und versuche mal mein Glück.
    Ich habe ein Problem, bei dem mich auch keiner meiner Freunde helfen kann.
    Ich möchte ein Programm schreiben, welche aus beliebig vielen zahlen, die in einem Array gespeichert sind, alle möglichen Kombination abfragt.

    Als beispiel:
    int zahl[12] = {1,2,3,4,5,6,7,8,9,10,11,12};

    Nun sollen alle zahlenkombinationen durchgegangen werden und geschaut werden wie diese Kombinationen zb. 13 ergeben.
    Das wäre zb. bei 3+10 oder 11+2 der fall.
    Aber auch bei 1+3+9 oder 1+2+3+7 usw.

    Ich war soweit das ich für einfach 12 scleifen geschrieben habe, in der jede Zahl abarbeitet wird.
    Aber das muss doch auch anders gehen oder?
    Das ganze soll nach möglichkeit eine rekursive funktion sein.

    Das ganze ist recht wichtig... danke euch schon einmal für die hilfe...
    Ich hoffe ihr kennt eine ANtwort

    0
  • M

    Also das mit den zwölf schleifen ist natürlich nich so geil 🙂

    Rekursiver ansatz wäre folgender:

    void KombiHelper(const std::vector<int>& zahlen, std::vector<int> bisher, int summe);

void AlleKombinationen(const std::vector<int>& zahlen, int summe)
{
 KombiHelper(zahlen, std::vector<int>(), summe);
}

void KombiHelper(const std::vector<int>& zahlen, std::vector<int> bisher, int summe)
{
  bisher.push_back(0); // dummy aufruf
  int letzt = bisher.size8) - 1;
  for(int i = 0; i < zahlen.size(); i++)
  {
     bisher[letzt] = zahlen[i];

     // summe berechnen
     if(std::accumulate(bisher.begin(), bisher.end()) == summe)
       // ausgabe von bisher;

     // weitere möglichkeiten prüfen
     KombiHelper(zahlen, bisher, summe);
  }
}

    ungetestet, aber er müsste so klappen. Allerdings werden mit diesem code auch Zahlen doppelt genommen. Aso, eine Abbruchbedingung müsste auch ncoh rein, zB dass nur 10 zahlen oder so zur kombination gehören dürrefn.

    0
  • S

    Das sieht ja alles ganz nice aus...
    nur leider sind meine Prgrammierfähigkeiten nicht so sehr ausgeprägt...
    Geht das noch ein wenig leichter?^^

    Das verwirrt mich ein wenig...
    void AlleKombinationen(const std::vector<int>& zahlen, int summe)

    0
  • M

    hm...

    also ein std::vector kannst du dir als array vorstellen, ist eigentlich genau das, nur dass er für dich die speicherverwlatung übernimmt und automatisch wächst wenn du mehr platz brauchst. Und void AlleKombinationen(...) ist die Funktion die du dann aufrufen musst.

    std::vector<int> zahlen;
for(int i = 0; i < 10; i++)
  zahlen.push_back(rand() % 10);
AlleKombinationen(zahlen, 10); // Gibt dir alle kombinationen den zahlen die aus die zusammen 10 ergeben.

    Der algorithmus dahinter ist ziemlich leicht. Kannst auch mit arays lösen ist aber aufwndiger wegen dem speicher.

    0
  • S

    Könntest du das anpassen mit einen normalen array, in dem zb. die zahlen 1,2,3,4,5,6 stehen und bei den die kombinationen durchlaufen werden?

    0
Anmelden zum Antworten