3

r(i,j)によって定義される再帰的に定義された関数値を計算したい

r i j  | i<0 || j<0   = 0
       | i==0 && j==0 = 1
       | otherwise    = (i-1) * r (i-2) j + r (i-1) (j-1)

明らかに、NxNこれらの係数の表は で計算できますO(N^2)。残念ながら、次のような単純な評価

[[r i j | j <-[0..50]]| i <- [0..50]]

とてつもなく効果のない方法 (指数関数的な複雑さ) で実行されます。どうやら、Haskell はそれぞれの再帰ツリー全体を構築し、r i j以前に計算された値などを無視しますr (i-1) (j-1)。

そのようなテーブルを計算するエレガントで効果的な方法は何ですか?

4

1 に答える 1

3

FUZxxl が言うように、これはメモ化の質問です。

r i j | i < 0 || j < 0 = 0
      | otherwise      = rss !! i !! j

rss = [[r' i j | j <- [0..]] | i <- [0..]]
  where r' 0 0 = 1
        r' i j = (i-1) * r (i-2) j + r (i-1) (j-1)

正確に最大 50 の値の明示的なテーブルが必要な場合は、前述のようtake 51 (map (take 51) rss)に、または[[r i j | j <-[0..50]]| i <- [0..50]]を使用できます。それ以外の場合は、直接呼び出しrまたは参照できrssます。

于 2012-05-17T09:41:56.413 に答える