Forth-eV Wiki

Da qui

NOTA: È una versione più difficile di problem 114.

Una riga che misura n unità in lunghezza ha dei blocchi rossi aventi una lunghezza minima di m unità messi su essa, in modo che ogni due blocchi rossi (che possono essere di diversa lunghezza) sono separati da almeno uno nero.

Sia F(m,n) una funzione che ritorna il numero di modi in cui una riga può essere costruita.

Per esempio, F(3, 29) = 673135 e F(3, 30) = 1089155.

Quindi, per m = 3, abbiamo che n = 30 è il più piccolo valore di n per cui il valore della funzione F(3,n) supera un milione.

Allo stesso modo, per m = 10, può essere verificato che F(10, 56) = 880711 e F(10, 57) = 1148904, quindi n = 57 è il minimo valore di n per cui F(10,n) supera un milione.

Per m = 50, trovare il minimo valore di n per cui F(50,n) supera un milione.

Risposta: trovala da solo eseguendo il codice Forth!

Una soluzione in gforth (0.170 secondi):

#! /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