2

素因数が2、3、5、ハミング数だけの数のリストを定義する必要があります。（つまり、2 ^ i * 3 ^ j * 5 ^ kの形式の番号。シーケンスは1、2、3、4、5、6、8、9、10、12、15、…で始まります）

factors関数を使用して、またはそれ以外の方法でそれを行うことができます。factors以下は、その引数の要素を返す必要があります。正しく実装できたと思います。

   factors :: Int -> [Int]
   factors n = [x | x <- [1..(div n 2) ++ n], mod n x == 0]

リスト内包表記を使用して2^i * 3 ^ j * 5 ^ kのリストを作成しようとしましたが、ガードの記述に行き詰まりました。

hamming :: [Int]
hamming = [n | n <- [1..], „where n is a member of helper“]

helper :: [Int]
helper = [2^i * 3^j * 5^k | i <- [0..], j <- [0..], k <- [0..]]
4

2 に答える 2

11

factors関数を使用して、またはそれ以外の方法でそれを行うことができます。

それ以外の方法で行うことをお勧めします。

簡単な方法の1つは、数値の素因数分解を取得する関数を実装することです。

isHamming :: Integer -> Bool
isHamming n = all (< 7) $ primeFactors n

次に、すべての正の整数のリストをフィルタリングするために使用されます。

hammingNumbers :: [Integer]
hammingNumbers = filter isHamming [1 .. ]

もう1つの方法は、除算とフィルタリングを回避し、ハミング数のみのリストを作成することです。

簡単な方法の1つnは、次の場合に限り、数値がハミング数であるという事実を使用することです。

  • n == 1、 また
  • n == 2*k、ハミング数はどこkですか、または
  • n == 3*k、ハミング数はどこkですか、または
  • n == 5*k、ここkで、はハミング数です。

次に、すべてのハミング数のリストを次のように作成できます。

hammingNumbers :: [Integer]
hammingNumbers = 1 : mergeUnique (map (2*) hammingNumbers)
                                 (mergeUnique (map (3*) hammingNumbers)
                                              (map (5*) hammingNumbers))

ここで、mergeUnique2つのソートされたリストをマージして、重複を削除します。

これはすでにかなり効率的ですが、最初から重複を生成しないようにすることで改善できます。

于 2013-03-23T17:52:29.130 に答える
2

セットhammingは

{2^i*3^j*5^k | (i, j, k) ∈ T}

どこ

T = {(i, j, k) | i ∈ [0..], j ∈ [0..], k ∈ [0..]}

ただし、[（i、j、k）|は使用できません。i <-[0 ..]、j <-[0 ..]、k<-[0..]]。このリストは、のような無限に多くのトリプルで始まるため(0, 0, k)です。
任意(i,j,k)のを指定するとelem (i,j,k) T、有限時間でTrueを返す必要があります。
おなじみですか？あなたは前に尋ねた質問を思い出すことができます： 増分ペアのhaskell無限リスト

その質問では、ハンマーがペアの答えを出しました。それをトリプルに一般化することができます。

triples = [(i,j,t-i-j)| t <- [0..], i <- [0..t], j <- [0..t-i]]
hamming = [2^i*3^j*5^k | (i,j,k) <- triples]
于 2013-03-23T18:51:29.140 に答える