给定一个数的阶乘末尾零的个数 - Ruby

Question

我在尝试计算给定数字的阶乘中末尾零的数量时遇到了一些困难。这是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

- user3563086

---

你有什么问题？ - sawa

@sawa 求末尾零的个数.. OP需要.. - Arup Rakshit

这是一个可行的解决方案 :) http://stackoverflow.com/a/23762680/125816 - Sergio Tulentsev

@SergioTulentsev 您的解决方案以及OP的解决方案与阶乘无关。它只是计算任意数字的尾随零。 - sawa

@sawa：我们都知道很少有用户会提出好的、范围明确的问题。因此，我们可以做出一些假设。 - Sergio Tulentsev

Answer 1

这更多是一个数学问题。你说得对，你所走的方向是错误的。（我的意思是说，你所走的路线将导致非常低效的解决方案）

首先尝试数学上减少问题。（顺便说一句，你需要考虑寻找O(log N)阶算法）

在我的回答中，我会跳过一些步骤，因为这似乎是一个作业问题。

末尾零的数量将等于系列乘法中5的总幂。

1到n之间的数字将具有n/5、n/25、n/125个是5的倍数、25倍数、125倍数...以此类推。

尝试使用这些提示并想出一个算法来计算阶乘中将塞入多少个10的幂次。

以下内容包含剧透

我决定在下面详细说明，如果你想自己尝试解决它，请停止阅读，思考一下，然后再回到这里。

这是问题的逐步简化过程：

1.

一个数字的末尾零的数量等于该数字因子中10的幂。

例如：

• 40 = 4 × 10^1，它有1个末尾零
• 12 = 3 × 4 × 10^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的幂次要比5的幂次多得多

例如

• 5！= 2³ * 3¹ * 5¹
• 10！= 2⁸ * 3⁴ * 5² * 7¹

如您所见，2的幂次将更快地增加，因此5的幂次将是两者中的最小值。

因此，我们只需要计算阶乘中5的幂次。

4.

现在让我们专注于任何n!中5的幂次

• 4！~ 5⁰
• 5！~ 5¹（高达9！）
• 10！~ 5²（高达14！）
• 15！~ 5³（高达`19！)
• 20！~ 5⁴（高达24！）
• 25！~ 5⁶（注意从5⁴到5⁶的跳跃，因为数字25增加了两个5的幂次）

5.

我想要计算阶乘中5的总次数的方法是...先计算所有5的倍数，它们都会增加一个5的幂。然后再计算所有25的倍数，它们都会增加一个额外的5的幂。注意，25增加了两个5的幂，所以我可以这么写：一个是因为它是5的倍数而增加的一个5的幂，另一个是因为它是25的倍数而增加的额外一个5的幂。然后计算阶乘中所有125（5^3）的倍数，它们会再增加一个额外的5的幂......以此类推。

6.

那么如何将其作为算法呢？假设数字为n。那么...
• pow1 = n/5 （向下取整为整数）
• pow2 = n/25
• pow3 = n/125
等等...

现在总的幂为pow = pow1 + pow2 + pow3 ... 7.

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

- Spundun

---

也许我的数学很生疏，但我不知道你想表达什么 :/ - Sergio Tulentsev

@SergioTulentsev 我想我会解释整个事情。 - Spundun

@SergioTulentsev 这有帮助吗？ - Spundun

我现在还能记得我的八年级数学课.. 我们的老师经常用这种方式来解释事情.. 做得好。 - Arup Rakshit

@ Spundun 你还记得...但对我来说，它已经售罄了.. :-) 希望你明白我的意思。 - Arup Rakshit

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。

那么在介于一和 128（包括边界）之间，任何一个可以被 5^1=>5 整除的数都提供至少一个因子，这样的数字有 128/5 => 25 个。其中，唯一能提供多于一个因子的是那些可以被 5^2=>25 整除的数，它们共有 128/25 => 5 个（分别为 25, 50, 75, 100, 125）。其中只有一个数能提供超过两个因子，而由于 125/(5^4) => 0，没有任何数字能提供超过三个因子。因此，五个因子的总数为：

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

where

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)

我随后进行了一些调整，以便仅使用整数算术来计算结果。

- Cary Swoveland

---

不错的优化。你可能需要注意 n=0 的情况。我曾经认为你的方法比简单循环每次乘以5要慢，但是Ruby基准测试让我不再这么认为了。我认为无论哪种方式，函数都非常非常快，具有 log(n) 的顺序（在你的代码中，log(n) 的时间来自于必须计算 log(n) 本身）。此外，在理论上，由于舍入误差，有可能会得到错误的比率整数，但我认为这种概率可能是微不足道的。我想在C中对两种方法进行基准测试，但现在太懒了。 - Spundun

此外，我也不确定最快的对数函数实现在哪里。 - Spundun

感谢您的纠正，@Spundun。我最初写成了return 0 if n < 5，但后来认为这不是必要的，忘记了n等于零的情况。我认为四舍五入不是问题。它可能发生的唯一地方是在log计算中，但这可以很容易地处理。随后的计算始终是整数值。 - Cary Swoveland

Answer 3

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

- Carlos G

---

这个页面上还有其他两篇帖子使用了这种方法，您在添加新内容吗？ - Teepeemm

我不会添加任何东西，只是在其他答案中看到的最短的代码。 - Carlos G

Answer 4

如果N是一个数字，则N!中末尾零的数量为

N/5 + N/5^2 + N/5^3 ..... N/5^(m-1)，其中(N/5^m)<1。

您可以在此处了解该公式的推导here。

- Noor A Shuvo

Answer 5

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

- Subham Kapoor

---

这个代码对于30!有效吗？http://www.tsm-resources.com/alists/fact.html将30!表示为265252859812191058636308480000000（7个尾随零）。而这里的代码返回6。 - Jack

我认为应该是 while int(n/j) > 0。 - Jack

写成了1而不是0。 - Subham Kapoor

能否请您在回答中添加更多的上下文信息。仅有代码的答案很难理解。如果您能在帖子中添加更多信息，将有助于提问者和未来的读者。 - RBT

Answer 6

我的解决方案

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

- Prem Anand

---

实际上，找到阶乘是解决问题的一种非常低效的方法。 - Teepeemm

Answer 7

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

- sneha vj

---

这与现有的答案不同吗？它是最简单的吗？ - greybeard

实际上，找到阶乘是解决问题的一种非常低效的方法。 - Teepeemm

Answer 8

count = 0
i  =5
n = 100
k = n

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

- Sourabh Dattawad

---

请不要只写出代码回答。请解释你的解决方案是做什么的! - Noel Widmer

Answer 9

根据@spundan的解释以及除@cary的代码之外，您可以通过以下非常简单和高效的方式找到末尾零的数量...请参见下面的代码。

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

例如zeros(100000000)，这将给出输出 -> 24999999
时间Time Elapsed -> 5.0453e-05(只需看5.0453e-05)
这是甚至毫秒的一部分。

- Jay_Pandya

---

如果其他两个答案已经提供了必要的代码，那么你的回答对这个页面有什么补充呢？ - Teepeemm

Answer 10

文章《关于GanitCharcha中的阶乘及其尾随零的注释》深入浅出地解释了这个问题背后的数学原理，值得一读。

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

- debapriyay

---

最好将材料放在这里，而不是放在链接后面。链接是否添加了此处没有的任何信息？ - Teepeemm