呼唤954 2021-12-11 10:01 采纳率: 100%
浏览 34
已结题

想要请教一下这个python问题该怎么解决

相关知识
找假币问题是一个比较简单且典型能够体现计算思维的问题。假设现在有n(n>=2)枚硬币,已知其中一枚为假币,且知道假币的重量是比真币轻的,请思考如何用分治思想解决该问题。

算法原理
本次实验中我们采用二分法解决假币问题。二分法是一个非常典型的分治思想的应用。

如果n是偶数,将n个硬币平均分成两份,直接比较这两份硬币的重量,假币在重量较轻的那份硬币中,继续对重量较轻的那一份硬币使用二分法,直到找出假币;
如果n是奇数,则随意取出一种的一枚硬币,将剩下的n-1枚硬币等分成两份。如果这两份硬币重量相同,则随机取出的那枚硬币即为假币;否则,按照硬币数为偶数是的处理办法继续执行算法。

测试输入:
3(此处省略七个3),2
预期输出 :
position is: 7, weight is: 2.

  • 写回答

1条回答 默认 最新

  • 陈年椰子 2021-12-11 13:50
    关注

    img

    img

    img

    
    '''
    先搞搞思路, 写几行伪代码
    
    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("约束条件", '未符合,结束程序。')
    
    
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

问题事件

  • 系统已结题 12月21日
  • 已采纳回答 12月13日
  • 创建了问题 12月11日

悬赏问题

  • ¥15 有没有整苹果智能分拣线上图像数据
  • ¥20 有没有人会这个东西的
  • ¥15 cfx考虑调整“enforce system memory limit”参数的设置
  • ¥30 航迹分离,航迹增强,误差分析
  • ¥15 Chrome Manifest扩展引用Ajax-hook库拦截请求失败
  • ¥15 用Ros中的Topic通讯方式控制小乌龟的速度,走矩形;编写订阅器代码
  • ¥15 LLM accuracy检测
  • ¥15 pycharm添加远程解释器报错
  • ¥15 如何让子窗口鼠标滚动独立,不要传递消息给主窗口
  • ¥15 如何能达到用ping0.cc检测成这样?如图