From db406f6812171d6f9ed6049779d0cbde7072caf2 Mon Sep 17 00:00:00 2001
From: totycro <totycro@unknown-horizons.org>
Date: Mon, 23 Apr 2012 20:45:20 +0200
Subject: zweiter teil des 3. blattes

---
 AufgabeFFP3.hs     | 27 +++++++++++++++++++++++++++
 TestAufgabeFFP3.hs | 21 ++++++++++++++++++++-
 2 files changed, 47 insertions(+), 1 deletion(-)

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 ->
-- 
cgit v1.2.3