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 |
void my_bounded_sum(const uint* p_numbers, uint num_numbers, uint bound, bool* p_out_select); |
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 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 |
////////////////////////////////////////////////////////////////////////// // 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; } |
Quellcode |
|
1 |
test.cpp:32: error: ISO C++ does not support ‘long long’ |
C-/C++-Quelltext |
|
1 |
long long int |
C-/C++-Quelltext |
|
1 |
__int64 |
Anonymous
unregistriert
Stimmt, wie kommst du auf so tolle Sachen?! f'`8kZitat von »"Atlan123"«
Super Aufgabe David!
Werbeanzeige