1000瓶酒的思考

上次我在星网锐捷笔试中，有道题目是这样的
在一个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
#include

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   {
    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   ans +=pow(2,prison[j]-1);
   printf("得出有毒的酒是第%d瓶/n/n",ans);
 }

 return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！