给定数的阶乘中尾随零的数量-Ruby

Question

尝试计算给定数字的阶乘中尾随零的数量有点困难。这是Codewars-无法让我的通过的挑战之一。

zeros(12) = 2       #=> 1 * 2 * 3 .. 12 = 479001600 

我想我在这里走错了路，可能还有更优雅的红宝石路。这是我迄今为止所做的。

def zeros(n) 
    x = (1..n).reduce(:*).to_s.scan(/[^0]/)
    return 0 if x == [] 
    return x[-1].length if x != [] 
end

Answer 1

def zeros(n)
    zeros = 0
    zeros += n /= 5 while n >= 1
    zeros
end

Answer 2

所以，既然@Spunden如此巧妙地泄露了秘密，这里有一种实现它的方法。

密码

def zeros(n)
  return 0 if n.zero?
  k = (Math.log(n)/Math.log(5)).to_i
  m = 5**k
  n*(m-1)/(4*m)
end

示例

zeros(3)   #=>  0
zeros(5)   #=>  1
zeros(12)  #=>  2
zeros(15)  #=>  3
zeros(20)  #=>  4
zeros(25)  #=>  6
zeros(70)  #=> 16
zeros(75)  #=> 18
zeros(120) #=> 28
zeros(125) #=> 31

解释

假设n=128。

然后，1和128之间的每个数字（包括）可以被5^1整除=

128/5 + 128/25 + 128/125 #=> 31

（注意，对于具有三个因子（5）的125，在这三项中各计算一个；对于具有两个因子（5）的25、50等，在第一项中各计算一个。）

对于任意n，我们首先计算最高功率k，其中：

5**k <= n

即：

k <= Math.log(n)/Math.log(5)

因此，最大值为：

k = (Math.log(n)/Math.log(5)).to_i

正如@spundun所指出的，您也可以通过简单的迭代来计算k，例如。，

last = 1
(0..1.0/0).find { |i| (last *= 5) > n }

因此，五个因子的总数为

(n/5) + (n/25) +...+ (n/5**k)

定义：

r = 1/5,

这笔款项被视为：

n * s

哪里

s = r + r**2 +...+ r**k

s的值是几何级数项的总和。我忘记了这个公式，但回想一下它是如何推导出来的：

s  = r + r**2 +...+ r**k
sr =     r**2 +...+ r**(k+1)

s-sr = r*(1-r**k)

s = r*(1-r**k)/(1-r)

然后我做了一些重新安排，这样只会使用整数算术来计算结果。

Answer 3

这更像是一个数学问题。你是对的，你走错了路。（我是说你走的路会导致一个非常低效的解决方案）

首先尝试从数学上减少问题。（顺便说一句，你正在尝试对数N阶算法。）

在我的回答中，我将尝试跳过几个步骤，因为这似乎是一个家庭作业问题。

尾随零的数量将等于序列乘法中5s的总幂。

1和n之间的数字将分别为5s、25s和125s的倍数。。。等等

试着接受这些提示，并想出一个算法来计算该阶乘中会塞进多少次幂。

我决定在下面详细解释一下，如果你想自己解决这个问题，那就别读了，试着想想，然后回到这里。

下面是问题的逐步简化

一个数字中尾随零的数量相当于该数字因子中10的幂

例如

• 40=4*10^1，并且它有一个尾随零

因子中10的数字幂与因子中2的幂和5的幂的最小值相同

例如

• 因此，最小功率为1

在任何阶乘中，2的幂将比5的幂多得多

例如

• <代码>5！=2^3*3^1*5^1
• <代码>10！=2^8*3^4*5^2*7^1

正如你所见，2的幂开始增加得更快，所以5的幂将是这两个中的最小值。

因此，我们需要做的就是在阶乘中计算5的幂。

现在让我们关注5在任意<代码>n中的幂

• <代码>4！~5^0
• <代码>5！~5^1（最多9个）
• <代码>10！~5^2（最多14个）
• <代码>15！~5^3（最多19！）
• <代码>20！~5^4（最多24个）
• <代码>25！~5^6（注意从5^4跳到5^6，因为数字25加了两个5的幂）

我想计算阶乘中五的总幂的方法是。。。计算所有5的倍数，它们都加上5的一次幂。然后计算所有25的倍数，它们都会增加5的额外幂。注意25加了两个5的幂，所以我可以把它写成，一个幂是5的倍数，一个额外的幂是25的倍数。然后计算阶乘中125（5^3）的所有倍数，再加上另一个5的幂。。。等等

那么你是如何把它作为一种算法的呢？

假设数字是n。因此...

• pow1=n/5（四舍五入为整数）

等等

现在总功率pow=Pow1 POW2 POW3...

现在你能把它表达成一个循环吗？