Benutzer-Werkzeuge

Webseiten-Werkzeuge


examples:project_euler_-_problem_p151

Project Euler - Problem 151

Quelle

In einem Kopierladen laufen 16 Aufträge jede Woche, für die jeweils ein Bogen spezielles farbechtes Papier der Größe A5 benötigt wird.

An jedem Montag Morgen öffnet der Vorarbeiter einen neuen Umschlag in dem ein großer Bogen des Spezialpapiers der Größe A1 ist. Er teilt ihn auf die Hälfte, und erhält so zwei Bögen der Größe A2. Dann teilt er einen solchen Bogen wiederum auf die Hälfte, und bekommt so zwei Bögen der Größe A3, und so macht er weiter, bis er einen Bogen der Größe A5 hat, der für den ersten Auftrag der Woche benötigt wird. Alle unbenutzten Bögen kommen in den Umschlag zurück.

Vor jedem folgenden Auftrag entnimmt er einen zufällig ausgewählten Bogen aus dem Umschlag.

Wenn der von der Größe A5 ist, wird er verwendet. Wenn der jedoch größer ist, beginnt er die 'teile-auf-die-Hälfte' Prozedur bis er hat was er braucht, und alle verbleibenden Bögen kommen immer wieder in den Umschag zurück.

Der erste und der letzte Auftrag jeder Woche sei ausgeschlossen. Wie groß ist dann die Wahrscheinlichkeit (je Woche), dass der Vorarbeiter einen einzelnen Bogen Papier in dem Umschlag findet?

Die Antwort soll auf sechs Decimalstellen gerundet im Format x.xxxxxx angegeben werden.

Antwort: Finde es selbst heraus mit Forth ;-)


Eine Lösung mit gforth:

#! /usr/bin/gforth
 
: p151  { a5 a4 a3 a2 -- F: res }
    0.0e                                              { F: res  }
    a5 a4 a3 a2 + + +                                 { W: left }
    1 left = a5 1 <> and if 1.0e to res then
    a5   0 > if a5 1-  a4     a3     a2    recurse  a5 s>d d>f f*  res f+    to res then
    a4   0 > if a5 1+  a4 1-  a3     a2    recurse  a4 s>d d>f f*  res f+    to res then
    a3   0 > if a5 1+  a4 1+  a3 1-  a2    recurse  a3 s>d d>f f*  res f+    to res then
    a2   0 > if a5 1+  a4 1+  a3 1+  a2 1- recurse  a2 s>d d>f f*  res f+    to res then
    left 0 > if res left s>d d>f f/                                          to res then
    res
;
 
1 1 1 1 p151
." The answer is " 6 set-precision f. cr
bye

Laufzeiten:

luca@tux-laptop:~/tmp$ time ./p151.fth
The answer is not given here, but was checked ok in project euler.

real    0m0.087s
user    0m0.084s
sys     0m0.004s
examples/project_euler_-_problem_p151.txt · Zuletzt geändert: 2013-06-06 21:26 (Externe Bearbeitung)