2

F＃を学習するためのコードを記述します。次に例を示します。

let nextPrime list=
    let rec loop n=
        match n with
        | _ when (list |> List.filter (fun x -> x <= ( n |> double |> sqrt |> int)) |> List.forall (fun x -> n % x <> 0)) -> n
        | _ -> loop (n+1)
    loop (List.max list + 1)

let rec findPrimes num=
    match num with
    | 1 -> [2]
    | n -> 
        let temp = findPrimes <| n-1
        (nextPrime temp ) :: temp

//find 10 primes
findPrimes 10 |> printfn "%A"

私はそれがうまくいくことをとても嬉しく思います！

私は完全に再帰の初心者です

再帰は素晴らしいことです。

findPrimesは効率的ではないと思います。

可能であれば、誰かがfindPrimesを末尾再帰にリファクタリングするのを手伝ってくれますか？

ところで、最初のn個の素数を見つけるためのより効率的な方法はありますか？

4

5 に答える 5

4

質問の最初の部分に関して、再帰的なリスト作成関数を末尾再帰的に記述したい場合は、中間結果のリストを追加のパラメーターとして関数に渡す必要があります。あなたの場合、これは次のようになります

let findPrimesTailRecursive num =
    let rec aux acc num = 
        match num with
        | 1 -> acc
        | n -> aux ((nextPrime acc)::acc) (n-1)
    aux [2] num

再帰関数auxは、その結果を（acc-umulatorのように）便利にaccと呼ばれる追加のパラメーターに収集します。終了条件に達したら、蓄積された結果を吐き出すだけです。末尾再帰ヘルパー関数を別の関数でラップしたので、関数のシグネチャは同じままです。

ご覧のとおり、auxの呼び出しは唯一であり、したがって最後に、n<>1の場合に発生する呼び出しです。これで末尾再帰になり、whileループにコンパイルされます。

私はあなたのバージョンと私の時間を計り、2000の素数を生成しました。私のバージョンは16％高速ですが、それでもかなり遅いです。素数を生成するために、私は命令型配列ふるいを使用するのが好きです。あまり機能的ではありませんが、非常に（非常に）高速です。

于 2010-06-04T11:33:37.687 に答える
3

単純に書いてみませんか：

let isPrime n =
    if n<=1 then false
    else
        let m = int(sqrt (float(n)))
        {2..m} |> Seq.forall (fun i->n%i<>0)

let findPrimes n = 
    {2..n} |> Seq.filter isPrime |> Seq.toList

またはふるい（非常に速い）：

let generatePrimes max=
    let p = Array.create (max+1) true
    let rec filter i step = 
        if i <= max then 
            p.[i] <- false
            filter (i+step) step
    {2..int (sqrt (float max))} |> Seq.iter (fun i->filter (i+i) i) 
    {2..max} |> Seq.filter (fun i->p.[i]) |> Seq.toArray
于 2010-06-04T10:52:12.433 に答える
3

別の方法は、追加の継続引数を使用して、findPrimesの末尾再帰を作成することです。この手法は常に機能します。スタックオーバーフローを回避しますが、おそらくコードを高速化することはできません。

また、nextPrime関数を使用するスタイルに少し近づけます。

let nextPrime list=
    let rec loop n = if list |> List.filter (fun x -> x*x <= n) 
                             |> List.forall (fun x -> n % x <> 0) 
                     then n
                     else loop (n+1)
    loop (1 + List.head list)

let rec findPrimesC num cont =
        match num with
        | 1 -> cont [2]
        | n -> findPrimesC (n-1) (fun temp -> nextPrime temp :: temp |> cont)

let findPrimes num = findPrimesC num (fun res -> res)        
findPrimes 10

他の人が言っているように、素数を生成するより速い方法があります。

于 2010-06-04T11:46:31.113 に答える
2

ところで、最初のn個の素数を見つけるためのより効率的な方法はありますか？

ここでは、F＃でエラトステネスの高速任意サイズのふるいを説明しましたResizeArray。

> let primes =
    let a = ResizeArray[2]
    let grow() =
      let p0 = a.[a.Count-1]+1
      let b = Array.create p0 true
      for di in a do
        let rec loop i =
          if i<b.Length then
            b.[i] <- false
            loop(i+di)
        let i0 = p0/di*di
        loop(if i0<p0 then i0+di-p0 else i0-p0)
      for i=0 to b.Length-1 do
        if b.[i] then a.Add(p0+i)
    fun n ->
      while n >= a.Count do
        grow()
      a.[n];;
val primes : (int -> int)
于 2010-06-04T19:20:23.597 に答える
2

これは少し遅れていることを私は知っています、そして答えはすでに受け入れられました。ただし、末尾再帰を作成するための適切なステップバイステップガイドは、OPまたはその他の人にとって興味深いものになる可能性があると思います。これが確かに私を助けてくれたいくつかの秘訣です。他の人が述べているように、素数を生成するためのより良い方法があるので、私は素数生成以外の単純な例を使用するつもりです。

いくつかからカウントダウンする整数のリストを作成するcount関数の素朴な実装を考えてみましょうn。このバージョンは末尾再帰ではないため、長いリストの場合、スタックオーバーフロー例外が発生します。

let rec countDown = function
  | 0 -> []
  | n -> n :: countDown (n - 1)
(*         ^
           |... the cons operator is in the tail position
                as such it is evaluated last.  this drags
                stack frames through subsequent recursive
                calls *)

これを修正する1つの方法は、パラメーター化された関数を使用して継続渡しスタイルを適用することです。

let countDown' n =
  let rec countDown n k =
    match n with
    | 0 -> k [] (*            v--- this is continuation passing style *)
    | n -> countDown (n - 1) (fun ns -> n :: k ns)
(*          ^
            |... the recursive call is now in tail position *)
  countDown n (fun ns -> ns) 
(*              ^
                |... and we initialize k with the identity function *)

次に、このパラメーター化された関数を特殊な表現にリファクタリングします。関数countDown'が実際にカウントダウンしていないことに注意してください。これは、継続がいつ構築され、いつn > 0評価されるかというアーティファクトですn = 0。最初の例のようなものがあり、それを末尾再帰にする方法がわからない場合は、2番目の例を記述してから、それを最適化して関数パラメーターを削除することをお勧めしますk。それは確かに読みやすさを向上させます。これは、2番目の例の最適化です。

let countDown'' n =
  let rec countDown n ns =
    match n with
    | 0 -> List.rev ns  (* reverse so we are actually counting down again *)
    | n -> countDown (n - 1) (n :: ns)
  countDown n []
于 2012-01-25T20:11:44.893 に答える