3

我需要在 Haskell 中编写一个或多个函数来解决中国剩余定理。它需要使用以下定义创建：

crt :: [(Integer, Integer)] -> (Integer, Integer)

答案看起来像

>crt [(2,7), (0,3), (1,5)]
(51, 105)

我想我有一个整体的想法，我只是没有知识来写它。我知道 crt 函数必须是递归的。我创建了一个辅助函数来将元组列表拆分为两个列表的元组：

crtSplit xs = (map fst xs, product(map snd xs))

在这个例子中，它给了我：

([2,0,1],105)

我想我需要知道的是为第一个列表中的每个元素创建一个列表。我将如何开始这样做？

4

2 回答 2

6

中国剩余定理有一个代数解，基于如果和互质x = r1 % m1，和x = r2 % m2可以简化为一个模方程。m1m2

为此，您需要知道什么是模逆以及如何使用扩展欧几里得算法有效地计算它。

如果你把这些部分放在一起，你可以用正确的折叠来解决中国剩余定理：

crt :: (Integral a, Foldable t) => t (a, a) -> (a, a)
crt = foldr go (0, 1)
    where
    go (r1, m1) (r2, m2) = (r `mod` m, m)
        where
        r = r2 + m2 * (r1 - r2) * (m2 `inv` m1)
        m = m2 * m1

    -- Modular Inverse
    a `inv` m = let (_, i, _) = gcd a m in i `mod` m

    -- Extended Euclidean Algorithm
    gcd 0 b = (b, 0, 1)
    gcd a b = (g, t - (b `div` a) * s, s)
        where (g, s, t) = gcd (b `mod` a) a

然后：

\> crt [(2,7), (0,3), (1,5)]
(51,105)
\> crt [(2,3), (3,4), (1,5)]  -- wiki example
(11,60)
于 2016-02-20T21:39:48.640 回答
2

无需进入代数，你也可以用蛮力解决这个问题。也许这就是你被要求做的。

对于您的示例，为独立于其他两个的每个 mod 创建一个列表（上限将是 mod 的最小公倍数，假设它们作为前提条件互质，即乘积，即 105）。这三个列表应该有一个可以满足所有约束的共同元素。

m3 = [3,6,9,12,15,...,105]
m5 = [6,11,16,21,...,101]
m7 = [9,16,23,30,...,100]

您可以使用Data.Set来查找这些列表的交集。现在，使用递归或折叠将此逻辑扩展到 n 个术语。

更新 也许更简单的方法是定义一个过滤器来创建一个具有固定余数的序列，并重复应用给定的对

Prelude> let rm (r,m) = filter (\x -> x `mod` m == r)

验证它是否有效，

Prelude> take 10 $ rm (1,5) [1..]                                               
[1,6,11,16,21,26,31,36,41,46]

现在，对于给定的示例，重复使用它，

Prelude> take 3 $ rm (1,5) $ rm (0,3) $ rm (2,7) [1..]        
[51,156,261]

当然我们只需要第一个元素，改为head

Prelude> head $ rm (1,5) $ rm (0,3) $ rm (2,7) [1..]       
51

我们可以用 fold 概括

Prelude> head $ foldr rm [1..] [(1,5),(0,3),(2,7)]                            
51
于 2016-02-20T22:06:20.947 回答