在给定数字的阶乘中的尾随零的数量 - 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

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

首先尝试以数学方式减少问题.(顺便说一句,你正在拍摄日志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.

现在让我们专注于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的倍数.然后计算5^3因子乘法中125()的所有倍数,他们又增加了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.

然后128,可被整除的一个和(包括)之间的每个数字5^1=>5提供至少一个因子,并且存在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

(注意,对于125,其中有三个约数5,一个是在这三个术语的计数;用于25,50等,其各自具有两个因素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)

然后我进行了一些重新排列,以便只使用整数运算来计算结果.