Mathematica 提供了一个看上去毫无用途的无厘头函数 Rasterize ，它可以以图片的格式输出运算结果。比如，下面这个句子可以打印出 (x+1)^n 的展开式的“倒影”：

    今天我突然想到，我们可以利用这个函数很方便地分析汉字在图象上的性质。函数 Binarize 可以把图象转换为单色单通道， ImageData 则可以把图象转换成数组的形式，以便我们定量分析。因此，下面这句话就可以把一个汉字转换成 12*12 的 01 矩阵：

查看更多 »

刚才在这里看到了如题所说的图像，立即想到用 Mathematica 验证一下。我选出了几个个人比较感兴趣的 k ，再用一句话便可输出所有对应 k 的图像：

kArray = {2, 3, 4, 6, 8, 10, 12, 14, 16, 18, 20, 36, 50};
For[i = 1, i <= Length[kArray], i++,
 Export["F:\\" <> ToString[kArray[[i]]] <> ".png",
  ArrayPlot[Table[Boole[Length[Divisors[x*y]] == kArray[[i]]], {x, 1, 400}, {y, 1, 400}],
   PixelConstrained -> {1, 1}, Frame -> False]]];

 
当 k=2 时，由于只有素数才有两个约数，因此所有点都是形如 (p, 1) 或者 (1, p) 的点，其中 p 为某个素数：

查看更多 »

    2009年2月份IBM Ponder This的谜题可能是从98年谜题月赛开办以来最难的谜题。谜题发布一个月之后仍然没有任何人答对，主办人不得不宣布延迟一个月，并再三增加提示。最终，答对此题的仍然只有7个人。很久没有看到如此精彩的谜题了，有兴趣的网友不妨试一试。
    题目非常有趣。传统的谜题是给出谜面求解谜底，但这个谜题则恰恰相反：下面这一串数字是某个问题的答案，你能猜出这个问题是什么吗？这串数字里有一个错误在哪里？

900F 80F0 8F00 80CA BE12 AA90 9400 0048 3E5B 8AC0
3400 00CB BC81 8A08 3C00 0050 BE43 00C0 3E00 A019
8059 BE13 2000 0092 BE9B 2A0B 2A00 8052 8841 04C0
3E00 840B 084B 0098 E000 8819 845A 8012 0300 0050
826F 0500 0600 846E 8264 0900 0A00 8065 0C00 0072
A054 8368 8569 4800 4400 8573 4200 4100 8349 8542
2800 2400 854D 2200 2100 9F00 E000 8888 8444 8000
0030 0DED 8222 0050 0060 8444 8222 0090 00A0 8000
00C0 0DED A000 8333 8555 4080 4040 8555 4020 4010
8333 8555 2080 2040 8555 2020 2010 8300 8500 8030
8050 0880 0840 8050 0820 0810 8030 8050 0480 0440
8050 0420 0410 8500 8030 8050 0280 0240 8050 0220
0210 8030 8050 0180 0140 8050 0120 0110 90F0 9F00
E000 8888 8444 8000 0003 0DED 8222 0005 0006 8444
8222 0009 000A 8000 000C 0DED A000 8333 8555 4008
4004 8555 4002 4001 8333 8555 2008 2004 8555 2002
2001 8300 8500 8003 8005 0808 0804 8005 0802 0801
8003 8005 0408 0404 8005 0402 0401 8500 8003 8005
0208 0204 8005 0202 0201 8003 8005 0108 0104 8005
0102 0101 9F00 8030 8050 8003 8005 0088 0084 8005
0082 0081 8003 8005 0048 0044 8005 0042 0041 8050
8003 8005 0028 0024 8005 0022 0021 8003 8005 0018
0014 8005 0012 0011 80FF 8F0F A333 8000 5000 0DED
8000 3000 0DED A333 C555 1800 1400 C555 1200 1100
8F0F A333 A555 1080 1040 A555 1020 1010 A333 A555
1008 1004 A555 1002 1001

查看更多 »

    创意C/C++编程挑战赛Time Limit Exceeded结束，题目果然非常有创意。大家可以在这里看到比赛题目和获胜选手的代码。其中两道题很有意思，我特别喜欢。

    一道叫做Compile Error的题目要求你写一个叫做multiply的类，里面包含一个mult(int a,int b)的函数，该函数用于打印出a和b的乘积。代码中不允许出现空格、“/”和“#define”。

    第一个问题就是，定义一个类的语句是class multiply{...}，这个空格要怎么避免？只要你知道typedef int foo也可以写成int typedef foo，我们就可以利用typedef来消除空格，把类的定义写成class{...}typedef multiply。但这下后面又冒出一个空格来，这个空格怎么消呢？一个巧妙的方法就是利用int typedef foo,bar的语句，把类定义语句写成class{...}typedef*foo,multiply，其中*foo是一个不会用到的类型，但是它帮助我们奇迹般地消除了一个空格。巧妙利用星号可以消除很多空格，例如我们在定义mult函数时就可以写成void*mult(...){...}。最后一个难题就是，定义函数mult(int a,int b)，参数表里面的两个空格怎么办？其实办法依然很多。不少网友都用到了typeof，这样便可以把int a写成typeof(int)a了。完整的类定义如下：

class{public:void*mult(typeof(int)a,typeof(int)b){cout<<a*b<<endl;return(0);}}typedef*m,multiply;

    在gcc下，即使警告全开，下面这个程序编译时也一声不吱。

#include <iostream>
using namespace std;
 
class{public:void*mult(typeof(int)a,typeof(int)b){cout<<a*b<<endl;return(0);}}typedef*m,multiply;
 
int main()
{
    multiply foo;
    foo.mult(23,67);
}

查看更多 »

    上次提到，我非常关注一个即将举办的另类编程挑战赛Time Limit Exceeded，这个比赛的得分算法很另类，它将根据你代码的总长度和特定字符的多少而定。在刚刚结束的测试赛中，有几个题目非常具有挑战性，参赛者提交的代码也是牛气冲天。

 
Power of 2
问题：
    输入数据含有多行，每行一个正整数。对每个数，检查看它是否是2的幂，是则输出yes，不是则输出no。
    你的程序不允许使用分号。
    规定0也是2的幂。

得分：
    S= length of code + number of whitespaces;
    score = (250000)/(S^2);

查看更多 »

刚过完年回到家，也跟大家说一声新年快乐。
今天莫名其妙地收到一封邮件，邀请我参加felicity.iiit.ac.in举办的几个编程比赛。我看了一下介绍，这些比赛还是挺有意思的，这里向大家推荐一下。

http://felicity.iiit.ac.in/codecraft/
CodeCraft，举办了两三年了，一个传统方式的编程比赛。
测试赛：14th Feb, 6pm - 8pm IST (GMT +5:30).
正式比赛：15th Feb, 2pm - 10pm IST (GMT +5:30).

http://felicity.iiit.ac.in/~math/
MathematiKa，已经举办过一年了，这是第二年的比赛。比赛共12道数学题，你只需要提交答案即可。例如，去年的第四题叫你计算前30个正整数x使得F(x) = 5x^2 + 14x + 1是一个完全平方数。提交时，把所有30个数从小到大连接在一起即可。最大的那个x有十几位，因此这题硬算是不行的。
测试赛：12th Feb, 6pm - 9pm IST (GMT +5:30).
正式比赛：13th Feb, 2pm - 10pm IST (GMT +5:30)

查看更多 »

    当我们研究复杂度时，我们往往会将现实机器进行理想化。例如，我们说冒泡排序是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发布的答案后，我一拍大腿，哎呀，还有一个如此简单巧妙的算法我没想到！相比之下，我的算法太复杂了，原因就在于我还没有充分挖掘到“大整数的常数级运算”的潜力。这个理想模型的假设太强大了。打开思路，放宽思维，大胆想象，从更大的尺度上来思考，我们可以得到一个简单得出奇的线性排序算法来。

查看更多 »