Computer les relations de récidive à Haskell

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

  •  28-10-2019
  •  | 
  •  

Question

Salutations, StackOverflow.

Disons que j'ai deux relations de récidive suivantes pour l'informatique 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})

Je voudrais calculer les valeurs S (0,0), S (0,1), S (1,0), S (2,0), etc ... de manière asymptotiquement optimale. Quelques minutes avec un crayon et du papier révèlent qu'il se déroule dans une structure Treeke qui peut être transversée de plusieurs manières. Maintenant, il est peu probable que l'arbre sera utile plus tard, donc pour l'instant je cherche à produire une liste imbriquée comme [[S(00)],[S(10),S(01)],[S(20),S(21),S(12),S(02)],...]. J'ai créé une fonction pour produire une liste plate de S (i, 0) (ou S (0, J), selon le premier argument):

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)

Je suis cependant à perte de savoir comment continuer.

Était-ce utile?

La solution

Je suggère de l'écrire dans un style récursif direct et d'utiliser la mémorisation pour créer votre traversée:

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')

La bibliothèque créera une table infinie pour stocker les valeurs que vous avez déjà calculées. Parce que les constructeurs de mémo sont sous le p paramètre, le tableau existe pour la portée de p; IE OSRR 1 2 3 créera un tableau dans le but de calculer A (2,3), puis de le nettoyer. Vous pouvez réutiliser le tableau pour un spécifique p en appliquant partiellement:

osrr1 = osrr p

À présent osrr1 Partagera le tableau entre tous ses appels (ce qui, selon votre situation, peut ou non être ce que vous voulez).

Autres conseils

Premièrement, il doit y avoir des conditions aux limites dont vous ne nous avez pas parlé.

Une fois que vous en avez, essayez d'indiquer la solution comme un tableau défini récursivement. Cela fonctionne tant que vous connaissez une limite supérieure sur I et J. Sinon, utilisez des combinateurs mémo.

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top