minfree divide & conquer von folien

1 files changed, 31 insertions, 3 deletions

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