最小假币问题的Python实现

假设由29枚硬币，其中一枚假币，假币比真币重，有一个量程和精度足够的天平，怎样保证最少称重次数找出假币？

思路：

将硬币分为3堆，则每堆的硬币数量为 n/3 ，但是这是在 n%3==0 的情况下才能成立，所以我们将 n 枚硬币分为 3 堆加 1 堆 余数堆(余数堆可能为0)，则可分为如下(n-n%3)/3, (n-n%3)/3, (n-n%3)/3, n%3。

如下分组：

a堆： (n-n%3)/3

b堆： (n-n%3)/3

c堆： (n-n%3)/3

d(余数堆): n%3

逻辑过程：

1.判断n中的硬币数量，如果n>2则执行2，否则执行4.

2.将n分为上图的四堆，拿 a 和 b 比较，如果 a > b ,则假币在 a 中。否则假币在b中。

3.如果 a == b，则拿 a 和 c 比较。如果 a == c,则假币在d(余数堆)中。将 d 再次执行流程1，并且n=n%3。如果不等，则假币在 c 中，将 c 再次 执行流程1，并且n=(n-n%3)/3。

4.如果n==2，则将两枚硬币进行比较找出假币。

5.如果n==1，则该硬币就是假币，输出结果结束

# -*- coding: utf-8 -*-
"""
Created on Sun Oct 18 20:23:22 2020

@author: chenj
"""
'list[start:end] 列表截取 包含start,不包含end'
#称重次数
times=0
'分组'
def fenzu (coins):
   n=len(coins)
   #如果硬币数量是两个则分成2组
   if n==2:
      group_a=coins[0 : 1]
      group_b=coins[1 : n] 
      print('group_a:',group_a,'group_b:',group_b)
      print('group_a_len:',len(group_a),'group_b_len:',len(group_b))
      return group_a,group_b #程序返回
   #print("length:",n)
   group_a=coins[0 : (n-n%3)//3]
   group_b=coins[(n-n%3)//3 : (n-n%3)//3*2]
   group_c=coins[(n-n%3)//3*2 : n-n%3]
   group_d=coins[n-n%3 : n] #余数堆
   #输出分组的结果与分组的个数
   print('group_a:',group_a,'group_b:',group_b,'group_c:',group_c,'group_d:',group_d)
   print('group_a:',len(group_a),'group_b:',
         len(group_b),'group_c:',len(group_c),'group_d:',len(group_d))
   return group_a,group_b,group_c,group_d

'两个组重量大小比较'
def chengzhong (group_a,group_b):
   if sum(group_a) > sum(group_b):
       result=('left')
   elif sum(group_a) < sum(group_b):
       result=('right')
   else:
       result =('equal')
   return result
'返回假币的列表组'
def find_fake2(group_a,group_b):
   res=chengzhong (group_a,group_b)
   if res=='left':
       return group_a
   elif res=='right':
       return group_b
'返回假币的列表组'
def find_fake(group_a,group_b,group_c,group_d):
   res=chengzhong (group_a,group_b)
   if res=='left':
       return group_a
   elif res=='right':
       return group_b
   elif res=='equal':   #如果a组和b组等 则比较a和c
       res = chengzhong(group_a, group_c)
       if res == 'equal': #如果相等返回d组(余数堆)
           print('a=b=c')
           global times #使用全局变量
           times += 1
           return group_d
       if res !='equal': #如果不相等则c为错误堆
           return group_c
       
'硬币的比较主要函数' 
def bianlifind(coins):
   global times #使用全局变量
   search_list=coins
   while len(search_list)> 1:
       print('search_list'+str(times),search_list,'search_list_len',len(search_list))
       if len(search_list)==2: #如果列表长度为2
           g1,g2=fenzu(search_list)
           search_list=find_fake2(g1,g2)
           times += 1
       else:
           g1,g2,g3,g4=fenzu(search_list)
           search_list=find_fake(g1,g2,g3,g4)
           times += 1
   fake=search_list[0] #列表只有一个时直接取出假币
#python的print字符串前面加f表示格式化字符串，
#加f后可以在字符串里面使用用花括号括起来的变量和表达式，
#如果字符串里面没有表达式，那么前面加不加f输出应该都一样.
   print(f'错误的硬币的重量{fake}')
   print('这个重硬币是在原始硬币的第', coins.index(fake)+1, '个位置')
   print(f'称重次数{times}')
'定义硬币的列表有一枚假币，1为真，2为假'
coins=[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,1]
#coins=[1,1,1,1,1,1,1,1,2]
bianlifind(coins)

运行结果：

本文地址：https://blog.csdn.net/qq_42324086/article/details/109256897