Wüstenfit

[sharkie_003]

Hallo,

Wir haben in Informatik eine Hausaufgabe aufbekommen und ich habe leider keine Ahnung wie ich das Problem angehn soll.

Die Aufgabe ist:
Du fährst mit dem Auto in die Wüste, Auto hat Totalschaden 500km von der Stadt entfernt. Du hast im Kofferraum 450 Dosen "Wüstenfit"(komprimiertes Essen&Trinken) und willst zurück in die Stadt.Mit einer Dose kannst du immer 15km laufen. In deinen Rucksack passen aber immer nur 12 Dosen.

Wir sollen jetzt ein Programm schreiben, dass uns die sinnvollste Verteilung von Dosen/Weg angibt.

Hat vielleicht jemand einen Ansatz für mich?
Ich weiß, dass ich auf dem Weg immer "Dosenhäufchen" anlegen kann, aber wie es weiter gehen soll...

Ich will kein komplettes Programm, nur ein bisschen Hilfe, weil ich das grade echt gar nicht verstehe.

Danke schonmal

Sharkie

 

[Napofis]

Das geh nicht, Dosenhäufen gibts nicht.

Deine maximale Reichweite ist (12+1)x15 = 195km. Dein Programm soll bestimmt nur etwas berechnen wenn der Weg kürzer ist als 195 km wenn er länger ist -> tot.

Wenn er kürzer ist musst du berechnen wie viele Dosen du brauchst. Zum Beispiel bei einem Weg von 145km brauchst du nur 9 Dosen.

$dosen = floor((int)$weg/15);

if ($dosen>12) echo 'Der Weg zu lang!';
else echo $dosen.' müssen eingepackt werden.';

 

[sharkie_003]

Doch es gibt Dosenhäufchen.
Wenn man 12 Dosen im Rucksack hat und eine isst um 15 km zu laufen. Dann ist man die 15km gelaufen und kann 12 Dosen ablegen. Dann wieder zurücklaufen mit einer Dose und neue Dosen holen....und so weiter^^
Ich weiß jetzt auch schon, dass ich 96 Dosen brauche um den Weg zurück zulegen. Die letzten 180km kann ich mit 12 Dosen laufen, die auf dem letzen Haufen vor der Stadt liegen.

Die "Lösung" hab ich schon...ich weißt halt nur absolut nicht, wie ich das in php schreiben soll :/

 

[saftmeister]

Die Frage ist doch nicht, wie man das in PHP macht, sonder wie der zugrunde liegende mathematische Algorithmus ist. Wenn du den gefunden hast, ist das in PHP (oder jeder anderen Sprache) kein Problem.

Ich werde dir nicht verraten, wie der mathematische Algo ist. Nur soviel: Es geht mit For-Schleifen und IMHO brauchst du Modulo.

 

[sharkie_003]

Ich steh grad echt total auf dem Schlauch. Ich will ja selber drauf kommen, aber ich komm echt nicht drauf.
Irgendeinen Tip oderso?

 

[Parantatatam]

So blöd es klingt, aber ich würde es objektorientiert lösen. Das kann man am Ende bestimmt auch auf prozedurale Ebene mit Arrays abstrahieren, aber wenn man von dem Gedanken ausgeht, dass man drei Arten von Objekten hat (Person, Dosen, Haufen) und dann die Person zwischen den Haufen hin und her wandern lässt und jedes Mal prüft, wieweit man noch von seinem Ziel entfernt ist. Und wenn man merkt, dass man das Ziel mit dem momentanen Vorrat nicht erreicht, dann schaut man nach, wieviel im Haufen davor liegt und zieht zwei ab. Soweit geht man dann eben von Haufen zu Haufen bis hin zum Ausgangspunkt. Aber das ist auch nur so eine Idee.

 

[CPoly]

Man könnte die Dosen doch auch immer wieder vor sich werfen :-D. Dann ist man in der Stadt und hat über 400 Dosen übrig :-D.

Spaß bei Seite, ich stimme saftmeister natürlich zu. Nimm dir doch einfach ein Blatt Papier und schreib dir die Zahlen auf. Mal dir mehrere Stationen auf und überleg wie sich die Zahlen ändern. So löst man Probleme und es ist eine viel höhere Kunst Probleme zu lösen als PHP Code zu hacken.

 

[sharkie_003]

Ich hab das jetzt nochmal versucht. Hab mich langsam rangetastet und verschiedene Formeln für verschiedene Variablen aufgestellt.

Gesamtstrecke = Die Strecke am Ende + die km die man mit einer Dose laufen kann * Anzahl der Häufchen

Die Strecke am Ende = Die Autostrecke(also hier 500km) - (die maximale Zahl an Dosen mit denen man laufen kann * die km die man mit einer Dose laufen kann

Die Anzahl der Häufchen = (Autostrecke - die Strecke am Ende) / (Anzahl der benötigten Dosen - die maximale Zahl an Dosen mit denen man laufen kann)
oder
Die Anzahl der Häufchen = (Autostrecke - die Strecke am Ende) / die km die man mit einer Dose laufen kann

Stimmt das soweit?
und wie bekomme ich die Anzahl der benötigten Dosen die man für die Häufchen braucht raus?
(Also Anzahl benötigte Dosen = die maximale Zahl an Dosen mit denen man laufen kann + die benötigten Dosen die man für die Häufchen braucht)

 

[asipak4you]

Mich hat das mal interessiert und ich habe etwas dazu geschrieben:

<?php
error_reporting(E_ALL);

$km_finish = 500;
$num_cans = 450;

for ($i = 2; $i <= 10; $i = $i + 2) {
  echo '<p>pile-size: ' . $i . ' | result: ' . simulateDesertTrip($i, 12, $km_finish, $num_cans, 15) . '</p>';
}

function simulateDesertTrip($pile_size, $max_cans, $km_finish, $num_cans, $km_per_can) {
  // each entry in the array fits to a pile, their distance between each other is 15km minimum
  $piles = array($num_cans);
  // km, the person has gone
  $km_gone = 0;
  // pile position, number fits to the index of the piles array
  $pos = 0;

  // move until you have reached the finish or the last pile is empty
  while ($km_gone < $km_finish && $piles[count($piles)-1] > 0) {
    move($pos, $piles, $max_cans, $pile_size, $km_per_can, $km_gone);
  }

  return $km_gone;
}

function move(&$pos, array &$piles, $max_cans, $pile_size, $km_per_can, &$km_gone) {
  if ($pos == 0 && $piles[0] > floor(($max_cans - $pile_size) / 2)) {
    $cans = ($piles[0] - $max_cans >= 0 ? $max_cans : $piles[0]);
    $piles[0] -= $cans;
    ++$pos;
    if (!array_key_exists($pos, $piles)) {
      $piles[$pos] = 0;
    }
    if ($piles[$pos-1] == 0) {
      $size = $cans - floor($max_cans - $pile_size) / 2;
    }
    else {
      $size = $pile_size;
    }
    $piles[$pos] += $size;

    $km_gone += floor(($max_cans - $pile_size) / 2) * $km_per_can;

    // [debug]
//    echo '<p>gone: ' . floor(($max_cans - $pile_size) / 2) * $km_per_can . '</p>';
//    echo '<pre>array: ', print_r($piles), '</pre>';
  }
  else if ($piles[$pos-1] > 0 && $piles[$pos-1] > floor(($max_cans - $pile_size) / 2)) {
    --$pos;
    $km_gone -= floor(($max_cans - $pile_size) / 2) * $km_per_can;
  }
  else if ($pos == 0 || $piles[$pos-1] == 0 || $piles[$pos-1] <= floor(($max_cans - $pile_size) / 2)) {
    $cans = ($piles[$pos] - $max_cans > 0 ? $max_cans : $piles[$pos]);
    $piles[$pos] -= $cans;
    ++$pos;

    if (!array_key_exists($pos, $piles)) {
      $piles[$pos] = 0;
    }

    if ($piles[$pos-1] == 0) {
      $size = $cans - floor($max_cans - $pile_size) / 2;
    }
    else {
      $size = $pile_size;
    }
    $piles[$pos] += $size;

    if ($piles[$pos] > 0) {
      $gone = ($piles[$pos] > floor(($max_cans - $pile_size) / 2) ? floor(($max_cans - $pile_size) / 2) * $km_per_can : $piles[$pos] * $km_per_can);
    }
    else {
      $gone = 0;
    }
    
    $km_gone += $gone;

    // [debug]
//    echo '<p>gone: ' . $gone . '</p>';
//    echo '<pre>array: ', print_r($piles), '</pre>';
  }
}

Die auskommentierten Zeilen dienen zu Debugzwecken.

Ergebnis:

pile-size: 2 | result: 195

pile-size: 4 | result: 240

pile-size: 6 | result: 315

pile-size: 8 | result: 420

pile-size: 10 | result: 465

Alle Angaben rechts neben der Pipe in km.

Merkwürdig ist nur, dass das Ergebnis unter 500km liegt, ich die Strecke also gar nicht schaffen kann. Möglicherweise befindet sich noch ein Fehler im Script.

Ein paar Überlegungen dazu:

Die Größe eines Haufens muss meiner Meinung nach durch 2 teilbar sein, natürlich ohne Rest. Denn würde ich eine Haufengröße von beispielsweise 9 wählen, könnte ich 15km hin und 15km zurück laufen, lasse 9 Dosen auf dem Haufen liegen und bringe eine Dose mit zurück => sinnfrei.

Weitere Beobachtungen:

Schaut man sich nur mal einen einzigen Fall und nicht alle Fälle von einer Haufengröße von 2-10 an, z.B. bei einer Haufengröße von 6 bemerkt man relativ schnell, dass man, um alle Dosen auf den nächsten Haufen zu schleppen, immer die Hälfe der Dosen alleine für den Hin- und Rückweg „verbrennt“. 3 Dosen hin, 3 Dosen zurück und 6 auf dem Stapel. Man kann sich also auch schnell von Hand ausrechnen, was bei einer Haufengröße von 6 herauskommen müsste.

Das lässt sich auf alle Haufengrößen übertragen. Haufengröße 8 => Verlust 1/3 aller Dosen bei der Umschichtung des Haufens auf die nächsten 15km.

Vielleicht mag sich das ja mal jemand angucken und vielleicht entdeckt er/sie ja einen Fehler. Der code ist leider relativ undokumentiert, also viel Spaß!

Gruß

PS. pile soll Haufen bedeuten. Vermutlich blöd übersetzt.

 

[saftmeister]

Wie kompliziert. Die Lösung lautet: Iterativ vorgehen!

Hier mal die erste Runde:

Nimm 12 Dosen, laufe 30Km, lege 8 Dosen ab und laufe zurück... Mehr kann und will ich dazu nicht sagen.

Ist auf jeden Fall mal ein interessantes Problem, um sich mit Mathe an sich zu befassen, statt gleich los zu programmieren ;-)

Edit: Ich sage doch noch was dazu: Viele denken von Anfang daran, möglichst weit zu kommen mit einer Ladung. Suche nach einem Weg, soviele Dosen wie möglich abzulegen und dafür kürzere Strecken zu gehen. Letzendlich erhöht sich bei korrekter Anwendung des Algos die Anzahl der Hin- und Rück-Läufe.