在给定数量的阶乘尾随零的数目 - 红宝石 [英] the number of trailing zeros in a factorial of a given number - Ruby

问题描述

有一个小麻烦试图计算给定数的阶乘尾随零的数目。这是从codewars-不能得到我传递的挑战之一。

 零（12）= 2＃=＆GT; 1 * 2 * 3 .. 12 = 479001600
 

我觉得我在错误的道路上我在这里有可能是一个更优雅的红宝石的方式。这是我下来为止。

 高清零（N）
    X =（1 ... N）。降低（*）to_s.scan（/ [^ 0] /）。
    返回0，如果x == []
    返回X [-1] .length如果x！= []
结束
 

解决方案

这更多的是一个数学问题。而你是对的，你是关在一个错误的道路。 （我的意思是你在路径将会导致非常低效的解决方案）

尽量减少问题的数学第一。 （顺便说一句，你拍摄的日志N阶算法。）

在我的答案我会尝试跳过了几步，因为它似乎是一个家庭作业的问题。

尾随零的数目将是等于5秒的系列中的乘法的总功率。

1和n将 N / 5 ， N / 25 ， N / 125 这是5秒的倍数，25岁以下，分别为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比的权力，更多的权力5

例如。

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

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

因此​​，我们需要做的是在阶乘数的5力量。

4

现在可以专注于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所有的倍数，都加了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

现在你能EX preSS，作为一个循环？

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.

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.

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

解决方案

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.)

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.

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.

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.

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

e.g.

• 40 = 4 * 10^1 and it has 1 trailing zero
• 12 = 3 * 4 * 10^0 so it has 0 trailing zeros
• 1500 = 3 * 5 * 10^2 so it has 2 trailing zeros

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

e.g.

• 50 = 2^1 * 5^2 so the minimum power is 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)

3.

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

e.g.

• 5! = 2^3 * 3^1 * 5^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.

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

4.

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

• 4! ~ 5^0
• 5! ~ 5^1 (up to 9!)
• 10! ~ 5^2 (up to 14!)
• 15! ~ 5^3 (up to `19!)
• 20! ~ 5^4 (up to 24!)
• 25! ~ 5^6 (notice the jump from 5^4 to 5^6 because the number 25 adds two powers of 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.

6.

So how'd you put that as an algorithm ?

lets say the number is n. So...

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

and so on...

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

7.

Now can you express that as a loop?

这篇关于在给定数量的阶乘尾随零的数目 - 红宝石的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！