有N个外表相同的球,其中有一个坏球,它的重量和其它N-1个不同,但不知道是偏轻还是偏重。现在有一架没有砝码的很灵敏的天平,问至少几次才能找出那个坏球,并知道它比标准球重还是轻。
时间: 2023-03-30 13:01:00 浏览: 71
这是一个经典的谜题,需要使用二分法来解决。首先将球分成两组,分别放在天平的两端,如果天平平衡,则说明坏球在剩下的球中,否则坏球在天平较轻的那组中。然后将较轻的那组球再分成两组,重复上述步骤,直到找到坏球。最坏情况下,需要称量log2(N)次才能找到坏球。至于坏球是偏轻还是偏重,则可以通过称量的结果和标准球的重量来判断。
相关问题
有N个外表相同的球,其中有一个坏球,它的重量和其它N-1个不同,但不知道是偏轻还是偏重。现在有一架没有砝码的很灵敏的天平,问至少几次才能找出那个坏球,并知道它比标准球重还是轻。
这是一个经典的谜题,需要使用二分法来解决。首先将球分成三组,每组放置在天平的两端和中间。如果天平平衡,则坏球在剩余的球中,可以将剩余的球再次分成三组进行比较。如果天平不平衡,则坏球在较轻的一组中,可以将较轻的一组的球再次分成三组进行比较。重复以上步骤,直到找到坏球并确定它是偏轻还是偏重。最坏情况下,需要比较log3(N)次才能找到坏球。
帮我写一份代码:有N个外表相同的球,其中有一个坏球,它的重量和其它N-1个不同,但不知道是偏轻还是偏重。现在有一架没有砝码的很灵敏的天平,问至少几次才能找出那个坏球,并知道它比标准球重还是轻。 【输入形式】球的个数N(小于50000个) 【输出形式】需要的称量次数K 【样例输入】119 【样例输出】5
这是一个经典的谜题,需要使用二分法来解决。首先将球分成三组,每组数量相等,然后将其中两组放在天平两端,如果天平平衡,则坏球在第三组中,否则坏球在天平较轻的一组中。接着将第三组分成三个等份,重复上述步骤,直到找到坏球。
因为每次都是将球分成三组,所以可以用三叉树来表示,每个节点表示一次称量,左子树表示天平左边较轻,右子树表示天平右边较轻,中间子树表示天平平衡。因为每次都是将球分成三组,所以树的高度为log3(N),所以需要称量的次数为log3(N)+1。
因此,代码如下:
#include <stdio.h>
#include <math.h>
int main()
{
int N, K;
scanf("%d", &N);
K = log(N-1)/log(3) + 1;
printf("%d\n", K);
return ;
}