1000瓶酒的思考

最新推荐文章于 2025-05-30 23:42:52 发布

pluton

最新推荐文章于 2025-05-30 23:42:52 发布

阅读量1.5k

点赞数

分类专栏：算法文章标签： fp math.h 算法 null file

本文链接：https://blog.csdn.net/pluton/article/details/1445722

版权

算法专栏收录该内容

5 篇文章

订阅专栏

上次我在星网锐捷笔试中，有道题目是这样的
在一个part中有准备了1000瓶酒，但其中有一瓶是毒酒，要求用最少的囚犯测出毒酒
毒酒发作时间略短于part开始的时间，发作后囚犯会死。（这里暗示每个囚犯只能喝一次酒，但可以喝多瓶）

当时我没有想出来，因为当时我纠缠于一个不是试卷上的算法浪费了很多时间所以没有仔细去想，后来听其他有去的人讲起
我才认真做了一下。

对于这道题我得出的答案是10个囚犯。
我是这样想的如果把10个囚犯看成二进制的话就有2的10次方也就

是1024种组合
这个数刚好大于1000，问题是囚犯喝酒的分配。
我将10个囚犯按1至10编号，将1000瓶酒按1至1000编号，
通过对少量数据的分析我得到一个规律：
囚犯1喝1，3，，999
囚犯2喝2，3，，，6，7，，，998，999
囚犯3喝4，5，6，7，，，12，13，14，15，，，996，997，998，999
囚犯m喝以2的m-1次方为开始连续2的m-1次方个数，接着是以2的m次方为公差的
等差排列并且连续2的m-1次方个数

下面的的代码计算出每个囚犯需要喝哪些酒
#include <stdio.h>
#include <math.h>

int main()
{
int m,i,j,t,prison[10],ans;
FILE *fp;
if((fp=fopen("poison.txt","wb"))==NULL)
return 1;

for(m=1;m<=10;m++)
{
printf("第%d个囚犯要喝的酒/n",m);
fprintf(fp,"/r/n第%d个囚犯要喝的酒:/r/n",m);
for(j=1;;j++)
{
   for(i=0;i<pow(2,m-1);i++)
   {
    t=pow(2,m-1)+i+pow(2,m)*(j-1);
    if(t>1000)break;
    printf("%5d",t);
    fprintf(fp,"%5d",t);
   }
   if(t>1000)break;
   }
   getchar();
}
fclose(fp);

while(1)
{
   puts("请输入被毒死的囚犯的编号");
   i=0;ans=0;
   do
   {
   scanf("%d",&prison[i]);
   i++;
   }while(getchar()!='/n');
   for(j=0;j<i;j++)
   ans +=pow(2,prison[j]-1);
   printf("得出有毒的酒是第%d瓶/n/n",ans);
}

return 0;
}