实验吧CTF — 大数据问题+手脑并用

首先看这两个题目:

大数据问题  手脑并用

这两个题目差不多,这就一起分析了

CTF的编程题比ACM的题目要简单很多,主要还是分析和编程

首先看手脑并用这个题目,求6789!的零的个数,因为6789相对来说是个比较小的数,可以直接计算并统计0的个数

(1)直接计算6789!

import math

a = 6789
print math.factorial(a)

得到的结果复制到notepad++中,可以看到0的个数

1

(2)分析下可以知道,n!零的个数由结果的因式分解中2和5的个数确定,2*5=10得到一个0,而因式分解中5的个数显然是少于2的,所以只需要统计有多少个因子5就ok了。

先来分析下阶乘的0个数规律

使用阶乘程序,计算

10! = 3628800

20! = 2432902008176640000

25! = 15511210043330985984000000

对结果进行分析得到:

10/5 = 2     2个0

20/5 = 4     4个0

25/5 = 5&5/5=1     5+1=6个0

所以程序应该是这样的:

import math

a = 6789
sum = 0

while a:
    sum += a/5
    a /= 5
print sum

运行得到结果

(3)然后看阶乘和的0的个数题目大数据问题

首先分析,要求阶乘和的末5位,根据之前的分析,当阶乘达到一个数后,后5位全都是0,对结果没有任何影响,而且知道25!结尾有6个零

所以只需要计算1-24阶乘的和的末5位就ok了

import math

a = 25
sum = 0

for i in range(1, a):
    j = math.factorial(i)
    sum += j

print str(sum)[-5:]

运行得到结果

(4)总结,这两道题目相对比较简单,没有涉及复杂的算法,编程前先分析可以有效减轻编程的复杂度,找出规律后再编写程序就简单多了。

 

您可能还喜欢...