在给定数字的阶乘中的尾随零的数量 – Ruby

尝试计算给定数量的阶乘中的尾随零的数量时遇到一些麻烦。 这是Codewars面临的挑战之一 – 无法通过。

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

我想我在这里走错路，可能有一种更优雅的ruby方式。 这就是我到目前为止所做的事情。

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

Answer 1

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

首先尝试以数学方式减少问题。 （顺便说一句，你正在拍摄日志N阶算法。）

在我的回答中，我将尝试跳过几个步骤，因为它似乎是一个功课问题。

尾随零的数量将等于系列乘法中5s的总功率。

1和n之间的数字将具有n/5 ， n/25 ， n/125数字，它们分别是5s，25s，125s的倍数……等等。

尝试采用这些提示并提出一种算法来计算将10幂数塞进该因子中。

掠夺者前方

我已经决定在下面详细解释，所以如果你想尝试自己解决它然后停止阅读，试着想一想，然后回到这里。

这是逐步减少问题的方法

1。

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

例如

• 40 = 4 * 10^1 ，它有1个尾随零
• 12 = 3 * 4 * 10^0所以它有0个尾随零
• 1500 = 3 * 5 * 10^2所以它有2个尾随零

2。

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

例如

• 50 = 2^1 * 5^2所以最小功率为1
• 300 = 3^1 * 2^2 * 5^2因此最小值为2（我们只关注2和5的幂的最小值，因此忽略3的幂和所有其他素因子）

3。

在任何阶乘中，将有比2的幂更多的2的幂

例如

• 5! = 2^3 * 3^1 * 5^1
• 10! = 2^8 * 3^4 * 5^2 * 7^1

正如你所看到的，2的功率将开始增加得更快，因此5的功率将是两者的最小值。

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

4。

现在让我们专注于任何n!的5的力量n!

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

5。

我想计算一个阶乘的五个总功率的方式是……计算所有5的倍数，它们都加上5的幂。然后计算所有25的倍数，它们都增加了额外的功率5.注意25加了两个5的幂，所以我可以把它作为一个幂，因为它是5的倍数和一个额外的功率，因为​​它是25的倍数。然后计算125（ 5^3 ）的所有倍数阶乘乘法，它们增加了另外5的额外功率……依此类推。

6。

那你怎么把它作为算法呢？

我想说数字是n 。 所以…

• pow1 = n/5 （向下舍入为整数）
• pow2 = n/25
• pow3 = n/125

等等…

现在总功率pow = pow1 + pow2 + pow3 ...

7。

现在你可以把它表达为循环吗？

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 。

然后，可以被5^1=>5整除的1到128 （包括）之间的每个数字提供至少一个因子，并且存在128/5 => 25这样的数字。 其中，唯一提供多个因子的是可被5^2=>25整除的那些，其中有128/25 => 5 （ 25, 50, 75, 100, 125 ）。 其中，只有128/125 => 1提供了两个以上的因子，并且由于125/(5^4) => 0 ，没有数字贡献超过三个除数。 因此，五个除数的总数是：

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

（注意，对于具有3个除数的125 ，在这三个项中的每一个中计数一个;对于25等，其中每个具有5两个因子，在每个第一项中计数一个。 ）

对于任意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 } 

因此，因子总数为5

 (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

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

Answer 4

如果N是一个数字，那么N中的尾随零数！ 是

N/5 + N/5^2 + N/5^3 ..... N/5^(m-1) WHERE (N/5^m)<1

你可以在这里学习这个公式是如何来的。

Answer 5

这是一个更容易阅读的解决方案：

 def zeros(num) char_array = num.to_s.split('') count = 0 while char_array.pop == "0" count += 1 end count end 

如果您看到改进，请告诉我您的想法并随时编辑！

Answer 6

关于因子及其在GanitCharcha中的尾随零的文章是有见地的，并且已经解释了这个背后的数学。 看一看。

http://www.ganitcharcha.com/view-article-A-Note-on-Factorial-and-it's-Trailing-Zeros.html

Answer 7

我的解决方案

 def zeros(n) trailing_zeros = [] fact = (1..n).inject(:*) fact.to_s.split('').reverse.select {|x| break if (x.to_i != 0); trailing_zeros << x} return trailing_zeros.count end 

Answer 8

 n = int (raw_input()) count = 0 num = 1 for i in xrange(n+1): if i != 0: num = num * i while(num >= 10): if num%10 == 0: count+=1 num = num/10 else: break print count 

Answer 9

根据@spundan给出的解释，除了@ cary的代码，你可以通过非常简单有效的方式找到尾随零的数量。见下面的代码..

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

例如零（100000000），这将为您提供输出 – > 24999999
随着时间流逝 – > 5.0453e-05 （见5.0453e-05 ）
这是偶数毫秒的一部分。

Answer 10

  n=int(input()) j=5 c=int(0) while int(n/j)>0: c=c+int(n/j) j=j*5 print(c) 

Answer 11

 count = 0 i =5 n = 100 k = n while(n/i!=0): count+=(n/i) i=i*5 n = k print count