python小练习（006）：探讨正整数长列表的乘积

jerryxjr1220

昨天python小练习的题目：传送门

今天的题目也不难，探讨一下一个长度非常长的正整数列表的乘积情况（不能直接相乘，不然结果会溢出）

1. 给你一个正整数长列表 L, 如 L=[1，3，5，7，9，...，10**7-1], 输出L内所有数字的乘积的长度（乘积是几位数）

2. 给你一个正整数长列表 L, 如 L=[2，4，6，8，10，...，10**7], 输出L内所有数字的乘积末尾0的个数

3. 给你一个正整数长列表 L, 如 L=[1，2，3，4，5，...，10**7], 判断列表内所有数字乘积的最后一个非零数字的奇偶，如果是奇数输出1，偶数输出0

SixPy

这其实是阶乘！

jerryxjr1220

看大家都算出来了，就贴下我的算法：
第一题：

1. import math
   
2. L1, L2, L3 = 1, 2, 1
   
3. ls1 = math.log10(1)
   
4. while L1<10**7:
   
5.         ls1 += math.log10(L1)
   
6.         L1 += 2
   
7. print int(ls1+1)
   
8. #32828528

复制代码

第二题：

1. L2 = 2
   
2. s2, c2 = 1, 0
   
3. while L2<10**7+1:
   
4.         s2 *= L2
   
5.         while s2%10==0:
   
6.                 s2 = s2//10
   
7.                 c2 += 1
   
8.         s2 = s2%10000 #s2可以保留更多位，但是对于最终结果没有影响。为了加快运算速度取4位即可。
   
9.         L2 += 2
   
10. print c2
    
11. #1249998

复制代码

第三题：

1. L3 = 1
   
2. s3 = 1
   
3. while L3<10**7+1:
   
4.         s3 *= L3
   
5.         while s3%10==0:
   
6.                 s3 = s3//10
   
7.         s3 = s3%10
   
8.         L3 += 1
   
9. print 1 if s3%2 else 0
   
10. #0

复制代码

把上限减小了些，方便计算
关键还是看方法

jerryxjr1220

SixPy 发表于 2016-11-16 09:54
这其实是阶乘！

我是偷懒了，举个例子，你可以当成不是阶乘，而是任意数，依次从列表里pop出来
你当成阶乘算也行，大数的阶乘直接也是算不出来的。

SixPy

2. 给你一个正整数长列表 L, 如 L=[2，4，6，8，10，...，10**7], 输出L内所有数字的乘积末尾0的个数

1. >>> sum(range(1, 7+1))
   
2. 28

复制代码

jerryxjr1220

SixPy 发表于 2016-11-16 11:04

应该不止吧，单单10**7就7个0了，还有10**7-10呢？，10**7-20......，还有10**6......

SixPy

jerryxjr1220 发表于 2016-11-16 11:09
应该不止吧，单单10**7就7个0了，还有10**7-10呢？，10**7-20......，还有10**6......

1. >>> sum(range(10,10**7+1,10))
   
2. 5000005000000

复制代码

这样？

SixPy

2. 给你一个正整数长列表 L, 如 L=[2，4，6，8，10，...，10**7], 输出L内所有数字的乘积末尾0的个数

1. >>> sum((int(math.log10(x))for x in range(10,10**7+10,10)))
   
2. 5888896
   

复制代码

tsembrace

目前只会2： 给你一个正整数长列表 L, 如 L=[2，4，6，8，10，...，10**7], 输出L内所有数字的乘积末尾0的个数

1. import time
   
2. 
   
3. start=time.clock()
   
4. lst=[]
   
5. number=1
   
6. counter=0
   
7. for i in range(1,10**7+1):
   
8.     if i%2==0:
   
9.         lst.append(i)
   
10. 
    
11. for i in lst:
    
12.     while i%10==0:
    
13.         counter+=1
    
14.         i=i//10
    
15. 
    
16. print("乘积末尾0的个数为："+str(counter))
    
17. end=time.clock()
    
18. print("程序运行耗时："+str(end-start)+"秒.")
    

复制代码

乘积末尾0的个数为：1111111
程序运行耗时：2.9052774056821926秒.

tsembrace

3. 给你一个正整数长列表 L, 如 L=[1，2，3，4，5，...，10**7], 判断列表内所有数字乘积的最后一个非零数字的奇偶，如果是奇数输出1，偶数输出0

1. import time
   
2. 
   
3. start=time.clock()
   
4. 
   
5. def func(n):
   
6.     number=1
   
7.     for i in range(1,n+1):
   
8.         number*=i
   
9.         while number%10==0:
   
10.             number//=10
    
11.         number%=10
    
12.     print("测试数为:"+str(n)+"————",end="")
    
13.     print("乘积最后一个非零数字为:"+str(number))
    
14.     if number%2==0:
    
15.         return 0
    
16.     else:
    
17.         return 1
    
18.         
    
19. i=func(10**7)
    
20. if i==1:
    
21.     print("奇数")
    
22. else:
    
23.     print("偶数")
    
24. end=time.clock()
    
25. print("程序运行耗时："+str(end-start)+"秒.")
    
26. 
    

复制代码

测试数为:10000000————乘积最后一个非零数字为:8
偶数
程序运行耗时：3.0042540711162005秒.

jerryxjr1220

tsembrace 发表于 2016-11-16 12:31
目前只会2： 给你一个正整数长列表 L, 如 L=[2，4，6，8，10，...，10**7], 输出L内所有数字的乘积末尾0的 ...

往这个方向考虑是对的，但是算法是错误的哦。
不能光数0，还要考虑进位0的问题，比如末尾数是8，乘以50的话，结果是400，就要多一个0出来哦。

jerryxjr1220

SixPy 发表于 2016-11-16 11:51

帮你用上限100验算了一下，结果不对哦。
你应该也没考虑*50 这种可能要进位的问题吧？

冬雪雪冬

先做一下第二题，不知结果对不对。
修改了一下，原来range到10**7，按题意应该是10**7 + 1

1. zero =0
   
2. for i in range(10, 10**7 + 1, 10):
   
3.     while True:
   
4. 
   
5.         if i % 10 != 0:
   
6.             break
   
7.         i //= 10
   
8.         zero += 1
   
9.     if i % 390625 == 0:
   
10.         zero += 8
    
11.     elif i % 78125 == 0:
    
12.         zero += 7
    
13.     elif i % 15625 ==0:
    
14.         zero += 6
    
15.     elif i % 3125 == 0:
    
16.         zero += 5
    
17.     elif i % 625 == 0:
    
18.         zero += 4
    
19.     elif i % 125 == 0:
    
20.         zero += 3
    
21.     elif i % 25 == 0:
    
22.         zero += 2
    
23.     elif i % 5 == 0:
    
24.         zero += 1
    
25. print(zero)

复制代码

1. 1249998

复制代码

tsembrace

jerryxjr1220 发表于 2016-11-16 13:17
往这个方向考虑是对的，但是算法是错误的哦。
不能光数0，还要考虑进位0的问题，比如末尾数是8，乘以50 ...

我原先算法是 考虑的，所以设置了number变量，编写的时候忘记了。。。
但回头来看原先算法：

1. for i in lst:
   
2.     number*=i
   
3.     while number%10==0:
   
4.         counter+=1
   
5.         number//=10

复制代码

速度已经无法忍受了
大概这种题目直接算乘法的话速度是很难有效解决的。
出现尾数0的情况有两种：
1、直接乘数就有0，如10，20，370，5550这些。
2、就是如你所说的两数字乘后产生，这种情况只能为尾数是5，而对于这种数列，每个尾数有5的数字总能分别至少找到1个偶数与其匹配相乘产生尾数0。
所以结果就是上述1+2.
思路大致如此吧。

jerryxjr1220

冬雪雪冬 发表于 2016-11-16 14:02
先做一下第二题，不知结果对不对。

答案很接近了，但是10**7次方，你还少算一种 i%1953125的情况。
不过你的算法挺新颖的 哈哈

冬雪雪冬

jerryxjr1220 发表于 2016-11-16 14:13
答案很接近了，但是10**7次方，你还少算一种 i%1953125的情况。
不过你的算法挺新颖的 哈哈

10**7-1为7位数，但最后一位是是偶数，只有为0才有意义。所以剩下的最多只能是6位。

jerryxjr1220

冬雪雪冬 发表于 2016-11-16 14:22
10**7-1为7位数，但最后一位是是偶数，只有为0才有意义。所以剩下的最多只能是6位。

你确定你把10**7也算上了，因为你的答案正好差了7

tsembrace

第二题代码，思路大致如前面所述，但实现代码中还有不少需要细化的地方。

1. import time
   
2. 
   
3. start=time.clock()
   
4. lst=[]
   
5. number=1
   
6. counter=0
   
7. for i in range(1,10**7+1):
   
8.     if i%2==0:
   
9.         lst.append(i)
   
10. 
    
11. 
    
12. for i in lst:
    
13.     #对于该偶数数列，首先判断是否尾数为0，多个0用while循环计算
    
14.     while i %10==0:
    
15.         counter+=1
    
16.         i//=10
    
17.         j=i
    
18.         #去除0后尾数为5的情况（存在足够多的偶数与之乘变成0）
    
19.         while j%10==5:
    
20.             counter+=1
    
21.             j//=5
    
22. 
    
23. print("乘积末尾0的个数为："+str(counter))
    
24. end=time.clock()
    
25. print("程序运行耗时："+str(end-start)+"秒.")
    

复制代码

乘积末尾0的个数为：1249998
程序运行耗时：3.1337824190978494秒.

jerryxjr1220

tsembrace 发表于 2016-11-16 14:38
第二题代码，思路大致如前面所述，但实现代码中还有不少需要细化的地方。

答对了
第二题会算了，第三题也就不难了

SixPy