python之结尾0的个数

时间:2022-01-20 18:25:13

1.贴题

题目来自PythonTip
结尾0的个数


给你一个正整数列表 L, 输出L内所有数字的乘积末尾0的个数。(提示:不要直接相乘,数字很多,相乘得到的结果可能会很大)。

例如: L=[2,8,3,50],

则输出:2


2.说明

在这道题上花了蛮长时间的,因为一直想不到好的方案。

错误方案!!!

一开始想的方案是分别统计0,2,4,6,8,5的个数,然后0就单独计一次。然后2,6计一次,4计两次,8计三次,加起来后和5的个数取小的,再加上刚刚0的次数。但是后来发现这样把每个数中间的0也计算进去了,就增加代码从后往前看,看到不是0就跳出循环。但是提交后还是不对,最后发现这样还是有问题的。例如L=[4,25],或L=[16,2500]就会得到错误的答案。

正确思路

思路来自fiveyes 发表于 2018-03-04 16:10:52

把每个数分解成若干个2相乘,以及若干个5相乘,最后统计2和5的个数,输出较小的一个就可以了,不需要统计0的个数,因为10也是由2*5得来的。

例如L=[4,25],统计结果2*2,5*5,所以是2个0。L=[16,2500],统计结果是6个2,4个5,所以是4个0。

3.参考代码

two = 0 #预设two为0
five = 0 #预设five为0
for i in L: #对L的每个元素进行遍历
    while i % 2 == 0: #只要还有2的因子
        two += 1 #two加一
        i = i / 2 #除掉一个2
    while i % 5 == 0: #只要还有5的因子
        five += 1 #five加一
        i = i / 5 #除掉一个5

print(min(two,five)) #打印two和five中小的一个

4.其他写法

1.递归法 来自yellowyao13
每次取一个数,与之前留下来不能被10整除的部分相乘,取出可以被10整除的部分,同时计数。

def find_10(a,b):
    if a%10==0:
        a,b=a/10,b+1
        a,b=find_10(a, b)
    else:
        a = a % 10
    return a,b

a,b=1,0
for i in range(1,len(L)+1):
    a*=L[i-1]
    a, b = find_10(a, b)
print(b)

2.原理同上非递归 来自sin7
上面是判断是否被10整除,这里判断从末位往前是否为零。

temp,c = 1,0
for x in L[::1]:
    temp = temp*x
    t = str(temp)
    for y in t[::-1]:
        if y=='0':
            c += 1
        else:
            temp = int(y)
            break
print(c)

3.使用reduce函数 来自Lands

from functools import reduce

def get_zero(L):
    count = 0
    a = reduce(lambda x,y: x*y, L)
    while a % 10 == 0:
        count += 1
        a //= 10
    return count

print(get_zero(L))

关于reduce函数,可参考菜鸟教程

5.总结

总结起来有两种思路
1. 将列表中的元素因式分解,分别统计2因子的个数和5因子的个数,最后取小的一个
2. 每次取一个数与之前无法被10整除的部分相乘,检验是否能被10整除,去掉被10整除的部分并计数,直到所有数都处理完

方法总结为
1. 简单循环法
2. 递归法
3. 末尾判断0法
4. 函数配合法

6.存档错误代码!!!

s = ""
zero = 0
for i in list(map(str,L)):
    for j in range(len(i)-1,-1,-1):
        if i[j] != "0":
            break
        else:
            zero += 1
    s += i

two = s.count("2")
four = s.count("4")
six = s.count("6")
eight = s.count("8")
five = s.count("5")
print(zero + min(two + 2*four + six + 3*eight, five))