有一堆共n枚硬币,其中一枚是假币,外观上无法区分,只知道假币的重量稍轻。要求仅使用一个天平,使用最少的重量比较次数找出假硬币。 将n个硬币分成数量相同的两堆,如果n为偶数,每堆的硬币个数为n/2; 如果n为奇数,每堆的硬币个数为(n-1)/2,两堆之外还会剩余一个硬币。 将两堆硬币上天平比较重量,如果有一堆较轻,那么假的硬币必然在轻的那一堆中。如果两堆硬币重量相等,且两堆之外有一个剩余硬币,则那个剩余硬币就是假硬币。如果两堆硬币重量相等,且两堆之外没有剩余硬币,则查找任务失败,未发现假硬币。 编写函数findFalseCoin(coins,start,n)并调用 实现"在读入的coins列表中,从下标start开始的n个硬币中查找假硬币"
时间: 2023-06-07 08:07:06 浏览: 68
def findFalseCoin(coins, start, n):
if n == 1:
return start
elif n % 2 == 0:
first_half_sum = sum(coins[start:start+n//2])
second_half_sum = sum(coins[start+n//2:start+n])
if first_half_sum < second_half_sum:
return findFalseCoin(coins, start, n//2)
else:
return findFalseCoin(coins, start+n//2, n//2)
else:
first_half_sum = sum(coins[start:start+(n-1)//2])
second_half_sum = sum(coins[start+(n-1)//2+1:start+n])
if first_half_sum < second_half_sum:
return findFalseCoin(coins, start, (n-1)//2+1)
elif first_half_sum > second_half_sum:
return findFalseCoin(coins, start+(n-1)//2+1, (n-1)//2+1)
else:
return start+n-1 # 剩余一个硬币就是假硬币