Susan的新天地

引用自大眼佳佳 （废话一句，现在的msn space做得不错么，引用其他人的文章这么容易）

当computer scientist遇到computer scientist

夜深人静,说一个两个computer scientist date的故事.

古时候,有两个computer scientist,本来想学别人花前月下,甜言蜜语的搞个浪漫约会.

但是在geek细胞的作用下,甜蜜了还没几分钟就开始无聊了.毕竟骨子里面,爹妈没给什么浪漫细胞啊.

于是在穷极无聊之余开始想东西玩,可手边只有一副扑克牌,所有玩起了24点.(两人中还有一"弱智"是生平第一次玩24点.)

玩不到两轮,继而发展为讨论如何用算法解决这个问题.

/********************算法如下(非CS的人请跳过)**********************/

1.以四个数字为leaf,运算符为中间节点建树.每一棵树代表一种计算的可能性.

2.固定四个数字的顺序,但是改变树的结构.比如说可以是两两组合然后再组合,也可以是两两组合再跟一个组合再跟剩下的组合.这样的话,有可能有n种情况.我现在觉得 n=3,但是记得某人说是5种.想不起来是为什么的啦.

3.作为中间节点的运算符可以是:+,-,*,/,中间的任何一种.但是因为leaf node的顺序是不可变的,所以除了常规的-,也就是-符号的左子树减右子树以外,还要定义一种是右子树减左子树的-.同样,/也要引入相应的新运算符.所以中间节点可以是6种运算符.这样的话,给定一个树的结构,可以有m种变化.我现在脑子不是太清醒,感觉m=6^3.

4.所以,给定4个数字也是4张牌,一共可以有mxn种可能.穷举一下,算其中有没有结果是24的就行了.

显然应该有优化的算法,不过这两个computer scientist看能在polynomial内解决也就懒得优化了.

/*********************算法完(非CS的人请继续看)**********************/

结论就是CS的人date之余不忘research.感觉好好想想这个算法,都有发paper的可能了.

还有,CS的人还是不要date自己人.感觉date自己人跟date电脑感觉没差.现在电脑不是也会算24点么.而且,跟电脑date的时候还能顺便把以上算法实现一下,验证一下对不对.