有一堆共n枚硬币,其中一枚是假币,外观上无法区分,只知道假币的重量稍轻。要求仅使用一个天平,使用最少的重量比较次数找出假硬币。 将n个硬币分成数量相同的两堆,如果n为偶数,每堆的硬币个数为n/2; 如果n为奇数,每堆的硬币个数为(n-1)/2,两堆之外还会剩余一个硬币。 将两堆硬币上天平比较重量,如果有一堆较轻,那么假的硬币必然在轻的那一堆中。如果两堆硬币重量相等,且两堆之外有一个剩余硬币,则那个剩余硬币就是假硬币。如果两堆硬币重量相等,且两堆之外没有剩余硬币,则查找任务失败,未发现假硬币。 编写函数findFalseCoin(coins,start,n)并调用 实现"在读入的coins列表中,从下标start开始的n个硬币中查找假硬币"
时间: 2023-06-07 17:07:13 浏览: 40
def findFalseCoin(coins, start, n):
if n == 1:
return start
half = n//2
left = findFalseCoin(coins, start, half)
right = findFalseCoin(coins, start+half, n-half)
if sum(coins[left:start+half]) < sum(coins[right:start+half]):
return left
elif sum(coins[left:start+half]) > sum(coins[right:start+half]):
return right
elif n%2 == 0:
return -1
else:
return start+n-1
相关问题
py有一堆共n枚硬币,其中一枚是假币,外观上无法区分,只知道假币的重量稍轻。要求仅使用一个天平,使用最少的重量比较次数找出假硬币。
这是一道经典的数学问题。可以采用二分法,将硬币分成两份,分别放在天平两端,比较重量。假设一半硬币重量为x,另一半为y,若天平平衡,则假硬币在剩下的一半中,否则在轻的那一半中,再次将轻的那一半重复上述步骤,最终找到假硬币。这个问题最少需要进行log2(n)次比较来找出假硬币。
有n枚硬币,其中有一枚硬币是假币,且假币的重量较轻,通过一架天平找出假币。比较次数最少。
可以采用二分法的思想,将n枚硬币分成两组,分别放在天平的两端,比较两端的重量,如果两端重量相等,则假币在剩下的n/2枚硬币中,否则假币在较轻的一组中。然后再将较轻的一组硬币继续分成两组,重复上述步骤,直到找出假币。这样比较的次数最少,为log2(n)次。