通过Project Euler我将我的解决方案与here进行比较 .
对于问题8,我的代码产生正确的答案(通过网站上的校验金确认)23514624000 .
module Main where
import Data.List
main = do
print $ last (sort eulerEight)
eulerEight = doCalc [ x | x <- toDigits 7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450]
where
doCalc (_:[]) = []
doCalc (x:xs) = if 0 `notElem` take 13 (x:xs) && length (x:xs) > 12
then product (take 13 (x:xs)) : doCalc xs
else doCalc xs
toDigits n
| n < 1 = []
| otherwise = toDigits (n `div` 10) ++ [n `mod` 10]
我意识到这可能要好得多,所以检查解决方案here并且它似乎不正确 .
import Data.Char (digitToInt)
import Data.List
problem_8 = do
str <- readFile "number.txt"
-- This line just converts our str(ing) to a list of 1000 Ints
let number = map digitToInt (concat $ lines str)
print $ maximum $ map (product . take 13) (tails number)
我检查了number.txt中的数字是否正确,并且两个示例都包含完整的1000位数字 . 任何人都可以阐明产出不同的原因吗? (我想也许可以用它使用的事实 tails
而不是 tail
,但我不确定)
2 回答
发生的事情是
digitToInt
返回一个Int
,它在32位系统上太短,无法在5增加到13时保存测试数 . 将其更改为(fromIntegral . digitToInt)
并且它可以正常工作 .该问题已被识别为Int溢出,但维基代码本身不正确 . 它没有正确地截断列表,并且可能产生不正确的结果,这取决于输入数据(即,它在这里通过幸运机会产生正确的结果) .
想象一下一串数字,以
0
结尾,然后是129
. 在计算最大值时,代码将错误地考虑9^12
. 更简单的是,对于1000个零,它将产生1作为答案 .由于压缩的特性,我们可以实现自动截断:
您的代码虽然正确,但有一些问题:
[x | x <- xs]
刚刚xs
last (sort xs)
只是maximum xs
,这更快附加在递归调用右侧的
是效率低下的已知来源 . 最好是在左边追加并在最后反转,但下面的转换更多是Haskellian: