蓝桥杯乘积尾0（分析）_飞道的博客

蓝桥杯乘积尾0（分析）

2021-04-17 15:41 210人阅读评论(0)

1. 问题描述：

如下的10行数据，每行有10个整数，请你求出它们的乘积的末尾有多少个零？

输出

输出一个整数表示答案

来源：http://oj.ecustacm.cn/problem.php?id=1361

2. 思路分析：

一开始的时候没有什么思路，感觉这么多大的数相乘肯定是出现溢出的情况，但是在使用python语言相乘的时候发现竟然没有出现结果溢出的情况。在网上查找了一下资料发现可以计算这些数字中包含着2的数目与5的数目的个数，两个数目的最小值就是乘积尾0的个数。具体的思路：首先0是由2 * 5得到的，所以我们需要计算出能够相互匹配的2和5的个数，也就是因子2和因子5的最小值，举一个简单的例子：4 * 25 = 100，其中4包括两个2，25包括两个5所以最终2和5匹配的数目为2也即乘积尾0的个数就是2，所以问题就转化为求解这些数字中因子2的数目和因子5的数目。因为数字比较多所以将这些数字复制到一个txt文件中，通过readlines方法读取整个文件，方法的返回值为包含文件中每一行内容的字符串类型，然后通过去除掉每一行的换行符使用空格对其分割得到字符串列表，遍历这个列表将字符串转为数字求解当前的数字中包含2和5的个数。这里可以使用一个递归的方法求解（也可以使用一个迭代的方法求解），每一次能够被当前的因子2或者5整除的时候那么就继续递归直到不能够被整除了那么返回0，每一次能够被整除的时候计数都是加1的。最终的答案是31。

3. 代码如下：


  
   
    
     
    
    
     
      # 递归方法求解当前数字中包含因子factor的数目
     
    
   
    
     
    
    
     
      def countFactors(n: int, factor: int):
     
    
   
    
     
    
    
         
      if n % factor != 
      0:
     
    
   
    
     
    
    
             
      return 
      0
     
    
   
    
     
    
    
         
      else:
     
    
   
    
     
    
    
             
      return 
      1 + countFactors(n // factor, factor)
     
    
   
    
     
    
    
      
     
    
   
    
     
    
    
      
     
    
   
    
     
    
    
     
      if __name__ == 
      '__main__':
     
    
   
    
     
    
    
     
          file = open(
      "data.txt", 
      "r+")
     
    
   
    
     
    
    
         
      # 读取整个文件
     
    
   
    
     
    
    
     
          txt = file.readlines()
     
    
   
    
     
    
    
     
          res = 
      1
     
    
   
    
     
    
    
     
          cnt2, cnt5 = 
      0, 
      0
     
    
   
    
     
    
    
         
      for line 
      in txt:
     
    
   
    
     
    
    
     
              nums = line.strip(
      "\n").split()
     
    
   
    
     
    
    
             
      for n 
      in nums:
     
    
   
    
     
    
    
     
                  res *= int(n)
     
    
   
    
     
    
    
     
                  cnt2 += countFactors(int(n), 
      2)
     
    
   
    
     
    
    
     
                  cnt5 += countFactors(int(n), 
      5)
     
    
   
    
     
    
    
     
          print(min(cnt2, cnt5))
     
    
   
    
     
    
    
     
          print(res)

转载：https://blog.csdn.net/qq_39445165/article/details/115762533

查看评论

飞道的博客

飞道的博客

个人资料

文章分类

文章存档

阅读排行

评论排行

推荐文章

蓝桥杯乘积尾0（分析）

* 以上用户言论只代表其个人观点，不代表本网站的观点或立场