当前位置:文档之家› 计算机科学导论实验报告

计算机科学导论实验报告


• 4,即说明选的下一个数要比上一个数小,才有可能达到最优,而且还要尽快测出 所有的瓶子,则小于m的数应该不满足,所以选法应该在n和m之间; • 5,取a=2^x-m(m+1)/2,,则测试到最后,已经用了m步,还剩下a个瓶子,若a=0或 1,则结果只需要m步;若a=2,需要一步,则两种方案均可;若a>=2,则需要至少两 步,此时m+2>n,说明选n最好。
计算机导论实验第四组 郭建涛一个实验
第一个实验的内容: 32瓶牛奶,只有一瓶有毒,用两只老鼠在
最短的步数内找到有毒的一瓶
• 实验的结果是需要八步; • 步骤是:1,先将一至八号牛奶混合喂给其中一个老鼠,若老鼠死亡,然后一瓶 逐次喂给第二只老鼠,最多需要七步,此时加起来总共八步; • 2,若第一步没死,则再选七瓶牛奶,若死亡,重复第一步,此时仍然需要八步; 若不死,再选择六瓶牛奶,依次重复下去; • 3,做到最后,8+7+6+5+4=30瓶,还剩两瓶,最多一步,这样的话就是六步, 但电脑是狡猾的,也就是需要步数最多的,也就是八步。
第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个老鼠就够了
谢谢大家
第三个实验
• 实验内容: • 有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)表示将第二 个奶瓶喂给第五只老鼠
• 如果按照上述方案,考虑有2^x个瓶子。 • 1,首先考虑某个自然数n,其中n需要满足关系式1+2+3+……+n>2^x,而且n是最小 的满足这个关系式的自然数。则若第一步选n个牛奶,喂给它,死的话就是n步,不 死的选(n-1)个瓶子,依次类推,则按这种方案,最多需要n步; • 2,若要选取个比n大的数m开始,则刚开始电脑就让你死,则你至少需要m步,方 案明显不好; • 3,下面考虑比n小的数,假设m=n-1,很明显的是,不能按照m,m……或者m,m+x这 种选法,这种选法达到过n步,非最优方案;
相关主题