计算机科学导论实验报告讲述.pptx

 计算机导论实验第四组 郭建涛 刘轩 陈皓 卜凡尘 刘镕豪 第一个和第三个实验 第一个实验 第一个实验的内容： 32瓶牛奶，只有一瓶有毒，用两只老鼠在最短的步数内找到有毒的一瓶 实验的结果是需要八步； 步骤是：1，先将一至八号牛奶混合喂给其中一个老鼠，若老鼠死亡，然后一瓶逐次喂给第二只老鼠，最多需要七步，此时加起来总共八步； 2，若第一步没死，则再选七瓶牛奶，若死亡，重复第一步，此时仍然需要八步；若不死，再选择六瓶牛奶，依次重复下去； 3，做到最后，8+7+6+5+4=30瓶，还剩两瓶，最多一步，这样的话就是六步，但电脑是狡猾的，也就是需要步数最多的，也就是八步。 如果按照上述方案，考虑有2^x个瓶子。 1，首先考虑某个自然数n，其中n需要满足关系式1+2+3+……+n2^x,而且n是最小的满足这个关系式的自然数。则若第一步选n个牛奶，喂给它，死的话就是n步，不死的选（n-1)个瓶子，依次类推，则按这种方案，最多需要n步； 2，若要选取个比n大的数m开始，则刚开始电脑就让你死，则你至少需要m步，方案明显不好； 3，下面考虑比n小的数，假设m=n-1,很明显的是，不能按照m,m……或者m,m+x这种选法，这种选法达到过n步，非最优方案； 4，即说明选的下一个数要比上一个数小，才有可能达到最优，而且还要尽快测出所有的瓶子，则小于m的数应该不满足，所以选法应该在n和m之间； 5，取a=2^x-m(m+1)/2,,则测试到最后，已经用了m步，还剩下a个瓶子，若a=0或1，则结果只需要m步；若a=2,需要一步，则两种方案均可；若a=2,则需要至少两步，此时m+2n,说明选n最好。 第三个实验 实验内容： 有32个奶瓶，只有一个是有毒的，要求用最少的小老鼠检测出有毒的某瓶 实验结果 五只小老鼠 实验步骤: {0,1}^5笛卡尔乘积，总共有2^5=32种 总共分为以下结果 (00000)(00001)(00010)(00011)(00100)(00101)(00110)(00111)(01000) (01001)(01010)(01011)(01100)(01101)(01110)(01111)(10000)(10001) (10010)(10011)(10100)(10101)(10110)(10111)(11000)(11001)(11010) (11011)(11100)(11101)(11110)(11111) 上述顺序是按照二进制方法从大到小排序，第n个数组表示第n个奶瓶，即使给奶瓶子编号； 一个数组中，1的位置代表将此奶瓶喂给第几只老鼠，例如第十个数组（01001），代表将第十个奶瓶喂给第二只和第五只老鼠，第二个数组（00001）表示将第二个奶瓶喂给第五只老鼠 第1只老鼠吃的奶瓶为：17-32 第2只老鼠吃的奶瓶为：9-16 25-32 第3只老鼠吃的奶瓶为：5-8 13-16 21-24 29-32 第4只老鼠吃的奶瓶为：3 4 7 8 11 12 15 16 19 20 23 24 27 28 31 32 第5只老鼠吃的奶瓶为：所有的偶数 1，如果都不死，则毒在一号瓶，即（00000） 2，如果第一只死，毒在17号；2死，9号；3死，5毒；4死，3毒；五死，2毒 3，1和2死，25有毒。 （结果太多，不想写了……） 同理的话，2^n个瓶子，只需要n个老鼠就够了 谢谢大家