®

Hundertweg

Selbst wenn man den kürzesten Weg nimmt, also nur nach rechts oder nach oben geht, gibt es viele, genauer gesagt 39 gleichgute Lösungen. Angesichts der grossen Anzahl von Möglichkeiten, in einer 7x7er-Matrix von dem einen Punkt zum anderen auf kürzestem Weg zu gelangen, ist das gar nicht mal viel.
Man kann sich 12 Mal entscheiden, ob man rechts oder hoch gehen will. Dabei darf man maximal 6 Mal nach oben und 6 Mal nach rechts gehen.
In meinem Programm heisst es: bool WalkMap[12] = {0,0,0,0,0,0,1,1,1,1,1,1};
Die Anzahl der Möglichkeiten, von der 06 bis zu der 02 in der Matrix zu wandern, ist also die Anzahl der Möglichkeiten, 6 Einsen und 6 Nullen verschieden anzuordnen.
Das sind (12!)/(6!*6!) also 479001600 / 518400 = 924.

Mein Programm, das alle Möglichkeiten durchgeht, können Sie hier runterladen. Natürlich ist nur der C++ Sourcecode interessant!

Hier drei der lang erwarteten Lösungen ;) als Beispiele:

Die komplette Liste mit den 39 Lösungen, die mein Programm erstellt hat, folgt jetzt.
'0' bedeutet 'nach oben' und '1' bedeutet 'nach rechts'. Mein Programm errechnet die Lösungen übrigens in weniger als einer Sekunde auf einem P3 500.

1. 001010001111
2. 001100010111
3. 001110101001
4. 001111000011
5. 001111001010
6. 001111100100
7. 001111101000
8. 010010001111
9. 010100010111
10. 010110101001
11. 010111000011
12. 010111001010
13. 010111100100
14. 010111101000
15. 011000110011
16. 011000111010
17. 011010001011
18. 011101010001
19. 011101100010
20. 011110000011
21. 011110001010
22. 011110100100
23. 011110101000
24. 100010110101
25. 100100110110
26. 100110001110
27. 100110110100
28. 100110111000
29. 101001010110
30. 101100110010
31. 110000100111
32. 110001010101
33. 110001101100
34. 110100110001
35. 110101010010
36. 110101110000
37. 110110010100
38. 110110011000
39. 111000010110

Falls Sie Anmerkungen oder Verbesserungsvorschläge allgemein oder zu meinem Programm haben, schreiben Sie eine Email an aur0n@aur0n.de

Daniel Gutekunst (8. August 2001)


Vielen Dank, Daniel, für diese tolle Lösung.

Man könnte auch mal nach einer Matrix-Füllung suchen, die lediglich eine einzige Lösung erlaubt. Dagegen spricht allerdings, dass man Aufgaben wie diese wohl nur mit stupidem, langwierigem Probieren oder Rechnerprogrammen lösen kann.