欧拉项目8
浏览欧拉项目我在这里比较我的解决方案。
对于问题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]
我意识到在这里检查解决方案可能会好很多,但似乎并不正确。
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)
我已经更改了5取13的值作为Project Euler网站上的问题,但是上面的代码产生了2091059712的错误答案。我已经检查了number.txt中的数字是否正确,并且它具有两个例子都是1000位数字。 任何人都可以阐明为什么产量不同吗? (即时考虑可能与它使用tails
而不是tail
的事实,但我不知道)
发生的事情是, digitToInt
返回一个Int
,在32位系统上,当5增加到13时,它太短而无法保存测试数字。将其更改为(fromIntegral . digitToInt)
并且它工作正常。
该问题已被确定为Int溢出,但维基代码本身不正确。 它不会正确截断列表,并且可能会产生不正确的结果,具体取决于输入数据(例如,它通过幸运机会在此产生正确的结果)。
设想一串数字,以0
结尾,然后是12 9
s。 在计算最大值时,代码将错误地考虑9^12
。 更简单的是,对于1000个零点,它将产生1个作为答案。
由于压缩的特性,我们可以实现自动截断:
import Data.Char
import Data.List
euler_8 = do
str <- readFile "numbers.txt"
print . maximum . map product
. foldr (zipWith (:)) (repeat []) -- here
. take 13 . tails . map (fromIntegral . digitToInt)
. concat . lines $ str
你的代码虽然是正确的,但有一些问题:
[x | x <- xs]
[x | x <- xs]
就是xs
last (sort xs)
只是maximum xs
,这更快 toDigits n xs -- to be called as `toDigits n []`
| n < 1 = xs
| otherwise = toDigits (n `div` 10) ((n `mod` 10) : xs)
链接地址: http://www.djcxy.com/p/80429.html
上一篇: Project Euler 8
下一篇: Project Euler 4