Benutzer-Werkzeuge

Webseiten-Werkzeuge


examples:project_euler_-_problem_p115

Project Euler - Problem 115

Quelle

HINWEIS: Dies ist eine schwierigere Variante des Problem 114.

Eine Reihe mit der Länge n Einheiten enthält rote Blöcke der Mindestlänge m so, dass zwischen zwei roten Blöcken immer mindestens ein schwarzes Quadrat liegt. Die roten Blöcke dürfen verschiedene Längen haben. (Siehe Bild beim Problem 114.)

Die Füll-Funktion F(m,n) soll die Anzahl verschiedener Möglichkeiten darstellen, in denen die Reihe gefüllt werden kann.

Zum Beispiel sind F(3,29) = 673135 und F(3,30) = 1089155.

Das bedeutet, für m=3 ist ersichtlich, dass n = 30 der kleinste Wert ist, für den die Füll-Funktion eine Anzahl ergibt, die eine Million überschreitet. In der gleichen Weise findet man, dass F(10,56) = 880711 und F(10,57) = 1148904 ist, so das n = 57 der kleinste Wert ist, bei dem die Füll-Funktion zum ersten mal eine Anzahl von über eine Million Möglichkeiten anzeigt.

Für m = 50 finde den kleinsten Wert n für den die Füll-Funktion zum ersten mal eine Anzahl von einer Million Möglichkeiten übersteigt.

Antwort: Finde es selbst heraus mit Forth ;-)


Eine Lösung mit gforth (ist in 170 Millisecunden gelaufen):

#! /usr/bin/gforth
 
Create X 1000 cells allot  \ allocate X[1000]
 
50      constant M
1000000 constant L
0       value    R
 
: solve
    1 X !
    1
    begin
        0 over cells X + !
        dup M > if
            dup M - 0 do
                dup M - i - X i cells + @ * over cells X + dup @ rot + swap !
            loop
        then
        dup cells X + @ R + to R
        1+
        R L >
    until
    ." Solution is " 2 - . cr
;
 
solve
bye
examples/project_euler_-_problem_p115.txt · Zuletzt geändert: 2013-06-06 21:26 (Externe Bearbeitung)