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

この問題は「フィボナッチ数列」に似ていますが、私の意見では、両者には大きな違いがあります。
メモ化は、この種の問題を解決するための一般的な手法です。
たとえば、フィボナッチ数列を計算するために使用できます。
以下は非常に簡単な図です。その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も非常に遅いです。リストを配列に置き換えても、ほとんど違いはありません。理由は単純で、 を呼び出すときにメモ化が行われないからfbsです。と の型シグネチャを比較すると、答えはより明確にfibsなりfbsます。

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

1 つは整数のリストで、もう 1 つは関数です。
メモ化を行うには、別の方法で 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

末尾再帰は、この種の問題に対するもう 1 つの一般的なアプローチです。

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 に答える
2

ここで dbaupp によって導入されたメモ化の概念にも基づいた 2 つのソリューションを提案したいと思います。既存の回答とは異なり、次のソリューションは、前の要素の値の代わりにインデックスを使用して、リストの新しい要素を計算します。

最初のアイデアは次のとおりです

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)かなり不十分です。

索引付けに関して、リストより優れているものは何ですか? 配列が登場します。これが2番目の解決策です。

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 に答える