您好,欢迎访问代理记账网站
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

Python学习与练习二

分治法找假币
【问题描述】

有一堆共n枚硬币,其中一枚是假币,外观上无法区分,只知道假币的重量稍轻。要求仅使用一个天平,使用最少的重量比较次数找出假硬币。
将n个硬币分成数量相同的两堆,如果n为偶数,每堆的硬币个数为n/2;
如果n为奇数,每堆的硬币个数为(n-1)/2,两堆之外还会剩余一个硬币。
将两堆硬币上天平比较重量,如果有一堆较轻,那么假的硬币必然在轻的那一堆中。如果两堆硬币重量相等,且两堆之外有一个剩余硬币,则那个剩余硬币就是假硬币。如果两堆硬币重量相等,且两堆之外没有剩余硬币,则查找任务失败,未发现假硬币。
编写函数findFalseCoin(coins,start,n)并调用
实现"在读入的coins列表中,从下标start开始的n个硬币中查找假硬币"
【输入形式】
【输出形式】
【样例输入】

100,100,100,99,100,100,100,100,100

【样例输出】

Fake coin:3

<代码是自己在学习Python过程中的作业,是自己写的>
代码如下:

def findFalseCoin(coins,start,n):
    if n==1:
        return 0;
    if n%2==0:
        coins1 = coins[start:start+(n//2)]
        coins2 = coins[start+(n//2):start+n]
        if sum(coins1) == sum(coins2):
            return -1
        elif sum(coins1) > sum(coins2):
            return start + (n//2) + findFalseCoin(coins2, 0, len(coins2))
        elif sum(coins1) < sum(coins2):
            return start + findFalseCoin(coins1, 0, len(coins1))
    else:
        coins1 = coins[start:start+((n-1)//2)]
        coins2 = coins[start+((n-1)//2):start+n-1]
        if sum(coins1) == sum(coins2):
            return n-1
        elif sum(coins1) > sum(coins2):
            return start + ((n-1)//2) + findFalseCoin(coins2, 0, len(coins2))
        elif sum(coins1) < sum(coins2):
            return start + findFalseCoin(coins1, 0, len(coins1))
    pass
coins = list(map(int,input().split(',')))
x = findFalseCoin(coins, 0, len(coins))
if x==-1:
    print("Fake coin is not found")
else:
    print("Fake coin:%d"%x)

分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进