3

我有一个计算 Motzkin 数的代码：

module Main where

    -- Program execution begins here
    main :: IO ()
    main = interact (unlines . (map show) . map wave . (map read) . words)

    -- Compute Motzkin number
    wave :: Integer -> Integer
    wave 0 = 1
    wave 1 = 1
    wave n = ((3 * n - 3) * wave (n - 2) + (2 * n + 1) * wave (n - 1)) `div` (n + 2)

但是即使是一个简单的数字的输出也30需要一段时间才能返回。

有什么优化思路吗？？

4

4 回答 4

10

有一个计算斐波那契数的标准技巧可以很容易地适应您的问题。斐波那契数的朴素定义是：

fibFunction :: Int -> Integer
fibFunction 0 = 1
fibFunction 1 = 1
fibFunction n = fibFunction (n-2) + fibFunction (n-1)

然而，这是非常昂贵的：因为递归的所有叶子都是1，如果fib x = y，那么我们必须执行y递归调用！由于斐波那契数呈指数增长，这是一种糟糕的情况。但是通过动态编程，我们可以共享两个递归调用所需的计算。令人愉快的单线看起来像这样：

fibList :: [Integer]
fibList = 1 : 1 : zipWith (+) fibList (tail fibList)

起初这可能看起来有点令人费解。这里的fibList参数zipWith作为前两个索引的递归，而tail fibList参数作为前一个索引的递归，这给了我们fib (n-2)和fib (n-1)值。1开头的两个s 当然是基本情况。这里还有其他关于 SO 的好问题可以更详细地解释这项技术，你应该研究这段代码和那些答案，直到你觉得你理解它是如何工作的以及为什么它非常快。

如有必要，可以Int -> Integer使用(!!).

让我们尝试将此技术应用于您的函数。与计算斐波那契数一样，您需要前一个值和倒数第二个值；并且还需要当前索引。这可以通过包含[2..]在对zipWith. 下面是它的外观：

waves :: [Integer]
waves = 1 : 1 : zipWith3 thisWave [2..] waves (tail waves) where
    thisWave n back2 back1 = ((3 * n - 3) * back2 + (2 * n + 1) * back1) `div` (n + 2)

和以前一样，可以使用(!!)or恢复函数版本genericIndex（如果确实需要Integer索引）。我们可以确认它在 ghci 中计算相同的函数（但更快，并且使用更少的内存）：

> :set +s
> map wave [0..30]
[1,1,2,4,9,21,51,127,323,835,2188,5798,15511,41835,113634,310572,853467,2356779,6536382,18199284,50852019,142547559,400763223,1129760415,3192727797,9043402501,25669818476,73007772802,208023278209,593742784829,1697385471211]
(6.00 secs, 3,334,097,776 bytes)
> take 31 waves
[1,1,2,4,9,21,51,127,323,835,2188,5798,15511,41835,113634,310572,853467,2356779,6536382,18199284,50852019,142547559,400763223,1129760415,3192727797,9043402501,25669818476,73007772802,208023278209,593742784829,1697385471211]
(0.00 secs, 300,696 bytes)
于 2016-09-20T19:50:30.233 回答
6

在 n=30 的情况下，您需要计算wave 29和wave 28，而这又需要计算wave 28、wave 27两次wave 26等等，这很快就会达到数十亿。

您可以使用与计算斐波那契数相同的技巧：

wave 0 = 1
wave 1 = 1
wave n = helper 1 1 2
    where
       helper x y k | k <n      = helper y z (k+1)
                    | otherwise = z
                    where z = ((3*k-3) * x + (2*k+1) * y) `div` (k+2)

这在线性时间内运行，并且助手具有每个k值 for wave (k-2)和wave (k-1)ready。

于 2016-09-20T18:54:33.297 回答
1

这是一个记忆的版本

wave = ((1:1:map waveCalc [2..]) !!)
    where waveCalc n = ( (2*n+1)*wave (n-1) + (3*n-3)*wave (n-2) ) `div` (n+2)
于 2016-09-20T19:07:01.137 回答
0

感谢大家的回应。根据我对 的理解Memoization，我将代码重写为：

mwave :: Int -> Int
mwave = (map wave [0..] !!)
  where wave 0 = 1
        wave 1 = 1
        wave n = ((3 * n - 3) * mwave (n - 2) + (2 * n + 1) * mwave (n - 1)) `div` (n + 2)

digits :: Int -> Int
digits n = (mwave n) `mod` 10^(100::Int)

关于如何输出模 10^100 的答案有什么想法吗？

于 2016-09-21T02:55:00.780 回答