3

以下を行うためのJコードを探しています。

2 3 4 5 7 21 45 49 61 ランダムな整数のリスト (ソート済み) があるとします。最初の要素から始めて、リスト内の要素の倍数を削除してから、次の要素に移動してその倍数をキャンセルしたいとします。などなど。

したがって、私が見ている出力は 2 3 5 7 61 です。基本的にはエラトステネスのふるいです。私はJを学んでいて、ほとんどのコードを取得するのが難しいと感じているので、誰かがコードも説明してくれれば幸いです:(

よろしく、babsdoc

4

2 に答える 2

4

それはまさにあなたが求めるものではありませんが、ここではSieve のより慣用的な (そしてはるかに高速な) バージョンがあります。

基本的に、必要なのは、どの数がどの数の倍数であるかを確認することです。これは、モジュロの表から取得できます。|/~

l =: 2 3 4 5 7 21 45 49 61
|/~ l
  0 1 0 1 1  1  1  1  1
  2 0 1 2 1  0  0  1  1
  2 3 0 1 3  1  1  1  1
  2 3 4 0 2  1  0  4  1
  2 3 4 5 0  0  3  0  5
  2 3 4 5 7  0  3  7 19
  2 3 4 5 7 21  0  4 16
  2 3 4 5 7 21 45  0 12
  2 3 4 5 7 21 45 49  0

倍数のすべてのペアは0、テーブルに を与えます。ここで、0自己モジュロ (2 mod 2、3 mod 3 など。0対角線上の s) に対応する s には関心がないので、それらを削除する必要があります。1これを行う 1 つの方法は、次のように、その場所に sを追加することです。

=/~ l
  1 0 0 0 0 0 0 0 0
  0 1 0 0 0 0 0 0 0
  0 0 1 0 0 0 0 0 0
  0 0 0 1 0 0 0 0 0
  0 0 0 0 1 0 0 0 0
  0 0 0 0 0 1 0 0 0
  0 0 0 0 0 0 1 0 0
  0 0 0 0 0 0 0 1 0
  0 0 0 0 0 0 0 0 1
(=/~l) + (|/~l)
  1 1 0 1 1  1  1  1  1
  2 1 1 2 1  0  0  1  1
  2 3 1 1 3  1  1  1  1
  2 3 4 1 2  1  0  4  1
  2 3 4 5 1  0  3  0  5
  2 3 4 5 7  1  3  7 19
  2 3 4 5 7 21  1  4 16
  2 3 4 5 7 21 45  1 12
  2 3 4 5 7 21 45 49  1

とも書ける(=/~ + |/~) l。

このテーブルから、最終的な数字のリストを取得します。列に , が含まれるすべての数字0が除外されます。

列を掛けるだけで、この除外リストを作成します。列に が含まれている場合0、その積は0それ以外の場合は正の数です。

*/ (=/~ + |/~) l
   256 2187 0 6250 14406 0 0 0 18240

最後のステップを実行する前に、これを少し改善する必要があります。0s とsだけに関心があるので、長い乗算を実行する理由はありませんnot-0。したがって、テーブルを作成するときは、各数値の「符号」を使用して0s とs のみを保持します (これは: です)。1signum*

* (=/~ + |/~) l
  1 1 0 1 1 1 1 1 1
  1 1 1 1 1 0 0 1 1
  1 1 1 1 1 1 1 1 1
  1 1 1 1 1 1 0 1 1
  1 1 1 1 1 0 1 0 1
  1 1 1 1 1 1 1 1 1
  1 1 1 1 1 1 1 1 1
  1 1 1 1 1 1 1 1 1
  1 1 1 1 1 1 1 1 1

それで、

*/ * (=/~ + |/~) l
  1 1 0 1 1 0 0 0 1

除外リストから、あなたはcopy:#最終的なリストへの数字:

l #~ */ * (=/~ + |/~) l
   2 3 5 7 61

また、

(]#~[:*/[:*=/~+|/~) l
   2 3 5 7 61
于 2012-11-29T00:38:37.193 に答える
2

暗黙の反復は通常、接続詞Powerを使用して行われます。完了のテストがフィックスポイントに到達する以外の何かである必要がある場合、DoWhile構造はうまく機能します。

このソリューションfilterMultiplesOfHeadでは、適用もフィルタリングもされていない数値がなくなるまで、繰り返し適用されます。すでに適用されている数字は、部分的な回答に蓄積されます。処理されるリストが空の場合、未処理のデータから処理済みのデータを分離するために使用されるボックスを取り除いた後、部分的な答えが結果になります。

   filterMultiplesOfHead=: {. (((~: >.)@ %~) # ]) }.
   appendHead=: (>@[ , {.@>@])/
   pass=: appendHead ; filterMultiplesOfHead@>@{:
   prep=: a: , <
   unfinished=: [: -. a: -: {:
   sieve=: [: ; [: pass^:unfinished^:_ prep

   sieve 2 3 4 5 7 21 45 49 61 
2 3 5 7 61

   prep 2 3 4 7 9 10
┌┬────────────┐
││2 3 4 7 9 10│
└┴────────────┘
   appendHead prep 2 3 4 7 9 10
2
   filterMultiplesOfHead 2 3 4 7 9 10
3 7 9
   pass^:2 prep 2 3 4 7 9 10
┌───┬─┐
│2 3│7│
└───┴─┘
   sieve 1-.~/:~~.>:?.$~100
2 3 7 11 29 31 41 53 67 73 83 95 97
于 2012-11-28T20:31:45.617 に答える