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 的递归调用来代替 list-comprehension 列表单子。

这有点棘手，因为您必须正确处理边缘情况，我允许自己进行一些优化：

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（第一种情况）时 - 它会返回一个长度与ds
  • 如果剩余的总和没有0，但没有d剩下的，我们就有麻烦了，因为没有解决方案（第二种情况） - 请注意，没有解决方案只是空列表
  • 在其他所有情况下，我们都有一个非零n（剩余总和）和一些ds左（第三种情况）：
    • 现在寻找您可以为x( maxN) 选择的最大数字，记住x * d^2应该是<= n上限，n / d^2但我们只对整数感兴趣（所以它是floor）
    • x从0到尝试所有maxN
    • x将其与剩余的一起使用时寻找剩余总和的所有解决方案ds并选择其中一个xs
    • 结合x以xs给出当前子问题的解决方案

list-monad 的绑定将为您处理其余部分；）

例子

λ> 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

Step 2.solutions根据列表的结构递归定义：

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 回答