2

我刚刚遇到一个具有挑战性的问题（来自编程竞赛实践），其中包含以下递归序列

给定 3 个数字mnk找到元素 a[k] 其中

a[0] = m
a[1] = n
a[i] = a[i-1] + a[i-2] ; if floor(i/2) mod 2 = 1
a[i] = a[i-1] - a[i-4] ; if floor(i/2) mod 2 = 0

示例：对于 m=2 n=3 k=6 答案为 9

a[0] = 2
a[1] = 3
a[2] = 3 + 2 = 5
a[3] = 5 + 3 = 8
a[4] = 8 - 2 = 6
a[5] = 6 - 3 = 3
a[6] = 3 + 6 = 9
...

这就是我生成序列的方式（这显然会消耗大量堆栈并且即使对于前 100 个元素也非常慢）

 1 fbm :: Int → Int → Int → Int
 2 fbm m n 0 = m
 3 fbm m n 1 = n
 4 fbm m n x = let a = fbm m n (x-1)
 5                 b = fbm m n (x-2)
 6                 c = fbm m n (x-4)
 7             in case (x `div` 2) `mod` 2 of
 8                 1 →  a + b
 9                 0 →  a - c
10 
11 fbs m n = map (λx→fbm m n x) [0..]

由于需要在大（〜1000+）索引处查找元素的问题。我尝试通过尝试仅在具有 4 个输入的函数上限制计算并在列表上递归地应用具有4 个元素窗口的函数但无法成功实现它们中的任何一个（这意味着我无法弄清楚如何做）

fs1 = map fst $ iterate next (a,b)
  where next (a,b) = something

fs2 = m:n:scanl (gen) 2 fs2 
  where gen [a,b,c,d] = something

fs3 = scanl (genx m n 0 0) (repeat 0)
  where genx a b c d = something

问题1：我的任何方法都是解决这个问题的好方法吗？（+请给我一个如何做的例子）

问题2：如果我走错了路，你会如何解决这种问题？

4

2 回答 2

2

我想提出两个解决方案，它们也是基于 dbaupp 在这里介绍的记忆的概念。与现有答案不同，以下解决方案使用索引而不是先前元素的值来计算列表的新元素。

第一个想法如下

fbs :: Int -> Int -> [Int]
fbs m n = m : n : map (fbMake m n) [2 ..]

fbMake :: Int -> Int -> Int -> Int
fbMake m n = f
  where f i | (i `div` 2) `mod` 2 == 1 = (xs !! (i - 1)) + (xs !! (i - 2))
            | otherwise                = (xs !! (i - 1)) - (xs !! (i - 4))
        xs = fbs m n

fbs m n该解决方案从其记忆的前辈构建列表元素。不幸的是，由于列表索引的O(n)性能相当差。

在索引方面有什么比列表更好的呢？数组开始发挥作用。这是第二个解决方案。

import Data.Array

fbs :: Int -> Int -> Int -> [Int]
fbs m n k = m : n : map (fbm m n k) [2 .. k]

fbsArr :: Int -> Int -> Int -> Array Int Int
fbsArr m n k = listArray (0, k) (fbs m n k)

fbm :: Int -> Int -> Int -> Int -> Int
fbm m n k i | (i `div` 2) `mod` 2 == 1 = (xs ! (i - 1)) + (xs ! (i - 2))
            | otherwise                = (xs ! (i - 1)) - (xs ! (i - 4))
  where xs = fbsArr m n k

它与第一个几乎相同，但这次结果被存储在一个数组中，并且索引其元素的速度明显更快。根据我的测试，它生成答案的(m, n, k) = (2, 3, 1000)速度比基于列表的方法快 10 倍以上。在这种情况下，答案是fbsArr m n k ! k。

于 2013-01-30T08:53:34.260 回答
2

这个问题类似于“斐波那契数列”，但在我看来，它们之间有很大的不同。
记忆化是解决此类问题的常用技术。
例如，我们可以用它来计算斐波那契数列。
下面是一个非常简单的说明。它不如那个zipWith解决方案，但它仍然是一个线性操作实现。

fib :: Int -> Integer
fib 0 = 1
fib 1 = 1
fib n = fibs !! (n-1) + fibs !! (n-2)

fibs :: [Integer]
fibs = map fib [0..]

如果我们尝试模仿上面的fib和fibs，也许我们会写下面的代码。

fbm :: Int -> Int -> Int -> Int
fbm m n 0 = m
fbm m n 1 = n
fbm m n x = let a = fbs m n !! (x-1)
                b = fbs m n !! (x-2)
                c = fbs m n !! (x-4)
            in case (x `div` 2) `mod` 2 of
                   1 ->  a + b
                   0 ->  a - c

fbs :: Int -> Int -> [Int]
fbs m n = map (fbm m n) [0..]

但是上面fbs的也超级慢。用数组替换列表几乎没有什么区别。原因很简单，调用的时候没有memoization fbs。fibs如果我们比较 和 的类型签名，答案会更清楚fbs。

fibs :: [Integer]
fbs :: Int -> Int -> [Int]

其中一个是整数列表，另一个是函数。
为了让记忆发生，我们必须以另一种方式实现 fbs。
例如

fbs m n = let xs = map fbm [0..]
              fbm 0 = m
              fbm 1 = n
              fbm x = let a = xs !! (x-1)
                          b = xs !! (x-2)
                          c = xs !! (x-4)
                      in case (x `div` 2) `mod` 2 of
                             1 ->  a + b
                             0 ->  a - c
          in xs

尾递归是此类问题的另一种常见方法。

fbm :: Int -> Int -> Int -> (Int, Int, Int, Int)
-- a[0] = m
-- a[1] = n
-- a[2] = m + n
-- a[3] = m + 2 * n
fbm m n 3 = (m+2*n, m+n, n, m)
fbm m n x = case (x `div` 2) `mod` 2 of
                 1 -> (a+b, a, b, c)
                 0 -> (a-d, a, b, c)
  where (a,b,c,d) = fbm m n (x-1)

最后但同样重要的是，这是一个数学解决方案。

a[0] = m
a[1] = n
a[2] = m + n
a[3] = m + 2n
a[4] = 2n
a[5] = n
a[6] = 3n
a[7] = 4n
a[8] = 2n

fbs m n = [m, n, m+n, m+2*n] ++ cycle [2*n, n, 3*n, 4*n]
于 2013-01-30T12:00:44.563 回答