zweiter teil des 3. blattes

1 files changed, 27 insertions, 0 deletions

diff --git a/AufgabeFFP3.hs b/AufgabeFFP3.hs
index 67519be..459f510 100644
--- a/AufgabeFFP3.hs
+++ b/AufgabeFFP3.hs
@@ -69,3 +69,30 @@ selector2 l = [ x | x <- best, getWeight x == min ]
         min = minimum $ map getWeight best
         best = selector l 
 
+
+-- pascal's triangle from exercise 1
+pd :: [[Integer]]
+pd = [[1]] ++ (zipWith (\x y -> zipWith (+) ([0] ++ x) (y ++ [0])) pd pd)
+
+-- naive
+binom :: (Integer, Integer) -> Integer
+binom (n, k)
+                | k == 0 || n == k = 1
+                | otherwise = binom (n-1, k-1) + binom (n-1, k)
+
+-- stream using pascal
+binomS :: (Integer, Integer) -> Integer
+binomS (n, k) = pd !! fromInteger n !! fromInteger k
+
+-- calc table 
+binomMemoTable :: [[Integer]]
+binomMemoTable = [ [ binomM (n, k)  | k <- [0..] ] | n <- [0..] ]
+
+-- using memoisation
+-- base case or recursion formula using lookup table
+binomM :: (Integer, Integer) -> Integer
+binomM (n, k) 
+        | k == 0 || n == k = 1
+        | otherwise = get (n-1) (k-1) + get (n-1) (k)
+        where get n k = binomMemoTable !! fromInteger n !! fromInteger k
+