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 +++++++++++++++++++++++++++
 1 file changed, 27 insertions(+)

(limited to 'AufgabeFFP3.hs')

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