好玩的题, 题目是这样的: 这里我们有三个 God, A, B, C. 对应着 True-God, False-God, Random-God, 当然, 你不知道具体对应关系如何. True-God 的回答总是正确的, False-God 的回答总是错误的, 而 Random-God 的回答是随机的. God 使用单词 ja, da 代表 Yes 和 No, 当然, 你也不知道具体哪个是 Yes, 哪个是 No. 你有三次机会, 每次只能问其中一个 God 问题, 问如何判断 A B C 的对应关系. 在看了提示后想到如下解决方法: 题目对于 Random-God 的行为表述不是很清楚, 比如回答前是否需要知道答案. 这里我们假设 Random-God 在确立随机性前需要知道答案是什么. 我们使用一道邪恶的题目, "你对本题的回答是永远一样的么?", 这样 False-God 和 Random-God 遇到这题就傻B了, 而 True-God 的答案(无论是 ja, da) 对应着 Yes. 然而, 虽然这个问题很邪恶, 但是无法判断连着两次提问遇到傻 B 的情况. 判断树深度大于 3, so, 解决方法不行. 继续看提示, 发现可以这么问, 比如问 A, "如果我问'B 是 Random-God 么?', 你会回答 `ja` 对么?", 这么一来, 如果回答的是 `ja`, 那么要么 A 是 Random-God, 给出了随机答案; 要么 B 是 Random-God(这两种情况下, C 都不会是 Random-God). 如果回答的是 `da`, 则要么 A 是 Random-God; 要么 B 不是 Random-God(这两种情况下, B都不会是 Random-God). 这样一来, 我们起码知道了一个不是 Random-God, 假设它为 C, 问它 "如果我问'你是 True-God 么?', 你会回答 `ja` 对么?", 那么他回答 `ja` 就代表它是..... 如果他回答 `da` 就代表它是...... 继续问这个 C, "如果我问'B 是 Random-God 么?', 你会回答 `ja` 对么?",..... Orz.... 很绕啊~~~ "如果我问'你明白了么?', 你会回答 `ja` 对么?"
2009年7月31日星期五
这是逻辑? Three Idols
2009年7月29日星期三
2009年7月15日星期三
Compile haskell package on win32
Many haskell packages depends on some libs, for e.g. libssl, libcurl, ...
so, when that goes to win32, things become complicated...
I find an easy way to do it:
Install Dev-cpp and use its devpackage system. There are lots of packages for c/c++, so when compile haskell packages:
simply pass --extra-include-dirs= and --extra-lib-dirs= to Setup.[l]hs
2009年7月14日星期二
质数/素数 Haskell 求解
在 ProjectEuler 经常遇到质数求解的问题, 需要一个够强大的算法.
尝试自己写了个, 用了 Memoization:
primeList :: [Integer]
primeList
= 2:3:5:[p | p <- [7,9..]
, all ((0 /=) . mod p) $ takeWhile (<= ceiling $ sqrt $ fromInteger p) primeList ]
在 Hugs 下测试:
Main> primeList !! 1000 7927 :: Integer (3341273 reductions, 4756123 cells, 5 garbage collections)貌似不错, 但是很明显, 代码适用范围有限, 例如 primeList !! 10000 在半天后终于出结果. ssword 提供了一个更短的算法, 目测貌似没我的效率高:
primes :: [Integer]
primes = sieve [2..]
where sieve (p : xs) = p : sieve [x | x <- xs, x `mod` p > 0]
代码相当巧妙, 很不错的筛选法, 但是效率实测... 估计是时间花在 [] 上和不断的回朔上, Lazy 嘛~ 发现用到下个值只好回朔到 2, 3, 5, 7, 11, 13....
Main> primes !! 1000 7927 :: Integer (35111063 reductions, 51142767 cells, 59 garbage collections)以上算法都只是处理小质数数列, 遇到大质数.... 全部死掉. PS, stack overflow. 熟悉的错误. 我找到了这个 http://en.wikipedia.org/wiki/Miller-Rabin_test, 感觉不错, 下面的 Haskell 算法是自己写的, 很丑陋.... 根据 Python 代码改的. Miller Rabin 筛选法.
-- Miller-Rabin methold By Andelf
-- true for p < 10^16 except `46 856 248 255 981’, so you can add 13
-- optimize: order of and, or, any, all/ all judge to odd/even
isPrime :: Integer -> Bool
isPrime p
| p == 2 = True
| even p || p < 2 = False
| otherwise
= all (isPrimeTest p) (takeWhile (< p) [2, 3, 7, 61, 24251])
where
isPrimeTest :: Integer -> Integer -> Bool
isPrimeTest n a
= odd d || t == n - 1
where
(t, d) = loop (pow a (n-1) n) (shiftTillOdd (n - 1))
loop t d = if t /= 1 && d /= n - 1 && t /= n - 1
then loop (t * t `mod` n) (d + d)
else (t, d)
shiftTillOdd = until odd $ flip div 2
pow :: Integer -> Integer -> Integer -> Integer
pow a d n
| even d = pow (a * a `mod` n) (d `div` 2) n `mod` n
| d == 1 || a == 1 = a
| otherwise = pow (a * a `mod` n) (d `div` 2) n * a `mod` n
本来想用 AKS 的, 后来发现在多项式判断那块时间太长, 所以还是采用了伪素数算法, 你所看到的第 2 行注释, p < 10^16 except `46 856 248 255 981’ 是没问题的.
代码经过简单优化, guard 判断的分支顺序可能很诡异, mod, even, odd, 等函数的使用可能也很诡异, 但请相信这个是在 Hugs 下测试过的, 目前是最优. div/(+) 就是比 Data.Bits 快很多. 很诡异. ghc 同学请自己权衡. 再次动手可能在 pow 函数上. [2, 3, 7, 61, 24251] 的选择请参考链接.
Main> head $ filter isPrime [10 ^ 100..] 100000000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000267 :: Integer (8965148 reductions, 25399307 cells, 29 garbage collections)参考链接 不是最优, 仅供参考.
订阅：
博文 (Atom)
博文
