Original Ideas

2008 年 10 月 6 日 / 21 条评论

首先呢，小小的庆祝一下我的订阅数终于过千了。真可惜，昨天的订阅数1023，差一点就是1024了……
最近不知道为什么，思维特别活跃，脑子里经常蹦出一些牛B的想法。先声明，这篇文章为matrix67.com原创；谁要是用了里面的东西而没署名，或者拿去用作商业用途的话……Alan Shore的模样将会像幽灵一样缠绕着你，出现在你的每一个恶梦中。

关于输入法：为什么能打出“推倒”却打不出“推不倒”？

为什么没有输入法可以依据语法规则生成更多词组？例如，我可以把“睡觉”、“理发”、“洗澡”、“打球”、“吃饭”一类词做一个标记，那么在里面插入“了”、“过”等词也可以直接视为一个词（这些词同样很常用）。这样的话，词库容量大大扩充了，但这种方法本身并不耗费太多的空间和时间。
或者有输入法已经开始这么做了？大家的输入法中，这些词语可以直接打出来么？

睡觉睡了觉睡过觉睡个觉睡完觉睡不成觉
理发理了发理过发理个发理完发理不成发
洗澡洗了澡洗过澡洗个澡洗完澡洗不成澡
打球打了球打过球打个球打完球打不成球
吃饭吃了饭吃过饭吃个饭吃完饭吃不成饭

事实上，这种结构能够派生出来的短语比你想像的更多，如“睡一睡觉”、“睡不睡觉”、“睡了一小时的觉”、“睡不完的觉”、“你睡你的觉去”、“觉也不睡”、“觉不好好睡”、”觉已经睡过了“等等；同时，这一类词的数量也相当多，漱口刷牙洗脸穿衣服穿鞋拿钥匙锁门开车上班写程序玩游戏下班回家做饭洗衣服上床做爱全是这一类词。因此词类标记的价值显得更大了。
又如，结果补语中间可以插入“不”、“得”变成可能补语。奇怪的是，为什么绝大多数输入法里都有“推倒”这个词，却没有“推不倒”这个词？这明明是在词库里做几个标记就能办到的事情。

推倒推得倒推不倒
吃完吃得完吃不完
学会学得会学不会
长高长得高长不高
飞起来飞得起来飞不起来
走进去走得进去走不进去

趣题：用最少的块移动实现逆序操作

2008 年 10 月 4 日 / 14 条评论

上次那篇日志发布之后，据说大家解题的热情相当高。Michael Brand告诉我说，他收到了很多来自中国的邮件，他感到非常高兴。在揭晓谜底之前，还是让我们先回顾一下题目：

对数列的一次“块移动”是指把一段数取出来插入到数列中的另一个地方（说穿了就是一次选择剪切粘贴的操作）。例如，数列1,4,5,6,2,3,7可以通过一次块移动完成排序（把456挪到3后面）。那么，想要让一个1到n的逆序排列n, n-1, …, 3, 2, 1变为顺序排列，最少需要多少次块移动？给出你的算法，并证明这个移动数目不能再少了。

需要指出的是，答案并不是n-1那么简单。当n=5时，只需要三步就可以搞定了：

5  4 [3  2] 1
3  2  5 [4  1]
[3  4] 1  2  5
1  2  3  4  5

寻求真心话大冒险之猜数游戏的最佳策略

2008 年 9 月 30 日 / 14 条评论

去年的高中同学会上，吃完饭后大家就坐成一圈开始玩猜数游戏了。主持人自己在手机上输入一个1到，比如说500，的数，然后大家轮流猜数，并由主持人告之是猜大了还是猜小了。猜中了的那个人接受惩罚，真心话，或者大冒险，然后成为新的主持人。例如，我们班班长想了个数230。然后某男猜200，班长说“200到500”，意思就是200小了，以后的人只能猜200到500之间的数；接下来某女说“300”，美女班长说“200到300”；然后另一个MM猜250，班长回答“200到250”；然后就轮到我猜了，我说“230吧”，班长一脸坏笑把手机拿出来给大家看，说“哈哈，你猜中啦”。然后呢，我就和某个MM做了一件特别牛B的事情，细节呢就不在这里说了。
当天同学会结束后我赶回学校机房继续讲课。我提出了这么一个问题：如果我不想猜中的话，怎么决策最好？如果我想猜中的话，又该猜什么呢？这个博弈过程复杂就复杂在，这是由多个人参与的游戏，目的不是尽早猜中或者最晚猜中，最佳决策很可能既不是猜正中间也不是猜最大或最小；游戏是一圈一圈地循环进行，策略要视总人数和数字范围而定，并且很可能每个人居心各不相同。

用计算机自动作曲？Wolfram的手机铃声生成算法

2008 年 9 月 28 日 / 11 条评论

随着计算机科学的发展，越来越多的人开始思考，人工智能到底能强到什么地步？是否会有一天，我们可以完全通过计算机算法生成一部想象力丰富、情节跌宕起伏的科幻小说？“写作机器”或许离我们还有些遥远，不过用计算机来自动作曲已经有了一些像模像样的算法了。网友digiter分享了一个非常有意思的站点WolframTones，它是Wolfram的一个有趣的项目：用程序算法随机生成一段动听的音乐（用来当手机铃声）。随便点击一个Style，系统会自动生成一段音乐，而且每次生成的都不一样。程序的算法简单得简直让人不敢相信：随机生成一组初始编码（第一列），然后按照一些简单的“生命游戏低维版”式的规则不断迭代生成出余下列的编码，再将这些编码与各音高一一对应起来。难以置信的是，这样简单的算法居然能产生出如此和谐动听的旋律，科学与艺术奇迹般地结合在了一起。

趣题：尽可能用奇数次猜测完成猜数游戏

2008 年 9 月 28 日 / 5 条评论

现在，我在心里想一个不超过n的正整数t。你的任务是尽可能用奇数次猜测猜中这个数（你知道n是多少）。每次猜测后，我都会告诉你你所做的猜测是大了还是小了。你不能猜测已经被排除了的数（来消耗猜测次数），你的每次猜测都必须符合我原来给出的回答。你觉得，你获胜（奇数次猜中）的几率有多大？

动态规划的几个类似的经典模型启发了我们：设a[m]表示采取最优策略后在m个数里猜奇数次猜中的概率，b[m]表示如果题目要求我们猜偶数次，那最优策略下有m个数时获胜的概率是多少。考虑现在我有m个数可以猜，我想在奇数次内猜中。现在我猜的是数字i。狗屎运最好时，我一次猜中直接就赢了，它的概率是1/m；有(i-1)/m的情况下我会得到“大了”的提示，这样的话我需要用偶数次猜测去猜前面那i-1个数；剩余的那(m-i)/m的情况中，我需要用偶数次猜测去猜m-i个数。因此，a[m] = Max {1/m + (i-1)/m * b[i-1] + (m-i)/m * b[m-i], 1≤i≤m} 。类似地，我们也可以得出b[m]的递推公式：b[m] = Max {(i-1)/m * a[i-1] + (m-i)/m * a[m-i], 1≤i≤m} 。
学习使用Mathematica确实是一件好事，你可以用Mathematica非常方便地描述出我们上面的两个递推公式，不需要自己去写那些冗长的程序了。
a[m_] := Max[Table[1/m + (i-1)/m * b[i-1] + (m-i)/m * b[m-i], {i, m}]]; a[0] := 0; b[m_] := Max[Table[(i-1)/m * a[i-1] + (m-i)/m * a[m-i], {i, m}]]; b[0] := 0;