| www.fahrradkurier-forum.de http://www.fahrradkurier-forum.de/ |
|
| Wie viele Möglichkeiten hat ein Fahrradkurier, eine bestimmte Strecke zu fahren? http://www.fahrradkurier-forum.de/viewtopic.php?f=15&t=2787 |
Seite 1 von 1 |
| Autor: | kokosadun [ Fr 26. Okt 2007, 11:02 ] |
| Betreff des Beitrags: | Wie viele Möglichkeiten hat ein Fahrradkurier, eine bestimmte Strecke zu fahren? |
Hab soeben ein möglicherweise interessantes Thema in einem anderen Forum entdeckt, und zwar im "Matheboard". Es geht darum, wie viele mathematische Möglichkeiten ein Kurier hat, eine bestimmte Strecke zu fahren. Hier klicken zum Thema im Matheboard Bin ja gespannt, was dabei noch herauskommt. Vielleicht mag sich jemand von unseren Lesern beteiligen? |
|
| Autor: | kiwi_kirsch [ Fr 26. Okt 2007, 11:53 ] |
| Betreff des Beitrags: | |
ooh das hatte ich früher mal im mathe-lk.. eieiei.. aber das ist jetzt neun jahre her.. |
|
| Autor: | dan [ Fr 26. Okt 2007, 14:56 ] |
| Betreff des Beitrags: | |
Die Anzahl der insgesamt möglichen Wege kannste bei dem Schachbrett-Modell einer Stadt mit dem Formelinstrumentarium der Kombinatorik durchrechnen. Das macht aber nicht wirklich glücklich denn Du willst ja nicht alle theoretisch möglichen Wege betrachten sondern "nur" wissen, wie viele kürzeste Wege es gibt. Wenn Du in einer p Felder breiten und q Felder hohen Stadt von "links unten" nach "rechts oben" kommen willst darfst Du also für einen kürzesten Weg grundsätzlich nur nach rechts oder nach oben gehen in einem Schritt. Das bedeutet, daß Du so lange, wie Du noch nicht rechts oder oben angekommen bist, je Schritt zwei Wahlmöglichkeiten hast. Bist Du einmal oben oder rechts angekommen gibt es nur noch eine. Wir brauchen aber erstmal die Länge des Weges um zu wissen wie viele Schritte überhaupt zu gehen sind. Die ist recht einfach zu bestimmen: wir müssen p-1 Felder nach rechts gehen und q-1 Felder nach oben s = (p - 1) + (q - 1) = p + q - 2 Auf diesem Weg gibt es nun "Restschritte" und "Wahlschritte". r = max(p-1,q-1) - min(p-1,q-1) Das sind die Restschritte. Die haben keine Wahlalternative. Die restlichen Schritte sind Wahlschritte, also w = s - r Für eine quadratische Stadt sollte man einfach "n über k" rechnen können, also (n über k) = n! / ((n-k)! * k!) Und das dann mit der Zahl der Restschritte multiplizieren, die ja an beliebiger Stelle in den Laufweg eingestreut werden können. Damit wird vermutlich irgendetwas der Art z = ((p-1)! / ((p-q-2)! * (q-1)!)) * r mit z als Zahl der möglichen Wege herauskommen. Hmm, nett. Leider muß ich gleich nochmal los und kann das Ding gerade nicht zu Ende basteln... |
|
| Autor: | kiwi_kirsch [ Fr 26. Okt 2007, 18:00 ] |
| Betreff des Beitrags: | |
0_0 |
|
| Autor: | tumor-pdm [ Fr 26. Okt 2007, 19:03 ] |
| Betreff des Beitrags: | |
Is das nicht das allseits beliebte "traveling salesman" Problem ? |
|
| Autor: | dan [ Sa 27. Okt 2007, 18:38 ] |
| Betreff des Beitrags: | |
@tumor: Beim TSP muß jedes Feld einmal besucht worden sein. Ist also was anderes. |
|
| Autor: | Maze [ Do 1. Nov 2007, 21:34 ] |
| Betreff des Beitrags: | |
ich fahr immer diagonal |
|
| Seite 1 von 1 | Alle Zeiten sind UTC + 1 Stunde |
| Powered by phpBB® Forum Software © phpBB Group http://www.phpbb.com/ |
|