BYR Achieve · 镜像论坛

☆─────────────────────────────────────☆ redfox (redfox) 于 (Fri Jul 6 18:33:47 2007) 提到: 有1000瓶水，其中有一瓶有剧毒（假设哪怕一个毒药分子在里面也能致命），现在给你10只小狗在24小时内通过小狗试药的方式鉴定出来哪瓶药有毒。情况1：假设小狗服药后2小时内即可判断是否中毒，鉴别方案有哪些？情况2：假设小狗服药之后20小时才能判断是否中毒，鉴别方案又是什么? ☆─────────────────────────────────────☆ CNLAS (Ich gewinne bestimmt……) 于 (Fri Jul 6 18:47:54 2007) 提到: 很赞的算法题。。。水木上就有答案。。。-v- 是在想不出来的可以过去看。。。 ☆─────────────────────────────────────☆ diysimon (真情的Forain就是我) 于 (Fri Jul 6 19:28:49 2007) 提到: 嗯。。。。同在水木上看完了。。。 _V_ ☆─────────────────────────────────────☆ mmgroup (からす) 于 (Fri Jul 6 19:54:45 2007) 提到: 同看完…… 知道为什么是20小时不是23小时了……真干起来一小时可能搞不定的.. 飘走... ☆─────────────────────────────────────☆ ComicLiu (Lookis) 于 (Sat Jul 7 00:23:45 2007) 提到: 小狗不会撑死么?1000瓶水啊... ☆─────────────────────────────────────☆ thq2004423 (John Avon) 于 (Sat Jul 7 00:32:24 2007) 提到: 【在 ComicLiu 的大作中提到: 】 : 小狗不会撑死么?1000瓶水啊... 假设哪怕一个毒药分子在里面也能致命 ☆─────────────────────────────────────☆ zwz (Claymore No.47 Logo) 于 (Sat Jul 7 01:04:37 2007) 提到: 实在想不出来。。。。。。。同看。=。= ☆─────────────────────────────────────☆ newton (孙氏春秋) 于 (Sat Jul 7 01:39:06 2007) 提到: 喝过水没中毒的是不是可以接着喝？ ☆─────────────────────────────────────☆ chenjiajing (蔡JJ's fans) 于 (Sat Jul 7 02:17:34 2007) 提到: 1，对半对半的试验，500－250－125－63－32－16－8－4－1－1－1，22小时搞定 2，排列组合，C（0，10）＋C（1，10）＋。。。C（10，10）＝10！》1000，根据狗的死亡情况可以判定数学解法是这样的 ☆─────────────────────────────────────☆ zzg1987102 (明日帝国) 于 (Sat Jul 7 03:41:39 2007) 提到: 你没有看清楚题目吧只要一个毒药分子都是致命的需要每瓶都喝光吗??? ☆─────────────────────────────────────☆ nusher (相逢恨早) 于 (Sat Jul 7 08:42:52 2007) 提到: 【在 chenjiajing 的大作中提到: 】 : 1，对半对半的试验，500－250－125－63－32－16－8－4－1－1－1，22小时搞定 : 2，排列组合，C（0，10）＋C（1，10）＋。。。C（10，10）＝10！》1000，根据狗的死亡情况可以判定 : 数学解法是这样的那个20小时的怎么解呢? ☆─────────────────────────────────────☆ joeyak47 (何足道) 于 (Sat Jul 7 09:16:07 2007) 提到: 每隔五分钟喝一次，看什么时候挂。。。 ☆─────────────────────────────────────☆ raulforever (raul－永远的王子) 于 (Sat Jul 7 10:40:26 2007) 提到: 水兑着喝呗 ☆─────────────────────────────────────☆ nusher (相逢恨早) 于 (Sat Jul 7 10:54:18 2007) 提到: 【在 joeyak47 的大作中提到: 】 : 每隔五分钟喝一次，看什么时候挂。。。那样都行的话,每隔一分钟喝都可以啊!!!! ☆─────────────────────────────────────☆ mayi103 (蚂蚁103) 于 (Sat Jul 7 11:28:02 2007) 提到: 2的10次方大于1000 ☆─────────────────────────────────────☆ flame (找实习ing) 于 (Sat Jul 7 11:32:28 2007) 提到: 分组 ☆─────────────────────────────────────☆ dadafer (立正·稍息·向前看|Qbic) 于 (Sat Jul 7 12:18:43 2007) 提到: 情况1：开始分10组的话，8小时搞定。最坏的情况是最后剩下10瓶水8只狗，然后 13 14 15 26 27 28 9 0 情况2：我的思路是搞几个类似于1中的交集，分时段喝下去，具体怎么分还没想好 ☆─────────────────────────────────────☆ dadafer (立正·稍息·向前看|Qbic) 于 (Sat Jul 7 12:37:11 2007) 提到: 看过答案了，思路基本正确..... 不过我对2进制不怎么敏感啊.... ☆─────────────────────────────────────☆ joeyak47 (何足道) 于 (Sat Jul 7 13:19:19 2007) 提到: 【在 nusher 的大作中提到: 】 : 那样都行的话,每隔一分钟喝都可以啊!!!! 有什么不可以么，我觉得可以阿，至少逻辑上没什么问题 ☆─────────────────────────────────────☆ nusher (相逢恨早) 于 (Sat Jul 7 13:30:16 2007) 提到: 【在 dadafer 的大作中提到: 】 : 看过答案了，思路基本正确..... : 不过我对2进制不怎么敏感啊.... 能把答案的地址发上来吗? 不知道去水木的哪找,对水木不熟悉..... ☆─────────────────────────────────────☆ manage (manage) 于 (Sat Jul 7 15:01:13 2007) 提到: 1，有N只狗活着的时候，把水平均分给N只狗喝，一瓶水一次只给分给一只狗 0时刻，10只狗，1000瓶水 2小时后，9只狗，100瓶水 4小时后，8只狗，12瓶水 6小时后，7只狗，2瓶水 8小时后，6只狗，1瓶水 8个小时搞定，还有6只狗活着 1C10=10 2C10=45 3C10=120 4C10=210 5C10=252 6C10=210 7C10=120 以上之和已经大于1000了 20个小时完成，最差情况还有3只狗活着 ☆─────────────────────────────────────☆ ggbb123 (A.Doctor...) 于 (Sat Jul 7 15:18:28 2007) 提到: 【在 nusher 的大作中提到: 】 : 能把答案的地址发上来吗? : 不知道去水木的哪找,对水木不熟悉..... 水木算法板块 ☆─────────────────────────────────────☆ ggbb123 (A.Doctor...) 于 (Sat Jul 7 15:20:14 2007) 提到: 【在 nusher 的大作中提到: 】 : 能把答案的地址发上来吗? : 不知道去水木的哪找,对水木不熟悉..... 发信人: hustoff (Golden Retriever~守望牧犬羊), 信区: Algorithm 标题: 10只狗怎么鉴别1000瓶水哪瓶有毒发信站: 水木社区 (Wed Jul 4 23:56:24 2007), 站内有1000瓶水，其中有一瓶有剧毒（假设哪怕一个毒药分子在里面也能致命），现在给你10只小强在24小时内通过小强试药的方式鉴定出来哪瓶药有毒。情况1：假设小强服药后2小时内即可判断是否中毒，鉴别方案有哪些？情况2：假设小强服药之后20小时才能判断是否中毒，鉴别方案又是什么？ updated @ 2007.7.5 13:00：凌晨发了个帖子，没想到十大了。。。强人很多，第一页就出现这么多正确答案。看来很多人都对二进制很敏感呀！这个应该可以归为算法或者算法相关的题目，《编程珠玑》里面有类似的案例讲解，一个好的策略（算法）能得到很好的时间复杂度和空间复杂度。看到不少人说这题目出的太残忍了，我自己也属狗的，改蟑螂来做实验品好了：） updated @ 2007.7.5 23:25: 我一个本科同学上午十点的作答，除了8小时就可以得到正确答案的那个方案我还在验证，其他的两种可以算作陈述比较详细的正确答案：）情况1：假设狗服药后2小时内即可判断是否中毒，鉴别方案有哪些？方法一：因为2的10次方1024>1000,可以做10次分半测试。每次测原来一半数目的药瓶，确定在哪一半里面，再重复。给1000个药瓶编号，最开始用1号狗闻1号到500号药瓶，两小时后1号狗死则可确定有毒药瓶在1-500号中，否则在501-1000号中；确定后用第二条狗闻确定毒药存在其中的的500个瓶子的前250个瓶子，两小时后可确定在哪250个瓶子中有毒药瓶；类似依次125，63，32，16，8，4，2，1。最坏的情况死掉10条狗，10*2小时内找到毒药瓶。方法二：1000除以10=100，每条狗喝不同的100种混合在一起的药，可知毒药在哪100种里，100再除以9=11+1=12，每条狗喝12种混合在一起的，可知在哪12种里，接下来就不用说了，8小时内就可以知道了。方法三：见情况二。情况2：假设狗服药之后20小时才能判断是否中毒，鉴别方案又是什么？还是因为2的10次方1024>1000,用10条狗闻（1）或者不闻（0），最后死（1）或者不死（0）可组合1024个不同状态，各代表一个瓶号，可一次性将毒药瓶找出。假设有3条狗要找出8瓶药中的一瓶毒药（2的3次方=8）。3条狗分别代表3个二进制数位。瓶号二进制狗的状态瓶0 000 3条狗都不闻瓶1 001 3号狗闻瓶2 010 2号狗闻瓶3 011 2号，3号狗闻瓶4 100 1号狗闻瓶5 101 1号，3号狗闻瓶6 110 1号，2号狗闻瓶7 111 1，2，3号狗闻 20小时后，3条狗的死和活就是上面8种状态组合。假设20小时后只有2号，3号狗死了，说明瓶3有毒; 假设20小时后，1号，2号，3号狗都死了，说明瓶7有毒。把这个例子推广到10条狗1000瓶药即可，只是10条狗代表10个二进制数位。其实情况1也可以这么解决，麻烦一点。而且如果情况２是准时在20小时会中毒死亡的话，一条狗可以在不同时间吃药（20小时到24小时还有４个小时），那根据死亡时间不同来确定是第几瓶也是一种方法，不过那太容易了。可怜的Puppy。 ☆─────────────────────────────────────☆ yangsjay (J) 于 (Sat Jul 7 15:51:03 2007) 提到: 情况1：(服用1h后可得出验毒结果) 多分法查找把1000瓶水分成100x10，每100瓶分给一只小狗，小狗沾用所属的100瓶水，用去两小时，牺牲一个小狗的代价，判断出有毒的一批水 100瓶。以此类推，初步缩小范围，找到有毒的一瓶水。考虑最坏情况，把过程简单表示如下: A: 1000=100x10 2h 1d(dead dog) B: 100=12*9 2h 1d C: 12=2*8(6) 2h 1d D: 2= 1*7(2) 2h 1d 若将以上过程顺序执行A-B-C-D，则耗时8小时，折损4只狗，得出结果！情况2 ：(服用20h后可得出验毒结果) 若考虑以上过程流水线执行（假令单步操作耗时1h），可大大减少时间尝试如下： 10只狗编号为d1,d2,...,d10 t=0h: 1000瓶水均分为10批：w1，w2,...,w10 d1->w1,d2->w2,...d10->w10 (->表示沾用该批水) t=1h: 将w1(100瓶)分成10批，w1w1,w1w2,.....w1w10， w2分成10批，w2w1,w2w2,...w2w10 ...... w10分成10批，w10w1,w10w2,...w10w10 让10只小狗对应沾用w1的10批水，即： d1->w1w1,d2->w1w2,...d10->w10w10 类似的，让10只小狗对应沾用w2的10批水 ...... 让10只小狗对应沾用w10的10批水说明： 1. 这里虽然我们不知道有毒的水究竟在w1...w10的那一者，从而对w1...w10都进行了再分批验证操错，但我们知道，有毒的仅在其中的一批，对应其他无毒批水的验证操作，对狗本身不产生影响。若t=20h时，死的第一条狗为di，则毒水只会在在第i批，而不会是其他的水。 2. 不管该批水毒没毒，进一步的的分组验证都继续进行。 t=2h: 将w1w1(10瓶)分为10瓶，w1w1w1,w1w1w2...w1w1w10,分别用对应的狗沾用对应瓶水 ... ... 将w1w10(10瓶)分为10瓶，w1w10w1,w1w10w2...w1w10w10,分别用对应的狗沾用对应瓶水 ...... ...... 将w10w1(10瓶)分为10瓶，w10w1w1,w10w1w2...w10w1w10,分别用对应的狗沾用对应瓶水 ... ... 将w10w10(10瓶)分为10瓶，w10w10w1,w10w10w2...w10w10w10,分别用对应的狗沾用对应瓶水 t=20h:我们坐等结果: 还是类以与情况一的方法：初步缩小范围，找到有毒的一批水。 t=20h,死第一支狗i,得出有毒水在第i批 :wi t=21h,死第二支狗j,得出有毒水在第i批中的第j小批:wiwj t=22h,死第三支狗k,得出有毒水为第i批的第j小批的第k瓶:wiwjwk; 可见，若采用顺序执行，将耗时4x20=80h；而采用流水线执行，耗时仅为22h。以上仅为个人初步思考，写点有点乱，恐缺周详，望各位看官包涵 ☆─────────────────────────────────────☆ yangsjay (J) 于 (Sat Jul 7 15:58:18 2007) 提到: 【在 ggbb123 的大作中提到: 】 : 发信人: hustoff (Golden Retriever~守望牧犬羊), 信区: Algorithm : 标题: 10只狗怎么鉴别1000瓶水哪瓶有毒 : 发信站: 水木社区 (Wed Jul 4 23:56:24 2007), 站内 : ................... ２２楼的方法很独特我的方案中，对应情况２，始终立足情况１的解决方法，并寻求改进，显得比较冗长．２２楼另辟蹊径解决问题，实在佩服[em18] ☆─────────────────────────────────────☆ wind11 (大甲) 于 (Sat Jul 7 16:48:11 2007) 提到: 哈哈，高中时候的竞赛题目，好像用二分法。 ☆─────────────────────────────────────☆ rue (rue) 于 (Sat Jul 7 17:19:56 2007) 提到: 没看答案想了一下，采用二进制方式，10条狗可以同一时间鉴别1024个瓶子，这个应该是同时鉴别最多的了。就是22楼方式 ☆─────────────────────────────────────☆ dongdong4321 (北邮人) 于 (Sat Jul 7 17:25:23 2007) 提到: 为什么非得用小狗？？残忍啊 ☆─────────────────────────────────────☆ yanzifan (二十年，一段流浪哀伤|DEATH & REBIRTH) 于 (Sat Jul 7 19:05:00 2007) 提到: 二进制啊二进制 ☆─────────────────────────────────────☆ haimeng001 (北邮人) 于 (Sat Jul 7 19:59:58 2007) 提到: 都是二进制的解法啊 ☆─────────────────────────────────────☆ haimeng001 (北邮人) 于 (Sat Jul 7 20:03:16 2007) 提到: 只用一只狗的解法：假设死亡时间精确到10秒以内，则每10秒钟喝一瓶水，看它在20小时后哪个时段死掉就能判断了。如果精确在10秒，则需要10*1000=1w秒=1000/6=166分钟=2小时46分钟如果精确在1秒，则需要16.6分钟如果精确在0.1秒。。。 ☆─────────────────────────────────────☆ baoyibao (---- 淡静良觉 ----) 于 (Sat Jul 7 21:58:29 2007) 提到: 【在 haimeng001 的大作中提到: 】 : 只用一只狗的解法： : 假设死亡时间精确到10秒以内，则每10秒钟喝一瓶水，看它在20小时后哪个时段死掉就能判断了。 : 如果精确在10秒，则需要10*1000=1w秒=1000/6=166分钟=2小时46分钟 : ................... 这个想法有创意。。。呵呵 ☆─────────────────────────────────────☆ anima (O,ICU) 于 (Sat Jul 7 23:19:15 2007) 提到: 干吗不自己喝呢???? ☆─────────────────────────────────────☆ haimeng001 (北邮人) 于 (Sun Jul 8 00:20:42 2007) 提到: 哈哈，其实二进制的解法我都想到了，毕竟以前有过编程基础。后来作了几年销售，总想着如何用最少的代价获得结果，就得到了这个"算法"。【在 baoyibao 的大作中提到: 】 : 这个想法有创意。。。呵呵 ☆─────────────────────────────────────☆ wandao001 (wandao001) 于 (Sun Jul 8 00:35:54 2007) 提到: 我的解法：1000分成10份，每份100瓶，每瓶取出一点这样做成10份，给狗喝；2小时后看结果。取毒死狗得那一份100瓶，再分成10份，9只狗去试验，同样每瓶取一小份，其中一份没狗试验。 2小时后，如果狗没死，鉴定剩下的那份，再让9条狗去试验10瓶水。其中一瓶无狗试验。2小时后如无论狗死或否，都可鉴定出来。如果，狗死了则把这10瓶再分为5组，用5条狗去试验，2小时后，对毒死狗的那份，再试验，2小时后，就可以知道，具体那瓶有毒。这样加上你的操作时间，用不了10个小时就可搞定。不用二进制。如有错误欢迎指正 ☆─────────────────────────────────────☆ mmgroup (からす) 于 (Sun Jul 8 08:06:46 2007) 提到: 顶算法贴……这贴10大吧…… ☆─────────────────────────────────────☆ ggbb123 (A.Doctor...) 于 (Sun Jul 8 09:46:27 2007) 提到: 【在 mmgroup 的大作中提到: 】 : 顶算法贴……这贴10大吧…… 那我顶个 [em22] ☆─────────────────────────────────────☆ heartremain (五year邮人) 于 (Sun Jul 8 10:43:10 2007) 提到: 二叉树？ ☆─────────────────────────────────────☆ hbxtzzm (日月神教) 于 (Sun Jul 8 12:58:18 2007) 提到: 【在 wandao001 的大作中提到: 】 : 我的解法：1000分成10份，每份100瓶，每瓶取出一点这样做成10份，给狗喝；2小时后看结果。取毒死狗得那一份100瓶，再分成10份，9只狗去试验，同样每瓶取一小份，其中一份没狗试验。 2小时后，如果狗没死，鉴定剩下的那份，再让9条狗去试验10瓶水。其中一瓶无狗试验。2小时后如无论狗死或否，都可鉴定出来。如果，狗死了则把这10瓶再分为5组，用5条狗去试验，2小时后，对毒死狗的那份，再试验，2小时后，就可以知道，具体那瓶有毒。这样加上你的操作时间，用不了10个小时就可搞定。不用二进制。 : 如有错误欢迎指正这是情况一，二进制指的是情况二…… ☆─────────────────────────────────────☆ dadafer (立正·稍息·向前看|Qbic) 于 (Sun Jul 8 13:21:31 2007) 提到: 【在 haimeng001 的大作中提到: 】 : 哈哈，其实二进制的解法我都想到了，毕竟以前有过编程基础。 : 后来作了几年销售，总想着如何用最少的代价获得结果，就得到了这个"算法"。赞最少代价。 ☆─────────────────────────────────────☆ roubaobao (肉包包) 于 (Sun Jul 8 17:22:01 2007) 提到: 这么可爱的小狗狗怎么能用来做实验呢，太残忍了，动物保护组织协会呢！

[合集] 有1000瓶水，其中有一瓶有剧毒（假设哪怕一个毒药分子在