005
18.09.2002, 07:22 Uhr
virtual
Sexiest Bit alive
(Operator)
|
Vorweg: ich fiunde Deine Lösung da eigentlich mit die Schönste.
Generell ist an Rekursiven Lösungen ja nichts auszusetzen, sie sind oft eleganter als die nicht-rekursiven. So sehe ich das auch beim Nikolausproblem.
Eine Nichtrekursive Lösung zum Nikolausproblem kann ich mal hier kurz skizzieren (sie ist nicht schwerer zu verstehen als eine rekursive), vielleicht schiebe ich noch die konkrete Implementation nach:
Das haus besteht aus 8 Strichen, die ich mal mit den Ziffern 0 - 7 durchnummerie. Der String "01234567" Representiert also einen Weg das Haus zu zeichnen, weil alle 8 Striche genau einmal vorkommen. Ob dies eine Legale Art ist, das Haus zu zeichnen, sei dahin gestellt.
Die Toplevel schleife koennte also so aussehen:
| C++: |
#include <algorithm>
void gebe_alle_moeglichkeiten_aus()
{
char striche[] = "01234567";
do
{
// Mach irgendwas, siehe unten
} while (std::next_permutation(striche, striche+8));
}
|
Die Schleife wird für jede denkbare Permutation - und damit pot. Möglichkeit - genau einmal durchlaufen. In der Schleife muessten nun zwei Dinge geschehen:
1. Prüfung, ob die Striche in umgekehrter Reihenfolge bereits gefunden wurden (dazu eben striche umdrehen und nachgucken, ob der resultierende String bereits in einem Ergebnisvektor vorhanden ist)
2. Prüfung, ob die Striche einen legalen Weg darstellen, das Haus zu zeichnen. Zu diesem Zweck bietet sich an, eine Matrix zu wenden, die die entsprechenden Informationen enthält. Ist es möglich, das Haus so zu zeichnen, kann der String in den Ergebnisvektor übernommen werden.
--
Gruß, virtual
Quote of the Month
Ich eß' nur was ein Gesicht hat (Creme 21) |
Ich erlabe dir, es mir gleich zu tun. 