在给定数字Ruby的阶乘中尾随的0的数目

Having a little trouble trying calculate the number of trailing zeros in a factorial of a given number. This is one of the challenges from Codewars- can't get mine to pass.

在计算一个给定数字的阶乘的末尾0的数量时遇到了一点麻烦。这是Codewars的挑战之一，我无法通过。

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

I think I'm on the wrong path here and there is probably a more elegant ruby way. This is what I have down so far.

我认为我走错了路，这里可能有一种更优雅的ruby方式。这是我目前所做的。

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

11 个解决方案

#1

This is more of a math question. And you're right, you are off on a wrong path. (I mean the path you are on is going to lead to a very inefficient solution)

这是个数学问题。你是对的，你走错了路。(我的意思是你所走的道路将导致一个非常低效的解决方案)

Try to reduce the problem mathematically first. (BTW you are shooting for a log N order algorithm.)

试着先从数学上减少问题。(顺便说一句，这是一个log N阶的算法。)

In my answer I will try to skip a few steps, because it seems like a homework question.

在我的回答中，我会尝试跳过一些步骤，因为这看起来像是一个家庭作业问题。

The number of trailing zeros is going to be equal to the total power of 5s in the multiplication of the series.

后面的0的个数等于5s在级数乘法中的总幂。

the numbers between 1 and n will have n/5, n/25, n/125 numbers which are multiples of 5s, 25s, 125s respectively... and so on.

1和n之间的数是n/5, n/25, n/125，分别是5s、25s和125s的倍数……等等。

Try to take these hints and come up with an algorithm to count how many powers of 10 will be crammed in to that factorial.

试着利用这些提示并想出一个算法来计算10的多少次幂会被填入那个阶乘中。

Spoilers Ahead

I've decided to explain in detail below so if you want to try and solve it yourself then stop reading, try to think about it and then come back here.

我决定在下面详细解释一下，如果你想自己解决它，那就不要读了，试着思考一下，然后再回来。

Here is a step by step reduction of the problem

这是一个逐步减少的问题

1.

The number of trailing zeros in a number is equivalent to the power of 10 in the factor of that number

一个数字后面的0的数量等于这个数字的因数的10次方

e.g.

如。

• 40 = 4 * 10^1 and it has 1 trailing zero
• 40 = 4 * 10 ^ 1和1后补零
• 12 = 3 * 4 * 10^0 so it has 0 trailing zeros
• 12 = 3 * 4 * 10 ^ 0 0 0
• 1500 = 3 * 5 * 10^2 so it has 2 trailing zeros
• 1500 = 3 * 5 * 10 ^ 2所以它有2 0

2.

The number power of 10 in the factors is the same as the minimum of the power of 2 and power of 5 in the factors

因子中的10次幂等于因子中2次幂和5次幂的最小值

e.g.

如。

• 50 = 2^1 * 5^2 so the minimum power is 1
• 50 = 2 ^ 1 * 5 ^ 2的最小功率,是1
• 300 = 3^1 * 2^2 * 5^2 so the minimum is 2 (we are only concerned with the minimum of the powers of 2 and 5, so ignore powers of 3 and all other prime factors)
• 300 = 3 ^ 1 * 2 ^ 2 * 5 ^ 2最低是2(我们只关心最低2和5的权力,所以忽略权力3和所有其他主要因素)

3.

In any factorial there will be many more powers of 2 than the powers of 5

在任何阶乘中2的幂要比5的幂大得多

e.g.

如。

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

As you can see the power of 2 is going to start increasing much faster so the power of 5 will be the minimum of the two.

你可以看到2的幂会以更快的速度增长所以5的幂是2的最小值。

Hence all we need to do is count the power of 5 in the factorial.

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

4.

Now lets focus on the power of 5 in any n!

现在我们关注任意n中5的幂!

• 4! ~ 5^0
• 4 !~ 5 ^ 0
• 5! ~ 5^1 (up to 9!)
• 5 !~ 5 ^ 1(9)
• 10! ~ 5^2 (up to 14!)
• 10 !~ 5 ^ 2(14)
• 15! ~ 5^3 (up to `19!)
• 15 !~ 5 ^ 3(19)
• 20! ~ 5^4 (up to 24!)
• 20 !~ 5 ^ 4(24)
• 25! ~ 5^6 (notice the jump from 5^4 to 5^6 because the number 25 adds two powers of 5)
• 25 !~ 5 ^ 6(注意从5 5 ^ 6 ^ 4,因为25号添加两个大国的5)

5.

The way I'd like to count the total power of five in a factorial is... count all the multiples of 5, they all add one power of 5. Then count all the multiples of 25, they all add an extra power of 5. Notice how 25 added two powers of 5, so I can put that as, one power because it's a multiple of 5 and one extra power because it's a multiple of 25. Then count all the multiple of 125 (5^3) in the factorial multiplication, they add another extra power of 5... and so on.

我计算5的阶乘的总幂的方法是。数所有5的倍数，它们都加一个5的幂。然后数所有25的倍数，它们都加5的幂。注意25加2的5次方，我可以把它写成，1次方因为它是5的倍数而1次方因为它是25的倍数。然后计算所有125多个(5 ^ 3)的阶乘乘法,他们添加另一个额外的5…等等。

6.

So how'd you put that as an algorithm ?

那你怎么把它作为一个算法呢?

lets say the number is n. So...

假设数字是n。

• pow1 = n/5 (rounded down to an integer)
• pow1 = n/5(取整)
• pow2 = n/25
• pow2 = n / 25
• pow3 = n/125
• pow3 = n / 125

and so on...

等等……

Now the total power pow = pow1 + pow2 + pow3 ...

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

7.

Now can you express that as a loop?

现在你能把它表示成一个循环吗?

#2

So, now that @Spunden has so artfully let the cat out of the bag, here's one way to implement it.

所以，现在@Spunden已经非常巧妙地泄露了秘密，这是实现它的一种方法。

Code

代码

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

Examples

例子

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

Explanation

解释

Suppose n = 128.

假设n = 128。

Then each number between one and 128 (inclusive) that is divisible by 5^1=>5 provides at least one factor, and there are 128/5 => 25 such numbers. Of these, the only ones that provide more than one factor are those divisible by 5^2=>25, of which there are 128/25 => 5 (25, 50, 75, 100, 125). Of those, there is but 128/125 => 1 that provides more than two factors, and since 125/(5^4) => 0, no numbers contribute more than three divisors. Hence, the total number of five divisors is:

那么每个数字一至128(包容)5 ^ 1 = > 5整除提供至少一个因素,还有128/5 = > 25这些数字。其中,唯一提供超过一个因素是那些能被5整除^ 2 = > 25,其中有128/25 = > 5(25、50、75、75、100)。其中,只有128/125 = > 1,提供两个以上的因素,自125年以来,/(5 ^ 4)= > 0,没有数字贡献超过三个因子。因此，5个因数的总数为:

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

(Note that, for 125, which has three divisors of 5, one is counted in each of these three terms; for 25, 50, etc., which each have two factors of 5, one is counted in each of the first terms.)

(注意，对于125，它有3个5的因数，在这3项中每一项都是1;对于25,50，等等，每一项都有两个因子5，每一项都有一个

For arbitrary n, we first compute the highest power k for which:

对于任意n，我们首先计算最高功率k，它是:

5**k <= n

which is:

这是:

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

so the largest such value is:

所以最大的值是:

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

As @spundun noted, you could also calculate k by simply iterating, e.g.,

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

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

The total number of factors of five is therefore

因此，5个因子的总数是

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

Defining:

定义:

r = 1/5,

this sum is seen to be:

这个数目可以看出是:

n * s

where

在哪里

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

The value of s is the sum of the terms of a geometric series. I forget the formula for that, but recall how it's derived:

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)

I then did some rearrangement so that only only integer arithmetic would be used to calculate the result.

然后我做了一些重新排列，以便只使用整数算法来计算结果。

#3

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

#4

Here's a solution that is easier to read:

这里有一个更容易阅读的解决方案:

def zeros(num)
  char_array = num.to_s.split('')
  count = 0

  while char_array.pop == "0"
    count += 1
  end

  count
end

Let me know what you think and feel free to edit if you see an improvement!

让我知道你的想法，如果你看到改进，请随时编辑!

#5

The article A Note on Factorial and its Trailing Zeros in GanitCharcha is insightful and has explained the Mathematics behind this well. Take a look.

这篇文章在GanitCharcha的阶乘和后面的零是有深刻见解的，并解释了这方面的数学。看一看。

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

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

#6

My solution

我的解决方案

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

#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

#8

As per the explanation given by @spundan and apart from @cary's code you can find number of trailing zero by just very simple and efficient way..see below code..

根据@spundan给出的解释，除了@cary的代码之外，您可以通过非常简单有效的方式找到末尾为0的数字。参见下面的代码. .

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

For example zeros(100000000) this will give you output -> 24999999
With the time Time Elapsed -> 5.0453e-05(Just See 5.0453e-05 )
This is the part of even milliseconds.

例如，0(100000000)这将给你输出-> 24999999与时间间隔-> 5.0453e-05(只看到5.0453e-05)这是毫秒的一部分。

#9

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

#10

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

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

#11

If N is a number then number of trailing zeroes in N! is

如果N是一个数字，那么N后面的0的个数!是

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

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

You can learn here how this formula comes.

你可以在这里学到这个公式是怎么来的。