阶乘尾随零
涉及阶乘计算的功能为设计巧妙的省时算法提供了充足的机会。 以盖尔·拉克曼·麦克道威尔(Gayle Laakmann McDowell)的CTCI提出的问题为例: 编写一个函数,该函数返回给定阶乘的尾随零数。 蛮力尝试将是计算阶乘,然后使用模10计算尾随零: 在完成这项工作的同时,如果我们停止考虑哪些整数有助于在阶乘或乘法方程中添加尾随零,则可以进行优化。 乘以10会在末尾加一个零,乘以两个乘积即为10的数字也是如此。 因此,我们可以推断出,如果仅对2和5的倍数进行累加,就可以忽略阶乘运算和零计数。会有更多的2的倍数,因此我们可以集中精力对5进行计数。 第一个边缘情况出现在25,因为它给我们两个5(5 x 5)。 因此,我们无需将数字乘以5,而是可以将5乘以每个数字的次数添加到计数器中。 还有一项其他优化。 你能说出它是什么吗?