由0和1构成的虫子

有一条虫子,它的整个身体由 n 节构成,每一节要么是有瑕疵的 1 ,要么是没有瑕疵的 0 ,因而整个虫子的身体结构就可以用一个 n 位 01 串来表示。你的目标是把整个虫子变成 000...00 的完美形式。每一次,你可以砍掉虫子最右侧的一节,同时虫子会在最左侧长出新的一节,以保持虫子的总长度不变。如果你砍掉的是一个 1 ,那么你可以指定虫子在最左侧长出的是 1 还是 0 ;但如果你砍掉的是一个 0 ,那么你无法控制虫子会在最左侧长出什么——它可能会长出 0 ,也可能会长出 1 ,因而你不得不假定,概率总是会和你做对,上天会竭尽全力地阻挠你。我们的问题是:不管虫子的初始状态是什么,你总能保证在有限步之内让虫子变成 000...00 吗?
注意,这个问题可能没有你想的那么简单。显然,我们必须得把一些 1 变成 0 ,这样才能让 1 的数目逐渐减少并最终消失。但是,如果只是简单地每次都把 1 变成 0 ,最终也不见得就一定能取胜。比如,如果这条虫子是 101 ,那么去掉最右边的 1 并选择在左边长出一个 0 ,虫子会变成 010 ;再把 010 右边的 0 去掉后,如果不巧左边长出的是 1 ,那么整条虫子又会回到 101 的状态。如此反复,将永远也不能得到 000 。而更加聪明的方法则是先把 101 变成 110 ,下一步虫子将会变成 111 或者 011 ,不管是哪种情况,接下来只需要逐个把 1 变成 0 就能获胜了。运用恰当的策略才能走到终点,这无疑让问题变得更加有趣。
不管虫子一开始是什么样子的,我们总能够在有限步之内获胜。下面是 Peter Winkler 给出的证明。让我们把连续 n 次操作视为一轮操作,因而完成一轮操作正好让虫子的整个身体更新一次。于是,每一轮操作实际上相当于是从右到左依次考虑虫子的每一位,每遇到一个 1 时你都可以选择是否把它修改成 0 ,每遇到一个 0 时它都会随机地被修改成 1 。我们一轮一轮地改造虫子的身体,并且每一轮都采取这样的策略:从最右端开始,每次遇到 1 都把它改成 0 ,直到第一次有 0 被改成 1 ;在此之后,不管新遇到的 0 变没变,都保留所有的 1 不变。如果这一轮下来后,没有 0 被改成 1 ,那么我们将会把所有的 1 都替换成 0 ,从而得到 000...00 的形式,直接获得胜利;如果途中有 0 被改成了 1 ,那么整个虫子作为一个二进制数将会严格增加。每经过一轮后,只要虫子没有变成 000...00 ,整个二进制数都会变得更大,最终将会变成 111...11 的形式,此时再也不会有 0 变成 1 了,于是按照我们的策略,在下一轮中,所有的 1 都会变成 0 ,从而获得胜利。
上一条:在java 7中捕获多个异常
下一条:已经没有了
北大青鸟网上报名
北大青鸟招生简章