3

モツキン数を次のように計算するコードがあります。

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, iffib x = yであるため、再帰呼び出しを実行する必要がありyます! フィボナッチ数は指数関数的に増加するため、これは悪い状態です。しかし、動的計画法を使用すると、2 つの再帰呼び出しで必要な計算を共有できます。このための楽しいワンライナーは次のようになります。

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

これは、最初は少し不可解に見えるかもしれません。ここでfibList引数 tozipWithは 2 つのインデックス前の再帰として機能し、引数は 1 つのインデックス前の再帰として機能し、とtail fibListの両方の値を与えます。最初の 2 つの s はもちろん基本ケースです。SO には、このテクニックをさらに詳しく説明する良い質問が他にもあります。このコードとその答えを、このコードがどのように機能し、なぜ非常に高速であるかを理解できるまで学習する必要があります。fib (n-2)fib (n-1)1

Int -> Integer必要に応じて、を使用してこれから型シグネチャを回復でき(!!)ます。

この手法を関数に適用してみましょう。フィボナッチ数の計算と同様に、前の値と最後から 2 番目の値が必要です。さらに、現在のインデックスが必要です。[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 に答える
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 に答える