找到最大的 n，这样 n！< k在哈斯克尔，使用折叠和无穷级数

Question

这在标题中陈述似乎很简单，但我很难编码。 我正在寻找最大的 n 这样的 n！

这是我尝试过的：

func1 = foldl (*) 1 [1..] . takeWhile (x -> x < (read "1e100" :: Scientific ))
func2 = (x -> foldl (*) 1 [1..x] . takeWhile (x < (read "1e100" :: Scientific )))
func3 = do
forM_ [1..] $ x -> do
let y = foldl (*) 1 [1..x]
when y >= (read "1e100" :: Scientific ) $
putStrLn x
return ()
func4 k = let nfac = foldl (*) 1 [1..n]
where nfac > k
-- func4 (read "1e100" :: Scientific )

我正在使用 Data.Scientific 库，因为 k 通常很大。

正确表达这一点的惯用语是什么？

Answer 1

简短的回答：将程序划分为函数，每个函数执行专用任务。

我们可以先定义一个函数来计算阶乘：

fact :: (Num a, Enum a) => a -> a
fact x = foldl (*) 1 [1..x]

现在我们可以生成一个 2 元组的列表，其中第一项是i，第二项是i!：

facts :: (Num a, Enum a) => [(a, a)]
facts = map (i -> (i, fact i)) [1..]

现在我们可以使用takeWhile来过滤此列表，以仅返回第二项(因此i!(小于n的元组：

factsless :: (Num a, Enum a) => a -> [(a, a)]
factsless n = takeWhile ((_, fi) -> fi < n) facts

现在我们可以用last来获取这个列表的最后一个元组，然后用fst来获取对应的i：

solution :: (Num a, Enum a) => a -> a
solution n = fst (last (factsless n))

鉴于n很大，只有Integer才能表示该数字。因此，使用Integer进行a可能更安全，因为否则小于检查可能永远不会失败，因此会发生溢出。

例如：

Prelude> solution 2
1
Prelude> solution 3
2
Prelude> solution 4
2
Prelude> solution 5
2
Prelude> solution 6
2
Prelude> solution 7
3
Prelude> solution 10
3
Prelude> solution 100
4
Prelude> solution 10000
7 
Prelude> solution (10^100)
69 

由于阶乘是积分，最好避免使用浮点数，通常整数会更精确、紧凑和高效。

优化：

我们可以通过生成无限列表来提高计算阶乘的性能，例如使用scanl：

facts :: (Num a, Enum a, Num b, Enum b) => [(a, b)]
facts = zip [1..] (scanl (*) 1 [2..])

其他优化是可能的，但我将其作为练习。

Answer 2

用扫描替换折叠，并将其结果通过takeWhile ...。然后索引它并采取last！

但首先解开read，把它变成一个普通的参数值。对于您正在实现的算法，它来自哪里并不重要。因此

factProblem :: Integer -> Int
factProblem k = -- fst . last . zip [0..] 
pred . length
. takeWhile (< k) . scanl (*) 1 $ [1..]
main :: IO ()
main = getLine >>= print . factProblem . read