N年前的难题..做出来的报个道

呆瓜小贼

%&175 问题：有十二个小球，一架没有砝码的天平，知道有一个小球质量与其它标准小球不同，但不知是轻还是重。用天平至少称几次可以挑出这个不标准的小球？写出详细过程和各种情况？以及不标准球是轻还是重？

kidfake

3次,用策略树,能确定轻或重
顺带一提，这个题有推广：对于给定的自然数N，我们怎么来解有N个球的称球问题？

呆瓜小贼

3次没错..但能解释一下策略树吗...我只听得懂数学归纳...

david010718

．．．．．．．．建议莫知我哀把此踢收录经典贴只中．

kidfake

v                        |--右--( 1轻)
                         |--右--(1 ; 2)|--平--( 5重)
                         |             |--左--(    )
                         |
                         |             |--右--( 2轻)
         |--右--(1,6-8;  |--平--(2 ; 3)|--平--( 4轻)
         |        5,9-11)|             |--左--( 3轻)
         |               |
         |               |             |--右--( 7重)
         |               |--左--(6 ; 7)|--平--( 8重)
         |                             |--左--( 6重)
         |
         |                             |--右--(10重)
         |               |--右--(9 ;10)|--平--(11重)
         |               |             |--左--( 9重)
         |               |
         |               |             |--右--(12重)
(1-4;5-8)|--平--(1-3;    |--平--(1 ;12)|--平--(13轻, 13重)*
         |          9-11)|             |--左--(12轻)
         |               |
         |               |             |--右--( 9轻)
         |               |--左--(9 ;10)|--平--(11轻)
         |                             |--左--(10轻)
         |
         |                             |--右--( 6轻)
         |               |--右--(6 ; 7)|--平--( 8轻)
         |               |             |--左--( 7轻)
         |               |
         |               |             |--右--( 3重)
         |--左--(1,6-8;  |--平--(2 ; 3)|--平--( 4重)
                  5,9-11)|             |--左--( 2重)
                         |
                         |             |--右--(    )
                         |--左--(1 ; 2)|--平--( 5轻)
                                       |--左--( 1重)
这个就是策略树,有兴趣可以看看<图论> or <离散数学>

呆瓜小贼

...看起来好象我们的方法不一样...
查查离散数学先...

曦儿

汗，偶怎么记得三次是三次，但什么离散数学一向8知道的说~~%&153

★工藤优作★

3次