009
25.10.2004, 19:47 Uhr
0xdeadbeef
Gott
(Operator)
|
Einfacher wärs noch so, denke ich. Ist jedenfalls schneller. Der Gedanke ist, erst die Möglichkeiten für 1 Münze zu berechnen, dann darauf die für 2, dann aus denen für 1 und 2 Münzen die für 3 usw, und dabei doppelte entfernen.
std::set ist ein Container, der das selbe Element nur einmal vorhält, wenn ich also "211" im set drinhabe und "211" einfügen will, ist nachher trotzdem nur ein mal "211" drin, wenn ich also die Strings vorher sortiere (mit std::sort), schmeiße ich auf die Art doppelte Einträge raus.
| C++: |
#include <algorithm>
#include <iostream>
#include <iterator>
#include <set>
#include <sstream>
#include <string>
#include <vector>
int main() {
// Ein Vektor (quasi gekapseltes Array) von sets (Mengen) von Strings, 21 Einträge
std::vector<std::set<std::string> > muenzen(21);
muenzen[0].insert(""); // Iterationsanfang, keine Möglichkeiten ohne Münzen
// std::vector<std::set<std::string> >::size_type ist ein vorzeichenloser integraler Typ,
// halt zur Indizierung des vectors.
for(std::vector<std::set<std::string> >::size_type i = 1; i <= 20; ++i)
// j nimmt die Werte 5, 2, und 1 an - war die kürzeste Art, das zu schreiben.
for(int j = 5; j > 0; j /= 2)
// Hier die eigentliche Konstruktion. Die Verteilungsmöglichkeiten für 10 Münzen sind
// eine 5 und die Aufteilungsmöglichkeiten für 5 Münzen, eine 2 und die Aufteilungsmöglichkeiten
// für 8 Münzen und eine 1 und die Aufteilungsmöglichkeiten für 9 Münzen zusammengefasst.
// Also:
if(i >= j) {
// j in einen String umwandeln
std::stringstream sout;
sout << j;
for(std::set<std::string>::iterator k = muenzen[i - j].begin();
k != muenzen[i - j].end();
++k) {
// den String mit der gerade betrachteten Möglichkeit zusammenketten
std::string s = sout.str() + *k;
// Sortieren für Übersicht und Aussonderung doppelter Treffer
std::sort(s.rbegin(), s.rend());
// Und das Ergebnis speichern. set sortiert doppelte Einträge automatisch aus.
muenzen[i].insert(s);
}
}
// Ausgabe aller Möglichkeiten
for(std::vector<std::set<std::string> >::size_type i = 1; i <= 20; ++i) {
std::cout << "---" << std::endl
<< i << std::endl
<< "---" << std::endl;
std::copy(muenzen[i].rbegin(),
muenzen[i].rend(),
std::ostream_iterator<std::string>(std::cout, "\n"));
}
}
|
--
Einfachheit ist Voraussetzung für Zuverlässigkeit.
-- Edsger Wybe Dijkstra |
.