From 036885a5375d0eada3b03d200fcc6353985a624b Mon Sep 17 00:00:00 2001
From: totycro <totycro@unknown-horizons.org>
Date: Tue, 29 May 2012 21:04:14 +0200
Subject: minfree divide & conquer von folien

---
 AufgabeFFP8.hs | 34 +++++++++++++++++++++++++++++++---
 1 file changed, 31 insertions(+), 3 deletions(-)

(limited to 'AufgabeFFP8.hs')

diff --git a/AufgabeFFP8.hs b/AufgabeFFP8.hs
index 298898b..e667654 100644
--- a/AufgabeFFP8.hs
+++ b/AufgabeFFP8.hs
@@ -47,13 +47,41 @@ search_countlist = length . takeWhile (/= 0) . elems
 
 -- basic divide-and-conquer
 minfree_b :: [Int] -> Int
+minfree_b xs = 	if (null ([0..b-1] \\ us))
+								then (head ([b..] \\ vs))
+								else (head ([0..] \\ us))
+								where
+								(us, vs) = partition (<b) xs
+								b = 1 + (length xs) `div` 2
 
 -- refined divide-and-conquer
---minfree_r :: [Int] -> Int
+minfree_r :: [Int] -> Int
+minfree_r xs = minfrom 0 xs
+
+minfrom :: Int -> [Int] -> Int
+minfrom a xs
+	| null xs = a
+	| length us == b-a = minfrom b vs
+	| otherwise = minfrom a us
+	where
+	(us, vs) = partition (<b) xs
+	b = a + 1 + (length xs) `div` 2
 
 -- optimised divide-and-conquer
---minfree_o :: [Int] -> Int
---
+minfree_o :: [Int] -> Int
+minfree_o xs = minfrom_o 0 (length xs, xs)
+
+minfrom_o :: Int -> (Int, [Int]) -> Int
+minfrom_o a (n, xs)
+	| n == 0 = a
+	| m == b-a = minfrom_o b (n-m, vs)
+	| otherwise = minfrom_o a (m, us)
+	where 
+	(us, vs) = partition (<b) xs
+	b = a + 1 + n `div` 2
+	m = length us
+
+
 -- basic divide-and-conquer mittels higher order function
 --minfree_bhof :: [Int] -> Int
 
-- 
cgit v1.2.3