spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

C-/C++-Quelltext

void my_bounded_sum(const uint* p_numbers,
                    uint num_numbers,
                    uint bound,
                    bool* p_out_select);

C-/C++-Quelltext

//////////////////////////////////////////////////////////////////////////

// spieleprogrammierer.de-Programmier-Contest #06                       //

// ******************************************************************** //

// Titel: ...... "Begrenzte Summe"                                      //

// Typ: ........ Spezial                                                //

// Deadline: ... 01.06.2008                                             //

// Abgabe: ..... contest@spieleprogrammierer.de                         //

// ******************************************************************** //

//                                                                      //

// Aufgabenstellung siehe:                                              //

// https://www.spieleprogrammierer.de/phpBB2/viewtopic.php?t=9494        //

//                                                                      //

//////////////////////////////////////////////////////////////////////////


#include <cmath>
#include <ctime>
#include <iostream>

typedef unsigned int uint;

//////////////////////////////////////////////////////////////////////////


// Mersenne Twister-Zufallsgenerator

class MTRand
{
public:
    MTRand(uint seed = 0) { this->seed(seed); }

    void seed(uint seed)
    {
        next = 0;
        const unsigned long long int factor = 69069;
        mt[0] = seed;
        for(uint i = 1; i != 624; ++i) mt[i] = static_cast<uint>(factor * mt[i - 1] + 1);
    }

    uint operator ()()
    {
        if(next == 624) { generateNumbers(); next = 0; }
        uint x = mt[next++];
        x ^= x >> 11;
        x ^= (x << 7) & 0x9D2C5680;
        x ^= (x << 15) & 0xEFC60000;
        x ^= x >> 18;
        return x;
    }

private:
    void generateNumbers()
    {
        const uint xorTab[] = { 0, 0x9908B0DF };
        for(uint i = 0; i != 227; ++i) { const uint x = (mt[i] & 0x80000000) | (mt[i + 1] & 0x7FFFFFFF); mt[i] = mt[i + 397] ^ (x >> 1) ^ xorTab[x & 1]; }
        for(uint i = 227; i != 624; ++i) { const uint x = (mt[i] & 0x80000000) | (mt[i + 1] & 0x7FFFFFFF); mt[i] = mt[i - 227] ^ (x >> 1) ^ xorTab[x & 1]; }
        const uint x = (mt[623] & 0x80000000) | (mt[0] & 0x7FFFFFFF);
        mt[623] = mt[396] ^ (x >> 1) ^ xorTab[x & 1];
    }

    uint mt[624];
    uint next;
};

//////////////////////////////////////////////////////////////////////////


// Hilfsfunktion zum Messen der Zeit

inline double time()
{
    return static_cast<double>(clock()) / CLOCKS_PER_SEC;
}

//////////////////////////////////////////////////////////////////////////


// globaler Zufallsgenerator, der genutzt werden darf

MTRand global_random(4711);

// >>> DEINE FUNKTION - BITTE IMPLEMENTIEREN! <<<

void my_bounded_sum(const uint* p_numbers,
                    uint num_numbers,
                    uint bound,
                    bool* p_out_select)
{
    // Achtung:

    // Der Inhalt von p_out_select wird vor dem Aufruf

    // dieser Funktion nicht initialisiert.

}

//////////////////////////////////////////////////////////////////////////


// Referenzimplementierung ("greedy")

void reference_bounded_sum(const uint* p_numbers,
                           uint num_numbers,
                           uint bound,
                           bool* p_out_select)
{
    uint sum = 0;
    for(uint i = 0; i != num_numbers; ++i)
    {
        // Die Zahl wird aufgenommen, wenn sie noch passt,

        // also wenn die bisherige Summe + diese Zahl den Grenzwert nicht überschreitet.

        if(p_out_select[i] = sum + p_numbers[i] <= bound) sum += p_numbers[i];
    }
}

//////////////////////////////////////////////////////////////////////////


// bestimmt die Punktzahl einer Lösung

double measure(void (* p_function)(const uint*, uint, uint, bool*),
               double num_seconds,
               uint random_seed,
               double* p_out_num_tasks_per_second = 0,
               double* p_out_average_score = 0,
               double* p_out_exact_hit_ratio = 0)
{
    MTRand random(random_seed);
    double total_score = 0.0;
    uint num_tasks = 0;
    uint num_exact_hits = 0;

    const double t0 = time();
    while(true)
    {
        uint numbers[50];
        bool select[50];

        // 5 bis 50 Zahlen zwischen 1 und 10000 erzeugen

        const uint num_numbers = 5 + random() % 46;
        uint total_sum = 0;
        for(uint i = 0; i != num_numbers; ++i)
        {
            const uint number = 1 + random() % 10000;
            numbers[i] = number;
            total_sum += number;
        }

        // zufällig einige Zahlen auswählen und deren Summe als Schranke verwenden

        uint bound = 0;
        do
        {
            for(uint i = 0; i != num_numbers; ++i)
            {
                // 50% Chance für jede Zahl, genommen zu werden

                if(random() % 2) bound += numbers[i];
            }
        }
        while(!bound);

        // Funktion aufrufen

        p_function(numbers, num_numbers, bound, select);

        // Zeit überschritten? Wenn ja, dann aufhören.

        if(time() > t0 + num_seconds) break;

        // erreichte Summe ausrechnen

        uint sum = 0;
        for(uint i = 0; i != num_numbers; ++i) if(select[i]) sum += numbers[i];

        // Die Summe darf nicht über dem Grenzwert liegen!

        if(sum > bound)
        {
            std::cout << "Summe liegt ueber dem Grenzwert!" << std::endl;
            return 0.0;
        }

        // Aufgabe geschafft

        ++num_tasks;

        // Punktzahl bestimmen

        const double ratio = static_cast<double>(sum) / bound;
        const double score = pow(ratio, 2000);
        total_score += score;
        if(sum == bound) ++num_exact_hits;
    }

    // Statistiken eintragen

    if(p_out_num_tasks_per_second) *p_out_num_tasks_per_second = static_cast<double>(num_tasks) / num_seconds;
    if(p_out_average_score) *p_out_average_score = total_score / num_tasks;
    if(p_out_exact_hit_ratio) *p_out_exact_hit_ratio = static_cast<double>(num_exact_hits) / num_tasks;

    // Punktzahl normalisieren

    return total_score / num_seconds;
}

//////////////////////////////////////////////////////////////////////////


int main()
{
    const double NUM_SECONDS = 5.0;
    const uint RANDOM_SEED = 31337;
    double num_tasks_per_second = 0.0;
    double average_score = 0.0;
    double exact_hit_ratio = 0.0;

    // Punktzahl der eigenen Implementierung bestimmen

    std::cout << "Teste eigene Funktion ..." << std::endl;
    const double my_score = measure(&my_bounded_sum, NUM_SECONDS, RANDOM_SEED, &num_tasks_per_second, &average_score, &exact_hit_ratio);
    std::cout << "Gesamtpunktzahl: ........................ " << my_score << std::endl;
    std::cout << "Tasks pro Sekunde: ...................... " << num_tasks_per_second << std::endl;
    std::cout << "Durchschnittliche Punktzahl pro Task: ... " << average_score << std::endl;
    std::cout << "Trefferquote des exakten Grenzwertes: ... " << exact_hit_ratio << std::endl;

    // Punktzahl der Referenzimplementierung bestimmen

    std::cout << std::endl;
    std::cout << "Teste Referenzfunktion ..." << std::endl;
    const double reference_score = measure(&reference_bounded_sum, NUM_SECONDS, RANDOM_SEED, &num_tasks_per_second, &average_score, &exact_hit_ratio);

    std::cout << "Gesamtpunktzahl: ........................ " << reference_score << std::endl;
    std::cout << "Tasks pro Sekunde: ...................... " << num_tasks_per_second << std::endl;
    std::cout << "Durchschnittliche Punktzahl pro Task: ... " << average_score << std::endl;
    std::cout << "Trefferquote des exakten Grenzwertes: ... " << exact_hit_ratio << std::endl;

    // Punkteverhältnis ausgeben (größer als 1 bedeutet, dass die eigene Funktion besser ist als die Referenzfunktion)

    std::cout << std::endl;
    std::cout << "Verhaeltnis der Gesamtpunktzahlen: ...... " << my_score / reference_score << std::endl;

    return 0;
}