Das hier habe ich aus einem anderen Forum gefunden:
===
Ein Mann ist in der Wüste…. er hat genau 500km noch zurückzulegen..bis er sein Ziel erreicht.
Er hat aber zum Glück Essens und Wasser Vorrat.. ..genau 450 Stück )

mit einem Vorrat (ein Brötchen) kommt er 15 km ..er kann aber nur 12 auf einmal tragen.
Wie müsste der Mann laufen um sein Ziel zu erreichen.
—————————————————————————-
Als Bsp für die Rechnung: er läuft 15km und verbraucht 1 Ration( dann legt er 10 Rationen ab ), dann läuft er wieder zurück und verbraucht wieder eine Ration. somit hat er 10 Rationen schon zum Punkt gebracht und brauch nur noch 485km zurückzulegen.


Ich bin auf eure Berechnungen gespannt.
Das ist kein Witz oder sonst was. es geht nur mit einer Rechnung :-) also keine blöden Lösungen die keinen Sinn ergeben



Die Lösung für die Km Zahl die er laufen muss mit dementsprechend viel Rationen ist kurz über 500Km…also er würde auch weiter kommen.
===

Ich habe mir da auch etwas überlegt, was ich auch wunderbar mathemetisch modelliert habe, aber leider war die Taktik falsch:

===
Man muss sich überlegen, wie man das mathemtisch mordellieren kann und sich dann verschiedene Taktike einfallen lassen.

Eine Möglichkeit wäre es z.B. gewessen, seinen ganzen Vorrat 'mitzunehmen'. Das könnte man z.B. in 10km Schritten machen. Es geht also so:

-12 Brötchen nehmen, diese 10km weit tragen (dabei geht ein Brötchen verloren)
-dann dort 10 Brötchen liegen lassen und mit einem zurück gehen

Das kann man dann auch mit dem Rest so machen. Um 10 Brötchen 15km weit zu tragen hat man am Anfang 12 weg nehmen müssen, da 2 für den Weg verbraucht wurden.

Also hat man von den 12 Brötchen 2 verbraucht bzw. hat von den 12 Brötchen 2/12=1/6=0,17=17% verbraucht.

Wenn man das auf alle 450 Brötchen hoch rechnet, dann verliert man 17% von den 40 Brötchen.

Also nach einem Transport aller Brötchen um 15km bleiben noch 450 - 450*0,17 = 373,5 Brötchen übrig.

Man kann dieses jetzt als Funktion auffassen (mathematische Modellierung) und dann ausrechnen wieviel Kilometer man mit dieser Taktik kommt.

Wenn man n mal 15km zurückgelegt hat, dann bleiben noch 450 * (1 - o,17)^n Brötchen übrig. (Wenn die Formel nicht klar sein sollte, kann ich sie gerne auch nochmal erklären) Wir können uns jetzt z.B. fragen wann noch 10 Brötchen übrig bleiben. Wir rechnen:


450 * (1 - 0,17)^n = 10
<=> durch 450 auf beiden Seiten
(1 - 0,17)^n = 10/450
<=> auf beiden Seiten log (siehe http://de.wikipedia.org/wiki/Logarithmus für Regel)
log( (1 - 0,17)^n ) = log(10/450)
<=> Regel von log
n * log( 1 - 0,17 ) = log(10/450)
<=>
n = log(10/450) / log(1-0,17)
= 20,4

Man kann die Brötchen also 20 mal 15km weiter nach vorne Transportieren. Dann liegen noch 10 Brötchen auf dem Feld (eigentlich noch etwas mehr, da es 20,4 sind und die Formel noch eine kleinen Fehler hat). Man schafft also (mindestens) noch mal 15km.

Mit dieser Taktik schafft man also auf jeden Fall 20 * 15 + 15 = 21 * 15 = 315km und noch ein wenig mehr.

Man muss sich also leider eine andere Taktik einfallen lassen, da einem noch etwas weniger als 100km fehlen……
===

Habt ihr vielleicht eine Lösung, mit der man die ganzen 500km schafft?

Finde die Aufgabe echt interessant, macht auch Spass so was…

mit 10 Brötchen kommt man nicht 15 Kilometer weit sondern 150 Kilometer!

wenn du die ungenaue Formel durch eine simple Java-Simulation ersetzt kriegst du die optimale Route,
ich denke es gibt keine andere Taktik als die von dir schon angesprochene,

dazu passt ja auch dass das letzt Brötchen gerade zu den 500 km reicht ;)

edit: ach ne, da hatte ich was nicht bedacht und nun reicht es nur noch für 480 km bei mir ;)


public class Test { public static void main(String[] args) throws Exception { int alterVorrat = 450; int neuerVorrat = 0; int weite = 0; while (alterVorrat > 0) { weite += 15; alterVorrat -= 12; // die letzten Brötchen in jeder Runde gesondert behandeln, siehe unten neuerVorrat = 10 * (alterVorrat / 12); alterVorrat = alterVorrat % 12; alterVorrat += 12; if (alterVorrat > 14) { // zweimal laufen neuerVorrat += alterVorrat-3; } else { // einmal laufen neuerVorrat += Math.min(alterVorrat,12)-1; } alterVorrat = neuerVorrat; neuerVorrat = 0; System.out.println("Weite: "+weite+" Vorrat: "+alterVorrat); } } } Weite: 15 Vorrat: 375 Weite: 30 Vorrat: 312 Weite: 45 Vorrat: 261 Weite: 60 Vorrat: 218 Weite: 75 Vorrat: 181 Weite: 90 Vorrat: 151 Weite: 105 Vorrat: 126 Weite: 120 Vorrat: 105 Weite: 135 Vorrat: 88 Weite: 150 Vorrat: 73 Weite: 165 Vorrat: 61 Weite: 180 Vorrat: 51 Weite: 195 Vorrat: 42 Weite: 210 Vorrat: 35 Weite: 225 Vorrat: 30 Weite: 240 Vorrat: 25 Weite: 255 Vorrat: 21 Weite: 270 Vorrat: 18 Weite: 285 Vorrat: 15 Weite: 300 Vorrat: 12 Weite: 315 Vorrat: 11 Weite: 330 Vorrat: 10 Weite: 345 Vorrat: 9 Weite: 360 Vorrat: 8 Weite: 375 Vorrat: 7 Weite: 390 Vorrat: 6 Weite: 405 Vorrat: 5 Weite: 420 Vorrat: 4 Weite: 435 Vorrat: 3 Weite: 450 Vorrat: 2 Weite: 465 Vorrat: 1 Weite: 480 Vorrat: 0

schlauer ist natürlich nur 7.5 km zu laufen, alle 12 abzulegen und zurück am vorherigen Stapel zu essen,


bisschen dumm wirds dann mit halben Brötchen (wenn man nur die Hinstrecke geht),
schwerer zu simulieren und besser mehrere Zwischenlager zu machen

… und ob es die beste Lösung ist, kannst du immernoch nur vermuten, nicht beweisen …

Unterschied zwischen Theoretiker und Praktiker halt :-)

ich wäre auch für einen beweis, aber der ist wohl schwierig.

im prinzip sucht man ja zunächst mal nach einem algorithmus, der das lösen kann. die frage ist, ob es einen solchen algorithmus gibt, das problem also entschidbar ist oder nicht.

und dann noch die nächste frage: wenn man einen gefunden hat mit dem es geht, wie viel zeit zum lösen braucht dieser?

Also.
Die Rechnung mit den Prozenten ist relativ ungenau…

Wenn man eine Schrittweite von s = 15 hat, kann man a Brötchen so transportieren, dass
a - 1 - 2 * floor((a-1) / 12)
Brötchen 15 Meter weiter ankommen.

Bei einer Schrittweite von s=7.5 gilt
a - 0.5 - floor((a-1) / 12)

und bei einer von s=3.75
a - 0.25 - 0.5 * floor((a-1) / 12)

fällt was auf? Allgemein scheint zu gelten

a - (s/15) * (1 - 2 * floor((a-1) / 12))

Wenn ich nun iterativ ausrechnen lasse, wie weit man damit kommt scheint es mir, dass die ideale Lösung
lim s -> 0
sein könnte…

Wertetafel:
s => weite
15 => 480.0
7.5 => 495.0
3.75 => 502.5
15/2^10 => 517.67578125

Ich habe ja aber nur eine iterative Formel, die ich nicht bewiesen sondern nur vermutet habe. Wenn man daraus eine direkte Formel ableiten könnte könnte man vielleicht die Grenzwertbetrachtung machen…

- clemens

(floor heißt abrunden…)

Da hilft nur ausprobieren! Vielleicht kann man das an RTL verkaufen: Einfach 10 Promis in die Wüste schicken mit möglichst wenig Brötchen und sehen, wer ankommt?

Wenn folgender Ansatz gewaehlt wird: Man unterteilt die Broetchen in gleichgrosse Einheiten, und geht dann mit diesen auf Reise.
Ich habe dazu den Code von Slater modifiziert – hoffentlich richtig …

public class Test { public static void main(String[] args) throws Exception { // Ein Broetchen besteht aus soviel Einheiten final int EINHEIT = 10; // Diese Strecke schaft man mit einem Verbrauch einer Einheit final double WEITE_PRO_EINHEIT = 15.0 / EINHEIT; // Soviel Broetcheneinheiten darf man maximal tragen final int MAX_TRAGELAST = 12 * EINHEIT; // Vorrat in $EINHEIT int alterVorrat = 450 * EINHEIT; int neuerVorrat = 0; double weite = 0; System.out.println("EINHEIT:" + EINHEIT ); System.out.println("WEITE_PRO_EINHEIT:" + WEITE_PRO_EINHEIT ); System.out.println("MAX_TRAGELAST:" + MAX_TRAGELAST ); System.out.println("Vorrat:" + alterVorrat + " Broetcheneinheiten" ); while (alterVorrat > 0) { weite += WEITE_PRO_EINHEIT; alterVorrat -= MAX_TRAGELAST; // die letzten Brötchen in jeder Runde gesondert behandeln, siehe unten neuerVorrat = (MAX_TRAGELAST - 2) * (alterVorrat / MAX_TRAGELAST); alterVorrat = alterVorrat % MAX_TRAGELAST; alterVorrat += MAX_TRAGELAST; if (alterVorrat > MAX_TRAGELAST + 2) { // zweimal laufen neuerVorrat += alterVorrat-3; } else { // einmal laufen neuerVorrat += Math.min(alterVorrat, MAX_TRAGELAST)-1; } alterVorrat = neuerVorrat; neuerVorrat = 0; System.out.println("Weite: "+weite+" Vorrat: "+alterVorrat); } } } EINHEIT:10 WEITE_PRO_EINHEIT:1.5 MAX_TRAGELAST:120 Vorrat:4500 Broetcheneinheiten Weite: 1.5 Vorrat: 4425 Weite: 3.0 Vorrat: 4352 Weite: 4.5 Vorrat: 4279 Weite: 6.0 Vorrat: 4208 Weite: 7.5 Vorrat: 4137 Weite: 9.0 Vorrat: 4068 Weite: 10.5 Vorrat: 4001 [...] Weite: 477.0 Vorrat: 16 Weite: 478.5 Vorrat: 15 Weite: 480.0 Vorrat: 14 Weite: 481.5 Vorrat: 13 Weite: 483.0 Vorrat: 12 Weite: 484.5 Vorrat: 11 Weite: 486.0 Vorrat: 10 Weite: 487.5 Vorrat: 9 Weite: 489.0 Vorrat: 8 Weite: 490.5 Vorrat: 7 Weite: 492.0 Vorrat: 6 Weite: 493.5 Vorrat: 5 Weite: 495.0 Vorrat: 4 Weite: 496.5 Vorrat: 3 Weite: 498.0 Vorrat: 2 Weite: 499.5 Vorrat: 1 Weite: 501.0 Vorrat: 0