Frage zu Knobelaufgaben-Algorithmus (kann es in den USA Wahlen ein Unentschieden geben)

Hallo, ich fange gerade an C++ zu lernen und wollte mir selbst ein paar interessante Aufgaben stellen. Dabei habe ich folgende Knobelaufgabe gesehen:

In den USA wählen 538 Wahlmänner den jeweiligen Präsidenten. Diese
Wahlmänner sind wie folgt auf die 51 Staaten verteilt:
Alabama 9
Alaska 3
usw...

Es ist die Frage zu klären, ob eine Stimmengleichheit bei der Wahl möglich ist.
Annahme: In jedem der Staaten setzt sich wie leider üblich entweder der
Kandidat der Republikaner oder jener der Demokraten durch.

Jetzt habe ich ein Programm geschrieben, dass auch wunderbar funktioniert. Allerdings wird es mir nie ein Ergebnis sagen können, da die "Berechnung" viel zu lange dauert (Permutation von 51 Elementen). Kann ich die Performance meines Programmes so verbessern, dass das Ergebnis in relativ kurzer Zeit ausgegeben wird? Oder muss ich den Algorithmus ändern? Wenn ja, wie? Hier mein Programm (ich hoffe, ihr versteht mein Programm. In stilistischer Hinsicht habe ich wenig Erfahrung mit Programmierung. Wäre also über jeden Tipp dankbar )

#include <iostream>
#include <algorithm>

int main()
{
    const unsigned int staaten = 51; //Anzahl Staaten der Usa

    //Wahlmännder pro Staat (nach Staaten alphabetisch sortiert)
    unsigned int arr[staaten] = {9,3,7,6,47,8,8,3,21,12,4,4,24,12,8,7,9,10,4,10,13,20,10,7,11,4,5,4,4,16,5,36,13,3,23,8,7,25,4,8,3,11,29,5,3,12,10,3,6,11,3};

    unsigned int *beg (arr); //pointer auf beginn des arrays
    unsigned int *end (beg+staaten); //pointer hinter das ende des arrays

    std::sort(beg, end);

    do
    {
        for(unsigned int* a(beg);a!=end;++a) //hier wird entschieden, wie viele staaten die republikander gewonnen haben
        {
            size_t republikaner (0), demokraten (0);

            for(unsigned int *b(beg); b!=a; ++b)
                republikaner+=*b; //alle stimmen der republikander zusammen zählen
            for(unsigned int *b(a);b!=end;++b)
                demokraten+=*b; //alle stimmen der demokraten zusammen zählen

            if(republikaner == demokraten)
            {
                std::cout<<"Unentschieden moeglich! :)";
            }
        }
    }
    while ( std::next_permutation (beg, end) ); //alle permutationen der wahlmänner

    std::cout<<"Unentschieden unmoeglich! :(";
}

Wie funktioniert das Wahlsystem mit den Wahlmännern überhaupt?

Tobiking2

Das erste was mir aufgefallen ist, ist dass du jedes mal die Stimmen der Demokraten und der Republikaner ausrechnest und miteinander vergleichst. Das könntest du dir sparen. Am Anfang die Hälfte der Gesamtstimmen ausrechnen und dann in jedem Durchlauf die Zahl der Demokraten damit vergleichen. Spart einige Rechnungen.

Ansonsten dürften die Permutationen das Problem sein. Die Anzahl der Permutationen ist 51 Fakultät, eine Zahl mit 66 Stellen. Zumal sind diese unnötig, da uns gar nicht genau interessiert, welcher Staat was wählt, und vor allem nicht die Reihenfolge. Was zählt ist, wieviele Staaten mit einer bestimmten Stimmzahl eine der beiden Partei wählen.

Nehmen wir als Beispiel die Staaten mit 4 Stimmen (7 Stück). Uns interessieren folgende Fälle: 0 Staaten wählen Demokraten, 1 Staaten wählen Demokraten ... 7 Staaten wählen Demokraten (Entspricht 0, 4, 8 ... Stimmen an Demokraten). Das sind 8 Fälle, statt 7! = 5040 bei Permutation.

Letztendlich bekommst du so eine lineare Gleichung: x*1 (Stimmen Staaten) + y*2 (Stimmen Staaten) ... = Hälfte der Stimmen. Wobei x = 0 bis Anzahl der Staaten mit einer Stimme etc.

Ich bin mir nur grad nicht sicher wie man das nun genau in C++ lösen könnte, wenn die Zahl der verschiedenen Stimmzahlen nicht vorher bekannt oder zumindest begrenzt ist.

volkard

Rucksackproblem

Sebastian Pizer

Ein paar Bemerkungen:

Zum Code:
Ich weiß nicht, wie es den anderen geht, aber ich finde die "direct initialization" gegenüber der "copy initialization" recht unleserlich, also int* foo(blah); versus int* foo = blah; . Man kann sich die Zeigergeschichte auch ganz sparen, wenn man Indizes statt Zeiger verwendet.

Zum Problem:
Dein Problem, welches Du zu lösen versuchst, ähnelt sehr stark dem Untermengensumme-Problem. Allerdings kommen bei Dir einige Zahlen der "Menge" mehrfach vor. Aber ich denke, dass es dadurch nicht einfacher wird. Das Untermengensumme-Problem ist bekanntermaßen "schwer" zu lösen (im Sinne der Ausführungsgeschwindigkeit). Für kleine Probleme würde ich die Branch-and-Bound-Methode verwenden. Du kannst ja mal testen, ob das bei n=51 noch zu einem Ergebnis führt bevor Du das Interesse am Problem verlierst.

Edit: Ich habe es mal ausprobiert und bin auch zu einem Ergebnis gekommen -- bzw etwa 3.000.000 Ergebnisse pro Sekunde (Intel Core2 Duo, 2.4 GHz, nur einen Kern genutzt, 32bit Linux, GCC 4.3.3, -O3, mit Rekursion).

Gruß,
SP

Th69

Seit wann gibt es in den USA 51 Staaten?
Ist der Song "51st state" von New Model Army jetzt also Realität geworden? -)

Sebastian Pizer

Gibt auch nur 50 Staaten, aber 51 Wahlgebiete (50 Staaten + Washington D.C.). Es kam mir auch komisch vor, deswegen hatte ich es gestern nachgeguckt.

Jester

volkard schrieb:

Rucksackproblem

Fast, eigentlich ist es nur PARTITION: http://de.wikipedia.org/wiki/PARTITION
Das Rucksackproblem hat zwei Kriterien: Wert und Gewicht. Aber der Hinweis ist trotzdem gut. Insbesondere dürfte der Ansatz mit dynamischer Programmierung hier die Laufzeit auf wenige Millisekunden drücken: http://de.wikipedia.org/wiki/Rucksackproblem#L.C3.B6sung_mittels_dynamischer_Programmierung