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

查看更多 »

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

    现在，我在心里想一个不超过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;

查看更多 »

    想当年搞竞赛那会儿，我真是读了不少书，收获相当大。进大学后渐渐地淡出了竞赛的世界，于是开始看各种类型的数学书。Pólya的几本牛书陪伴我熬过了无聊的古代汉语课和现代文学史课，每个星期消化一点《什么是数学》已经成了一种习惯。最近笔记本的电池越来越不能扛了，熄灯后最多挺一个半小时。那要是笔记本没电了我该干啥呢？于是在网上买了个平板阅读灯，等寝室的人都睡了之后安安静静地伏在床上看书、思考。想看的书真是多啊……偏偏我看书又慢。正在看《苏菲的世界》，《三体II》还没看，昨天又买了一大堆书……真希望我能有更多的时间来看书。

Sofies verden / Sophie's World / 苏菲的世界
    这是一本异常奇特的小说，也是一本绝佳的哲学史入门读物。最早我是在Wikipedia的self reference词条下知道这本书的，因为这本小说中的主人公最终发现自己是一本小说中的主人公。现在正在看这本书，马上要看完了。我看书是出了名的慢，断断续续地看了一个假期都还没看完。

Kabalmysteriet / The Solitaire Mystery / 纸牌的秘密
    和Stetson MM聊得最火热的那段时间里，我曾经提到过我要看《苏菲的世界》。Stetson MM告诉我说，《苏菲的世界》她没看过，但是同一作者的另一本书《纸牌的秘密》她看过的，并且她非常强烈地向我推荐这本书。前几天看到她校内上的日志还引用了《纸牌的秘密》里面的话。

The Cat Who Walks Through Walls / 穿墙猫
    科幻大师Robert A. Heinlein的一部科幻小说。我是相当喜欢Heinlein的了，《你们这些还魂尸》是我见过的最牛B的时间悖论题材的科幻小说。The Cat Who Walks Through Walls也是我在Wikipedia的self reference词条下看到的，它上面介绍说，这本书considers the universe as an author-manipulated object including the plot in the book itself，想必应该会相当有趣吧。目前这本书好像没有中译。

One Two Three... Infinity / 从一到无穷大
The Emperor's New Mind / 皇帝新脑
    这两本书是相当经典的了，我居然还没读过-_-b
    刚刚把这两本书买了，看完苏菲就看它们俩。

查看更多 »

    在所有8-bit的整数中，含有k个数字“1”的二进制数一共有C(8,k)个。给出其中的一个二进制数，你如何利用位运算快速找到下一个恰有k个“1”的数？例如，如果给你二进制数01011100，那么下一个（含4个“1”的）数就是01100011。在继续阅读下去之前，建议你仔细思考一下。你或许会想看看我很早以前写的一篇介绍位运算的文章。这是一道很好的题目，很多位运算技巧在这里都有体现。

    在草稿纸上随便举几个例子，规律很容易看出来。由于“1”的个数是固定的，为了让这个二进制数更大，我们必须把第一个出现在“1”左边的“0”改成“1”；同时，为了让这个二进制数尽可能小，我们必须把它右边那些“1”重新排到最低位去。
    更具体地说，下一个二进制数可以通过以下步骤得到：找到右起第一个单个的或连续的数字“1”，把它们全改成“0”，同时把它们左边的那个“0”改为“1”。此时，“1”的个数可能减少了，我们只需把还差的“1”摆在最右边就行了。举个例子，01011100的右起第一个“1”在第三位，把它和左边紧挨着的“1”一并变为“0”，并把再左边那个“0”变为“1”，于是我们得到01100000。我们还差两个“1”，把这两个“1”补在最低位得到01100011即可。现在我们的任务是，想出一个用位运算来实现这些步骤的办法。
    我们已经熟知，用x & -x可以提取最右边的那个“1”。当意识到可以利用加法来消除连续的“1”时，我们很快得到了第一步操作的位运算实现：把x & -x加到x上，利用二进制加法的进位把“..01111..”变成“..10000..”。现在，我们需要计算出刚才的操作中一共“跳过”了多少个“1”，换句话说现在的x的右起第一个“1”和原来的x的右起第一个“1”差了多少位。关键就在这里！我们可以用除法来完成这一步，例如100000除以100就相当于把被除数右移2位，得到的结果即可以表示两个数中的“1”差了多少位。在最低位产生指定数量的“1”需要用到另一个技巧：减1操作可以把右边连续的“0”都变成“1”，即把...10000变成...01111。我们得到了该问题的第一个算法：

b = x & -x;
t = x + b;
c = t & -t;
m = (c/b >> 1) - 1;
r = t | m; //最终结果

    我们对上述算法做一个简单的说明：

操作              | 样例     |  说明
------------------+----------+----------------------------
x                 | 01011100 |  原数
b = x & -x        | 00000100 |  提取x的右起第一个“1”
t = x + b         | 01100000 |  把x的右起第一个位于某个“1”左边的“0”变成“1”，并把它右边的那些“1”都变为“0”
c = t & -t        | 00100000 |  提取t的右起第一个“1”
c / b             | 00001000 |  右移c中的那个“1”，其结果中最低位连续的“0”的个数正好是c和b中的“1”相差的距离
m = (c/b >> 1) - 1| 00000011 |  在最低位产生数字“1”，其个数比上述的“距离”少1
r = t | m         | 01100011 |  最终结果

    除去赋值，我们一共用了9个运算符。有可能用更少的运算么？

查看更多 »

Stetson MM给我推荐的一个Flash小游戏。挺适合给完全没有学过编程的人了解一下什么是“程序设计”。
给个链接：http://armorgames.com/play/2205/light-bot

查看更多 »

    有时候，这个网站会带给人一种难以察觉的忧伤：一个找不到MM的Geek在阴暗的寝室一角用一台用了两年多的R51e努力地更新着一个从不做广告在外面打广告、从不做关键字、连网页标题都没SEO过的个人Blog。最近想写的科学东西很多，但我一直忙着在做系里的图书馆分馆的网站；写日志的时间越来越少，很多相当有趣的问题及其精妙的解答过程被我写得越来越简略，以致于有人告诉我说最近写的很多东西都看不懂，这让我很是苦恼。说实话，20号早晨起来发现我的网站遭遇了三个力量无比强大的字母时，我第一次产生了放弃更新这个写了三年多的Blog把所有文章打个包放出来下载然后完美收场的念头。当然我知道这是做不到的，估计过不了多久我又会在什么地方再开一个Blog从零开始继续更新，因为我永远是一个找不到MM的Geek。后来网上一查，知道了在DreamHost上的网站被封是一个很常见的现象，心里顿时感觉平衡了不少。DreamHost上的垃圾网站太多，我多半又是被同一IP下的某个提供日韩生活大片的网站害了。在这里严重感谢dd牛把独立IP给了我，让我能够继续维护这个网站。小小的发一下牢骚，别的也不说什么了，一切都还和原来一样……我睡觉了，各位晚安~~

    有这么一个无自环的有向图，它的顶点数在30和40之间（包括30和40）。对于图里面的任意两个点A和B，要么存在一条有向边A->B，要么存在唯一的一个“中间点”C使得A可以通过A->C->B两步走到B。换句话说，对任意给定的A、B两点，从A到B的长度不超过2的路径有且仅有一条。注意，即使当A=B时，这个条件也是成立的。试问这个图有多少个顶点。

 
查看更多 »