1

我一直在尝试解决一个需要 Sigma 表示法（或者至少我认为）的问题，但是我遇到的 Haskell 中 Sigma 表示法的每个实现都没有在其函数中使用索引变量。我一直试图复制的特定公式是：

在此处输入图像描述

它用于计算 n! 中尾随零的数量，但我得到的最好的是：

 sigma :: (Enum a, Num b) => a -> a -> (a -> b) -> b
 sigma i k fn = sum . map fn $ [i..k]

 zeros :: Int -> Int
 zeros n = sigma 1 n (???)

我也在尝试创建一个通用的 sigma 函数，它与 f 中的索引变量一起使用。这有效，但对于 100！，它会给出 -11 个尾随零。溢出？

zeros :: Int -> Int
zeros n = sigma 1 n (\i -> n `div` 5 ^ i)
        where sigma i k fn = sum $ map fn [i..k]

PS 我在限制编译时间的浏览器内 IDE 上。（所以速度很重要）

4

2 回答 2

2

你的麻烦只是来自类型不匹配。您想truncate在最后执行并使用小数运算进行除法、求幂和求和，然后在最后截断结果。因此，您需要的不仅仅是zeros n = sigma 1 n something：

zeros :: Integral a => a -> a
zeros n = truncate $ sigma 1 n (\i -> fromIntegral n / 5 ^ i)

您需要担心的细节是fromIntegral n，它n从 an转换Integral a => a为 a Num b => b，^运算符允许Integral a => a参数作为指数，因此我们不需要在那里转换，然后truncate将转换回 a Integral。我们可以使这个签名更加通用，并返回Integral我们输入的不同，但这在实践中并不是很有用。

所以现在我们可以输入Int或Integer，这取决于你需要输入多大的数字到这个函数（因为你提到过100!），但要注意，制作100!元素列表会严重消耗 RAM 和 CPU 时间。

如果您真的想计算大数的尾随零，将其转换为字符串可能会容易得多，如下所示：

zeros :: (Show a, Integral a) => a -> Int
zeros = length . takeWhile (== '0') . reverse . show
于 2014-10-13T14:17:14.733 回答
1 
sigma i k fn = sum $ map fn [i..k]
zeros n = sigma 1 n (\i -> fromIntegral n / 5**(fromIntegral i))

Haskell 不会自动在整数和浮点数之间进行转换。这就是为什么你需要fromIntegral.

于 2014-10-13T13:57:04.303 回答