相关知识
找假币问题是一个比较简单且典型能够体现计算思维的问题。假设现在有n(n>=2)枚硬币,已知其中一枚为假币,且知道假币的重量是比真币轻的,请思考如何用分治思想解决该问题。
算法原理
本次实验中我们采用二分法解决假币问题。二分法是一个非常典型的分治思想的应用。
如果n是偶数,将n个硬币平均分成两份,直接比较这两份硬币的重量,假币在重量较轻的那份硬币中,继续对重量较轻的那一份硬币使用二分法,直到找出假币;
如果n是奇数,则随意取出一种的一枚硬币,将剩下的n-1枚硬币等分成两份。如果这两份硬币重量相同,则随机取出的那枚硬币即为假币;否则,按照硬币数为偶数是的处理办法继续执行算法。
测试输入:
3(此处省略七个3),2
预期输出 :
position is: 7, weight is: 2.
'''
先搞搞思路, 写几行伪代码
1、输入n,真币重量a,假币重量b,假币位置m , 约束 b<a
2、初始化 列表 list_n
list_n = [a for n in range(n)]
list_n[m-1] = b
3、根据列表长度切列表,比较,如未找到,继续遍历重量小的列表,直到切完。
'''
def show_result(l):
print('Find! position is: {}, weight is: {}.'.format(l[0],l[1]))
work_cmd = input("请输入硬币n,真币重量a,假币重量b,假币位置m , 约束 b<a:\nn a b m\t")
work_num = [int(x) for x in work_cmd.split(" ")]
if (work_num[2] < work_num[1]) and (work_num[0]>1) and (work_num[3] <= work_num[0]):
list_n = [[i+1,work_num[1]] for i in range(work_num[0])]
list_n[work_num[3]-1][1] = work_num[2]
print("硬币列表", list_n)
while len(list_n) > 1:
listlen = len(list_n)
offset1 = listlen // 2
offset2 = offset1
if listlen % 2 == 1:
offset2 = offset2 + 1
list1 = list_n[:offset1]
list2 = list_n[offset2:]
sum1 = sum([n[1] for n in list1])
sum2 = sum([n[1] for n in list2])
if sum1 == sum2 :
if offset1 != offset2:
show_result(list_n[offset1])
break
else:
print('Not Find!')
else:
if sum1 < sum2:
if len(list1)==1:
show_result(list1[0])
break
list_n = list1
else:
if len(list2)==1:
show_result(list2[0])
break
list_n = list2
else:
print("约束条件", '未符合,结束程序。')