2 files changed, 47 insertions, 1 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
+
diff --git a/TestAufgabeFFP3.hs b/TestAufgabeFFP3.hs
index bbb5fbc..c83099c 100644
--- a/TestAufgabeFFP3.hs
+++ b/TestAufgabeFFP3.hs
@@ -15,8 +15,27 @@ cases1 = TestLabel "foo" $ TestList [
         TestCase $ assertEqual "e" ((selector2 . (filter 5) . transformer . generator) [(5,13),(2,7),(2,6),(10,100)]) [([(2,7),(2,6)],4,13)]
         ]
 
+cases2 = TestLabel "bar" $ TestList [
+  TestCase $ assertEqual "a" [ binomS (8, i) | i <- [0..7] ] [ binom (8, i) | i <- [0..7] ],
+  TestCase $ assertEqual "a" (binom (1,1)) (binomS (1,1)),
+  TestCase $ assertEqual "a" (binom (2,1)) (binomS (2,1)),
+  TestCase $ assertEqual "a" (binom (18,12)) (binomS (18,12))
+        ]
+
+cases3 = TestLabel "bar" $ TestList [
+  TestCase $ assertEqual "a" [ binomM (8, i) | i <- [0..7] ] [ binom (8, i) | i <- [0..7] ],
+  TestCase $ assertEqual "a" (binom (1,1)) (binomM (1,1)),
+  TestCase $ assertEqual "a" (binom (2,1)) (binomM (2,1)),
+  TestCase $ assertEqual "a" (binom (18,12)) (binomM (18,12))
+        ]
+
+cases4 = TestLabel "bar" $ TestList [
+  TestCase $ assertEqual "a" ( [binomS (n, k) | k <- [0..50], n <- [k..50] ] ) ( [binomM (n, k) | k <- [0..50], n <- [k..50] ] ) 
+        ]
+
+
 tests :: [Test]
-tests = [cases1]
+tests = [cases1, cases2, cases3, cases4]
 
 main = do
   forM tests $ \test ->