0

Haskellで次の問題を解決したい：

n を自然数とし、A = [d_1 , ..., d_r]を正数の集合とする。

次の方程式のすべての正の解を見つけたいです。

n = Sum d_i^2 x_i.

たとえば、 ifn= 12と set A= [1,2,3]. 次の方程式を自然数上で解きたいと思います。

x+4y+9z=12.

次のコードを使用するだけで十分です。

[(x,y,z) | x<-[0..12], y<-[0..12], z<-[0..12], x+4*y+9*z==12]

私の問題は、 n が固定されておらず、セット A も固定されていない場合です。セット A によってインデックス付けされた一定量の変数を「生成」する方法がわかりません。

4

2 に答える 2

3

doリスト内包表記の代わりに、リストモナドの -notation を使用して再帰呼び出しを使用できます。

エッジケースを正しく処理する必要があるため、少しトリッキーです。少し最適化することができました。

solve :: Integer -> [Integer] -> [[Integer]]
solve 0 ds = [replicate (length ds) 0]
solve _ [] = []
solve n (d:ds) = do
  let maxN = floor $ fromIntegral n / fromIntegral (d^2)
  x <- [0..maxN]
  xs <- solve (n - x * d^2) ds
  return (x:xs)

それはこのように動作します：

  • 最初の引数で残りの合計を追跡しています
  • この合計が0ある場合、明らかに行われ、0 のみを返す必要があります (最初のケース) - と同じ長さの 0 のリストを返しますds
  • 残りの合計が ではない0のに が残っていないd場合、解決策がないため問題が発生します (2 番目のケース) - 解決策がないのは単なる空のリストであることに注意してください
  • 他のすべてのケースでは、非ゼロn(残りの合計) といくつかのds残り (3 番目のケース) があります。
    • 次に、選択できる最大数を探しますx( )上限はであるべきですが、整数のみに関心があるmaxNことを覚えておいてください (つまり です)x * d^2<= nn / d^2floor
    • xから まで0のすべてを試すmaxN
    • xこれを残りの合計で使用する場合、残りの合計のすべてのソリューションを探し、dsそれらのいずれかを選択しますxs
    • と組み合わせxてxs、現在の部分問題の解を与える

リストモナドのバインドが残りを処理します;)

例

λ> solve 12 [1,2,3]
[[0,3,0],[3,0,1],[4,2,0],[8,1,0],[12,0,0]]

λ> solve 37 [2,3,4,6]
[[3,1,1,0],[7,1,0,0]]

述べる

負の数を扱う場合、これは失敗します - 必要な場合は、さらにいくつかのケースを導入する必要があります - きっと理解できます (この時点では、Haskell よりも実際に数学的です)。

于 2016-05-04T04:22:23.160 に答える
1

いくつかのヒント:

最終的には、次のシグネチャを使用して関数を記述します。

solutions :: Int -> [Int] -> [ [Int] ]

例:

solutions 4 [1,2]  == [ [4,0], [0,1] ]
  -- two solutions: 4 = 4*1^2 + 0*2^2,  4 = 0*1^2 + 1*2^2

solutions 22 [2,3]  == [ [1,2] ]
  -- just one solution: 22 = 1*2^2 + 2*3^2

solutions 10 [2,3]  == [ ]
  -- no solutions

solutionsステップ 2.リストの構造に基づいて再帰的に定義します。

solutions x [a] = ...
  -- This will either be [] or a single element list

solutions x (a:as) = ...
  -- Hint: you will use `solutions ... as` here
于 2016-05-04T04:09:32.747 に答える