F# - Fibonacijev niz ogranicen velicinom elementa

[ Shadowed @ 30.01.2015. 09:24 ] @

Igram se malo u poslednje vreme F#-om pa sam se malo zaglavio

Naravno, najnezgodniji deo je izbacivanje imperativnog programiranja iz glave

Evo problema koji me trenutno muci. Racunanje fibonacijevog niza do n-tog elementa je jednostavno:

Code:

let rec fibonacci n =
    match n with
    | x when x <= 1 -> 1
    | _ -> (fibonacci (n-1) + fibonacci (n-2))

I mogu ga ispisati sa:

Code:

let rec PrintFib n =
  match n with
  | 1 -> printfn "%A" (fibonacci 1)
  | _ -> printfn "%A" (fibonacci n)
         PrintFib (n-1)

doduse, obrnutim redosledom sto takodje nisam uspeo da skontam kako da uradim da ide od najmanjeg, ali se oko toga nisam ni trudio (jos uvek)

Medjutim, ako je zadatak "prikazati sve elemente fib niza manje od N" onda nastaje problem.
Zapravo, cini mi se da je u oba slucaja problem sto se ide od najveceg ali ne kontam kako da okrenem..
Neki hint bi dobro dosao (ovo mi je vise kao mozgalica, nije mi za neki projekat)

Naravno, znam da mogu imperativno da uradim i u F#-u ali where the fun in that

[ mmix @ 30.01.2015. 12:01 ] @

Mislim da ne mozes rekurzivno, (mozda neka forward recursive muljavina) i bez da vuces prethodnu vrednost da bi je vratio kad izadjes iz opsega.

Ovo je imho idealan zadatak za "beskonacne" sekvence:

Code (csharp):

let fibMax maxN =

    Seq.unfold (fun (a, b) -> Some(a, (b, a + b))) (0, 1)

    |> Seq.pairwise 

    |> Seq.find(fun p -> fst p < maxN && snd p >= maxN) 

    |> fst

_{[Ovu poruku je menjao mmix dana 30.01.2015. u 14:16 GMT+1]}