Haskellの再発関係を計算します

StackOverflow https://stackoverflow.com/questions/5397578

  •  28-10-2019
  •  | 
  •  

質問

挨拶、スタックフロー。

コンピューティングのために2つの再発関係があるとしましょう s（i、j）

S_{i,j+1} = X_{PA}S_{i,j} + \frac{1}{2p}(iS_{i-1,j}+jS_{i,j-1}) \\ S_{i+1,j} = X_{PB}S_{i,j} + \frac{1}{2p}(iS_{i-1,j}+jS_{i,j-1})

値を計算したいのですが S（0,0）, S（0,1）, S（1,0）, S（2,0）, 、など...漸近的に最適な方法で。鉛筆と紙で数分で、それがいくつかの方法で横断できるツリーの構造に展開することを明らかにしています。今、それはありそうもないツリーが後で役に立つので、今のところはネストされたリストを作成しようとしています [[S(00)],[S(10),S(01)],[S(20),S(21),S(12),S(02)],...]. 。のフラットリストを作成する関数を作成しました s（i、0） （また S（0、j）, 、最初の引数に応じて）：

osrr xpa p predexp = os00 : os00 * (xpa + rp) : zipWith3 osrr' [1..] (tail osrr) osrr
  where
    osrr' n a b = xpa * a + rp * n * b
    os00  = sqrt (pi/p) * predexp
    rp    = recip (2*p)

しかし、私はさらに進む方法として途方に暮れています。

役に立ちましたか？

解決

直接再帰スタイルで書いて、メモを使用してトラバーサルを作成することをお勧めします。

import qualified Data.MemoCombinators as Memo

osrr p = memoed
    where
    memoed = Memo.memo2 Memo.integral Memo.integral osrr'
    osrr' a b = ...  -- recursive calls to memoed (not osrr or osrr')

ライブラリは、既に計算した値を保存する無限のテーブルを作成します。メモコンストラクターが下にあるためです p パラメーター、テーブルは範囲のために存在します p; IE OSRR 1 2 3は、A（2,3）を計算する目的でテーブルを作成し、それをクリーンアップします。特定のテーブルを再利用できます p 部分的に適用することにより：

osrr1 = osrr p

今 osrr1 すべての呼び出しの間でテーブルを共有します（これは、あなたの状況に応じて、あなたが望むものである場合とそうでない場合があります）。

他のヒント

まず、あなたが私たちに言っていないいくつかの境界条件がなければなりません。

それらを手に入れたら、解決策を再帰的に定義された配列として述べてみてください。これは、IとJの上限を知っている限り機能します。それ以外の場合は、メモコンビネーターを使用します。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top