当我们研究复杂度时，我们往往会将现实机器进行理想化。例如，我们说冒泡排序是O(n^2)的，这其实是不准确的。这个论断假设整数之间的比较运算是O(1)的，而事实上它们是O(log(min(|a|,|b|)))的。多数时候我们都认为这种机器模型的理想化是合理的，毕竟这让问题简化了不少，并且也能反映出算法的本质。但大家有想过吗，这个“大整数随便算”的假设其实是一个超级大漏洞，我们可以利用理想模型中的这一漏洞来作弊，获得时间复杂度更低的算法。上个月，Michael Brand在他的UyHiP里就提出了这样一个问题：假设计算机对任意大整数的赋值、四则运算、取余运算、比较运算、位运算（包括左移右移）的复杂度都是常数级别，你能否设计出一个O(n)的排序算法来？

    我非常喜欢这个题目。月初的时候我就提交了一个正确的算法。我们将用左移和加法运算把整数序列编码成一个超大整数，然后利用排序网络进行并行排序。这个算法比较复杂，你可以按照下面的思路一步一步得到这个算法。

1. 如何用位运算来取绝对值？

2. 给出两个正整数a, b，不用比较运算和判断语句如何把小数赋给a，大数赋给b？
    提示：和加差除以2等于大数，和减差除以2等于小数

3. 如何利用位运算把整数序列编码成一个超大整数？
    例如把（二进制数）11, 1011, 1110, 1编码为一个数00011 01011 01110 00001

4. 如何用位运算给超大整数中的所有数同时取绝对值？

5. 给出两个超大整数a, b，不用比较运算和判断语句如何把对应位置上的小数赋给a的对应位置，大数赋给b的对应位置？ 例如把
      a = 000010 000111 000100 001001
      b = 000001 001011 000011 011111
    变成
      a = 000001 000111 000011 001001
      b = 000010 001011 000100 011111

6. 如何实现奇偶移项排序？

    最后，由于奇偶移项排序只有O(n)层，因此整个算法是O(n)的。

    但是，这个算法太繁琐了，不具有美观性。虽然这个算法是我自己想出来的，但我仍然很不满意。待我看了这个月Michael Brand发布的答案后，我一拍大腿，哎呀，还有一个如此简单巧妙的算法我没想到！相比之下，我的算法太复杂了，原因就在于我还没有充分挖掘到“大整数的常数级运算”的潜力。这个理想模型的假设太强大了。打开思路，放宽思维，大胆想象，从更大的尺度上来思考，我们可以得到一个简单得出奇的线性排序算法来。

查看更多 »

    我们之前已经见过了正则表达式的一些很特殊的用法。这里我们再来看一个：用正则表达式判断数的整除性。例如，下面这个表达式可以匹配01串S当且仅当S是一个可以被3整除的二进制数。

^1((10*1)|(01*0))*10*$

    如果你不信的话，不妨把下面这段代码粘贴进浏览器的地址栏，然后回车运行一下：

javascript:alert(/^1((10*1)|(01*0))*10*$/.test("1000000100"))

    被test的是516的二进制表达。516可以被3整除，因此程序返回true。你可以自己把1000000100换成其它的二进制数试试。
    但是呢，从这个正则表达式里我们竟看不出任何端倪。奇怪了，为什么这个正则表达式可以用于判断整除性？能被3整除的二进制数究竟有何规律？

查看更多 »

  网友Mingliang Zhu在TopLanguage上发起提问。

  设想这样一个计算机系统，它只支持以下几个操作：
    1. 定义变量、给变量赋值；
    2. 变量自身加一；
    3. 令一段语句循环执行指定的次数。
  这个系统只处理且只能处理0和正整数。系统不存在“溢出”的问题。
  注意这个系统没有比较运算，事实上它甚至不存在Boolean值和判断语句。
  循环语句也不是FOR i=a TO b DO的形式，只能是LOOP n的形式。

  在这个系统上实现加法很容易，让a自增b次即可。现在的问题是，你能在这个系统上实现减法吗？

查看更多 »

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

查看更多 »

    在所有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个运算符。有可能用更少的运算么？

查看更多 »

    Daisuke Minematsu和他的同学们发现，Josephus问题中也隐藏着分形图形。Josephus问题是初学编程的人必然会接触到的一个问题——n个人围成一圈进行1到k报数，每次报到k的人退出游戏（离开这个圆圈），那么最后剩下的那个人是谁。在这里，我们考虑一个Josephus问题的变种：双向Josephus问题。双向Josephus问题中有两个交替进行的报数进程，其中一个按顺时针方向踢出每第k个人，另一个进程则逆时针踢出每第k个人。两个进程交替进行，直到最后只剩一人为止。假如n=10, k=3的话，第一个退出的人是#3，第二个退出的人是#8，第三个退出的人是#6，以后分别是4, 10, 9, 5, 1, 7，最后剩下的人是2。我们用S(n,k)来表示在相应的n值和k值的情况下最后剩下的那个人的编号，对于每个固定的k值，函数S的图象竟然都是一个分形图形。右图是S(n,4)所对应的图象，你可以非常清楚地看到这个图象的自相似性。你可以自己用Mathematica来验证一下。

查看更多 »

    我的左眼有相当严重的散光，因此无缘各种类型的3D立体图，包括看对眼、立体眼镜、左右两幅图（一只眼睛看一个）等等。后来，网上出现了一种只需要一只眼睛就能体验的3D图，原理非常简单，效果也比较震撼。只需要在两个眼睛的位置分别拍照，然后做成gif循环显示两个图片，大脑也可以从中迅速获取信息分辨出第三维来。闲逛ffffound时偶然发现这个图，突然想到：同样的方法为何不用于展示三维数据呢？于是试着用Mathematica做了一个。Mathematica输出gif动画相当简单，只需要一句Export["file.gif",{g1, g2, ...}]就行了。在这里，我们将用三维空间的点来展示组合数的各位数字之和的分布情况。可以看到，使用3D动画的效果非常明显。

img = ListPointPlot3D[
  Table[Total[IntegerDigits[Binomial[i, j]]], {i, 0, 50}, {j, 0, 50}],
   ViewVertical -> {0, 0, 1}, ImageSize -> 600];
Export["F:\\file.gif", {Show[img, ViewVector -> {-32, -20, 60}],
  Show[img, ViewVector -> {-31, -21, 60}]}];

    类似地，我们还可以做出环视一周的gif动画来，虽然这样将很难观察出细节，但对总体的把握效果将更好。

    只有想不到，没有做不到。还是在这里，我惊奇地发现Mathematica居然有DictionaryLookup和WordData这样的函数（我的6.0里就有，不知道5.x有没有）。于是，一连串牛B的Mathematica用法出现了：

 
包含ijk三个连续字母的单词：
In[1]:= DictionaryLookup["*" ~~ "ijk" ~~ "*"]
Out[1]= {"Dijkstra"}

 
连续三次出现重复字母的单词：
In[2]:= DictionaryLookup[RegularExpression[".*(.)\1(.)\2(.)\3.*"]]
Out[2]= {"bookkeeper", "bookkeepers", "bookkeeping"}

 
首尾三个（及以上）的字母完全相同的单词：
In[3]:= DictionaryLookup[RegularExpression["([a-z]{3,})[a-z]*\1"]]
Out[3]= {"abracadabra", "anticoagulant", "antidepressant", \
"antioxidant", "antiperspirant", "bedaubed", "beriberi", "bonbon", \
"cancan", "chichi", "couscous", "dumdum", "entailment", \
"entanglement", "entertainment", "enthrallment", "enthronement", \
"enticement", "entitlement", "entombment", "entrainment", \
"entrancement", "entrapment", "entrenchment", "froufrou", "hotshot", \
"hotshots", "ingesting", "ingoing", "ingraining", "ingratiating", \
"ingrowing", "ionization", "mesdames", "microcosmic", "murmur", \
"muumuu", "outshout", "outshouts", "physiography", "pompom", \
"redelivered", "rediscovered", "respires", "restores", \
"restructures", "tartar", "tessellates", "testates", "testes", \
"tormentor", "tsetse", "underfund", "underground"}

查看更多 »