ntsd杀进程
google的blog搜索2007/01/05 11:26
文章作者：9Enjoy 转载请注明原文链接。
同事发给我一首题，一看晕了，Ｎ年没做这种题目了。
ＳＥ一下，搜索出这篇来了：http://community.csdn.net/Expert/topic/5241/5241662.xml?temp=.2350122，讨论的人还真多。拉到中间，发现welshem(天堂客) 回答的有理：
引用
楼上大哥又发了一帖啊,我来说说我的思路吧:
1、最后一个人我想只能是赌命的，但他的信息能不能给其他人帮助？如果行，那就是只会死一个。
2、黑白让我想起1、0，想对于最后一个，倒数第二个少看到的就是自己的那顶要命的帽子，也就是少了个1/0
3、由于不能报自己看到了多少个1、0所以只能把这此数并起来
4、0 就不管了，就计1，报奇偶（实际上就是所见0、1之和的最低位啦）
那好，方法有了
1、最后一个人如果看到奇数顶帽子报“黑”否则报“白”，他可能死
2、其他人记住这个值（实际是黑帽奇偶数），在此之后当再听到黑时，取反一次
3、从倒数第二人开始，就有两个信息：记住的值与看到的值，相同报“白”，不同报“黑”
99人能100%活，1人50%能活
现在最重要的是选最后一个人了，他是50%死的可能的，必须有奉献精神的啊！
接着往下拉，又看到了welshem的高论：
引用
WYlslrt(WY.lslrt http://www.wyos.net ) :
1、最后一个人如果看到奇数顶帽子报“黑”否则报“白”，他可能死
2、其他人记住这个值（实际是黑帽奇偶数），在此之后当再听到黑时，取反一次
3、从倒数第二人开始，就有两个信息：记住的值与看到的值，相同报“白”，不同报“黑”
这是算法
按你的情况：
未开始
位置：6 5 4 3 2 1
状态：0 0 1 1 0 0
可见：0 0 1 0 0 0
信息：无
第一人说白(0)（赌）
位置：6 5 4 3 2 1
状态：0 0 1 1 0 0
可见：0 0 1 0 0 0
信息： 0 0 0 0 0
死活：活
第二人说白(0)（同）
位置：6 5 4 3 2 1
状态：0 0 1 1 0 0
可见：0 0 1 0 0 0
信息： 0 0 0 0
死活：活 活
第三人说黑(1)（不同）
位置：6 5 4 3 2 1
状态：0 0 1 1 0 0
可见：0 0 1 0 0 0
信息： 1 1 1（取反)
死活：活 活 活
第四人说黑(1)（不同）
位置：6 5 4 3 2 1
状态：0 0 1 1 0 0
可见：0 0 1 0 0 0
信息： 0 0（取反)
死活：活 活 活 活
第五人说白(0)（同）
位置：6 5 4 3 2 1
状态：0 0 1 1 0 0
可见：0 0 1 0 0 0
信息： 0
死活：活 活 活 活 活
第六人说白(0)（同）
位置：6 5 4 3 2 1
状态：0 0 1 1 0 0
可见：0 0 1 0 0 0
信息：
死活：活 活 活 活 活 活
更有人写了php来推论，
原文：http://hi.baidu.com/rainchen/blog/item/cc5f5c608b6129df8cb10d5c.html
引用
根据其说法用PHP实现的简单模拟演算代码为：
$count = 100;
$man = array();
$black = array_fill(0, $count, 1);
$white = array_fill(0, $count, 0);
$manInBlack = 0;
$manInWhite = 0;
for($i=1;$i<=$count;$i++)
{
if(rand(0,1))
{
$man[$i] = array_pop($black);
$manInBlack++;
}
else
{
$man[$i] = array_pop($white);
$manInWhite++;
}
}
function getFrontBlackCount($queue, $me)
{
$count = 0;
for($i=$me-1; $i>=1; $i--)
{
if($queue[$i])
{
$count++;
}
}
return $count;
}
echo "manInBlack:$manInBlack, manInWhite:$manInWhite \n";
// start
$flag = 0;
for($i=$count;$i>=1;$i--)
{
$FrontBlackCount = getFrontBlackCount($man, $i);
$guess = ($FrontBlackCount%2) ^ $flag;
if($guess)
{
$flag = (int)!$flag;
}
if($guess == $man[$i])
{
$result = 'alive';
}
else
{
$result = 'die';
}
echo "man $i ,his hat is {$man[$i]} , FrontBlackCount=$FrontBlackCount ,newflag=$flag, he guess: $guess, so he will $result \n";
}
