4

问候，堆栈溢出。

假设我有两个用于计算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)

然而，我不知道如何进一步进行。

4

2 回答 2

8

我建议以直接递归的方式编写它并使用 memoization 来创建您的遍历：

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。即 osrr 1 2 3 将创建一个用于计算 A(2,3) 的表，然后对其进行清理。p您可以通过部分应用来重用该表：

osrr1 = osrr p

现在osrr1将在所有调用之间共享表（根据您的情况，这可能是也可能不是您想要的）。

于 2011-03-22T22:17:34.003 回答
1

首先，一定有一些你没有告诉我们的边界条件。

一旦你有了这些，尝试将解决方案声明为递归定义的数组。只要您知道 i 和 j 的上限，这就会起作用。否则，使用备忘录组合器。

于 2011-03-23T10:48:45.247 回答