0

match を利用してフィボナッチ数列を作成する再帰関数を作成しようとしました。私は Euler2 を動作させましたが、Euler2a では、反復制約 j を除いて関数全体を自己完結型にしようとしています。

数列を提供するために Euler2a をどのように変更する必要がありますか?

どんなポインタでも大歓迎です。:)

Euler2 の結果

val Euler2 : list:int リスト -> i:int -> j:int -> int リスト

val z : int リスト = [1; 2; 3; 5; 8; 13; 21; 34; 55; 89]

Euler2a の結果

val Euler2a : j:int -> (int リスト -> int -> int -> int リスト)

val z2 : (int リスト -> int -> int -> int リスト)

Euler2

let rec Euler2 (list: int list) i j =
    match i with
    | 1 | 2         ->  Euler2 list (i+1) j
    | _ when (i<=j) ->  let newList = list @ [list.[list.Length - 1] + list.[list.Length - 2]]
                        Euler2 newList (i+1) j
    | _             ->  list

let z = Euler2 [1;2] 1 10

Euler2

let rec Euler2a (j:int) =
    let i = 1
    let list = [1;2]
    let rec Euler2b (list: int list) i j =
        match i with
        | 1 | 2         ->  Euler2b list (i+1) j
        | _ when (i<=j) ->  let newList = list @ [list.[list.Length - 1] + list.[list.Length - 2]]
                            Euler2b newList (i+1) j
        | _             ->  list
    Euler2b

let z2 = Euler2a 10
4

2 に答える 2

4

そのジョンの回答Euler2bの本文からの内部関数への再帰呼び出しの形式に関する差し迫った問題に加えて、採用されたアプローチに関連するあまり明白でない問題があります。Euler2a

  • 実装では、基本データ構造としてF# リストを使用します。Project Euler Problem 2を解決することはできますが、慣用的な F# リストというよりも、配列のように使用されます。式は、 indexers の使用からだけでなく、各反復で現在のリストを完全に破棄し、新しい要素を 1 つ長く再作成するappend 演算子からもlist @ [list.[list.Length - 1] + list.[list.Length - 2]]計算コストが非常に高くなり、ガベージ コレクションに不必要な圧力がかかります。リストの F# での慣用的な使用法は、次のように、リストを左から拡張し、最終ステップで反転させることです。list.[i]@

    let euler2c len =
    let rec inner (list: int list) i len =
        match list with
        | l::p::tail when (i < len) -> inner ((l + p)::l::p::tail) (i+1) len
        | _  ->  List.rev list
    inner [2;1] 2 len

  • ある長さのフィボナッチ数のリストを持つことは、元の問題を解決するのに便利ではありません。解決策は最後の要素の値に基づいている必要があり、おそらく追加のパラメーター/条件が必要になるからです。listからF# シーケンスに切り替えて、任意の長さのフィボナッチ シーケンスを遅延して表現することは、はるかに慣用的です。ライブラリ関数Seq.unfoldを使用すると、次のような簡潔なワンライナー実装が可能になります。

    let fibnums = Seq.unfold (fun(curr,next) -> Some(curr,(next,curr+next)))(1,2)

    fibnumstype of をseq<int>使用すると、ライブラリ関数とコンビネータを使用して慣用的に操作できます。特に、最後の要素が 4000000 を超えないシーケンスを作成することは、 のように簡単に表現できますfibs |> Seq.takeWhile ((>=) 4000000)。

于 2013-10-17T07:08:13.203 に答える