spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

C-/C++-Quelltext

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

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

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

// Titel: ...... "Mega-Summe"                                           //

// Typ: ........ Geschwindigkeit                                        //

// Deadline: ... 06.01.2008                                             //

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

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

// Aufgabe:                                                             //

// --------                                                             //

// Deine Funktion muss die Summe vieler großer Zahlen berechnen, die    //

// als Strings im Dezimalsystem in einem Vektor übergeben werden.       //

// Das Ergebnis wird ebenfalls als String geliefert.                    //

// Die Zahlen und das Ergebnis haben keine führenden Nullen, außer wenn //

// sie wirklich Null sind.                                              //

// Alle Zahlen haben maximal 256 Ziffern, das Ergebnis kann natürlich   //

// auch mehr haben. Die Summe besteht aus maximal 1.000.000 Zahlen.     //

// Negative Zahlen kommen nicht vor.                                    //

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


#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <ctime>

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


static const size_t MAX_NUMBERS = 1000000;
static const size_t MAX_DIGITS = 256;

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


// einfacher Zufallsgenerator

unsigned int random()
{
    static unsigned long long int seed = 4284567975ULL;
    const unsigned int value = static_cast<unsigned int>((279470273ULL * seed) % 4294967291ULL);
    seed = value;
    return value;
}

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


// generiert eine zufällige Zahl mit der angegebenen Anzahl von Stellen

const std::string random_number(size_t digits)
{
    std::string result(digits, '0');
    if(digits == 1) result[0] += random() % 10;
    else
    {
        result[0] += 1 + (random() % 9);
        for(size_t i = 1; i != digits; ++i) result[i] += random() % 10;
    }

    return result;
}

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


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

const std::string my_sum(const std::vector<std::string>& numbers)
{
    return "0";
}

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


// Referenzfunktion, zum Vergleich

const std::string reference_sum(const std::vector<std::string>& numbers)
{
    // maximale Stringlänge finden

    size_t max_length = 0;
    for(std::vector<std::string>::const_iterator it = numbers.begin(); it != numbers.end(); ++it)
        if(it->length() > max_length)
            max_length = it->length();

    // Kopie der Zahlen erzeugen und links Nullen anhängen

    std::vector<std::string> copy(numbers);
    for(std::vector<std::string>::iterator it = copy.begin(); it != copy.end(); ++it)
        *it = std::string(max_length - it->length(), '0') + *it;

    // Ergebnis initialisieren

    std::string result(max_length, '0');

    // Stellen von hinten addieren

    int carry = 0;
    for(size_t i = max_length; i--;)
    {
        int sum = carry;
        for(std::vector<std::string>::iterator it = copy.begin(); it != copy.end(); ++it)
            sum += (*it)[i] - '0';

        result[i] += sum % 10;
        carry = sum / 10;
    }

    // letzten Übertrag vorne anhängen, falls vorhanden

    std::ostringstream result_str;
    if(carry) result_str << carry;
    result_str << result;

    return result_str.str();
}

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


int main()
{
    const size_t TEST_NUMBERS = 1000000;    // Anzahl der Zahlen beim Test (<= MAX_NUMBERS)

    const size_t TEST_MAX_DIGITS = 256;     // maximale Stellenanzahl der Zahlen (<= MAX_DIGITS)

    time_t t0;

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


    std::cout << "Generiere Liste mit " << TEST_NUMBERS << " Zahlen mit maximal " << TEST_MAX_DIGITS << " Stellen ..." << std::endl << std::endl;
    std::vector<std::string> numbers;
    numbers.reserve(TEST_NUMBERS);
    for(size_t i = 0; i != TEST_NUMBERS; ++i)
        numbers.push_back(random_number(1 + (rand() % TEST_MAX_DIGITS)));

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


    std::cout << "Berechne Referenzergebnis ..." << std::endl;
    t0 = clock();
    const std::string reference_result(reference_sum(numbers));
    const double reference_secs = static_cast<double>(clock() - t0) / CLOCKS_PER_SEC;
    std::cout << "Dauer: " << reference_secs << " s" << std::endl << std::endl;
    std::cout << "Ergebnis: " << std::endl << reference_result << std::endl << std::endl;

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


    std::cout << "Berechne eigenes Ergebnis ..." << std::endl;
    t0 = clock();
    const std::string my_result(my_sum(numbers));
    const double my_secs = static_cast<double>(clock() - t0) / CLOCKS_PER_SEC;
    const double factor = reference_secs / my_secs;
    std::cout << "Dauer: " << my_secs << " s (" << factor << " mal so schnell)" << std::endl << std::endl;
    std::cout << "Ergebnis: " << std::endl << my_result << std::endl << std::endl;

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


    std::cout << (reference_result == my_result ? "Ergebnis ist korrekt!" : "Ergebnis ist FALSCH!") << std::endl << std::endl;

    return 0;
}