Stilllegung des Forums
Das Forum wurde am 05.06.2023 nach über 20 Jahren stillgelegt (weitere Informationen und ein kleiner Rückblick).
Registrierungen, Anmeldungen und Postings sind nicht mehr möglich. Öffentliche Inhalte sind weiterhin zugänglich.
Das Team von spieleprogrammierer.de bedankt sich bei der Community für die vielen schönen Jahre.
Wenn du eine deutschsprachige Spieleentwickler-Community suchst, schau doch mal im Discord und auf ZFX vorbei!
Werbeanzeige
Administrator
C-/C++-Quelltext |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 |
////////////////////////////////////////////////////////////////////////// // 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; } |
Administrator
Administrator
Zitat von »"David Scherfgen"«
Naaa, alle ausgeschlafen?
Dann nichts wie ran! Wer macht mit?
C-/C++-Quelltext |
|
1 |
sum += (*it)[i] - '0'; |
Administrator
Werbeanzeige