IBM Ponder This上个月的题目比较有趣：我在心里面想一个2到166之间的整数（包括2和166），你的任务是用尽可能少的是非问句（我只能回答是或者否）猜出这个数除1以外的最小约数是多少。
    (1) 寻找一种策略使得在最坏情况下猜到答案的询问次数最少。
    (2) 寻找一种策略使得在平均情况下猜到答案的期望询问次数最少。

    第一个问题很容易回答。虽然2到166之间的整数一共有165个，但它们的最小约数（以后我们说的“最小约数”都是指的不包括1的最小约数）只有38种。因此，事实上你只需要用二分法在38个可能的答案当中找出一个就可以了。由于2^5=32，2^6=64，因此最坏情况下需要6次询问才能保证猜到。
    真正困难的是后面一个问题：要想让平均猜测次数尽可能少，我们该从哪里入手呢？

查看更多 »

    今天学到了一个新的名词，Runge现象。1901年，Carl David Tolmé Runge意外地发现，用差值插值多项式逼近函数f(x)=1/(1+25x^2)时出现了一些反常的现象。如图，灰色的粗线就是Runge函数在[-1,1]上的图象。蓝色虚线是过[-1,1]上的6个等距点所得到的5次多项式，红色虚线是过[-1,1]上的10个等距点所得到的9次多项式。可以看到，当次数变高时，插值多项式反而变得更不准确。

查看更多 »

在网上偶然看到这篇文章，决定把之前创作排序算法内存状态演示图所用的Mathematica程序修改一下，于是搞出来5个midi音乐。这些midi文件用音高来表示内存状态，初始时的音都是乱的，然后声音渐渐变得有序，最后就成了从低到高的一串音符。

http://www.matrix67.com/data/bubble_8_elements.mid
http://www.matrix67.com/data/insert_8_elements.mid
http://www.matrix67.com/data/select_8_elements.mid
http://www.matrix67.com/data/quick_12_elements.mid
http://www.matrix67.com/data/bogo_6_elements.mid

哪位兄弟能推荐一个在线放midi文件的好方法？

    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

查看更多 »

    上次我们谈到，我们考虑时间复杂度时往往假设任意大的整数运算（赋值、四则运算、取余运算、比较运算、位运算包括左移右移）都可以在常数时间内完成，殊不知这留下了一个非常具有研究价值的漏洞：能否利用计算机理想模型中的整数运算，把问题打包成超大整数后并行计算，从而办到一些在普通计算机上无法办到的事情？我们在上一次的文章中介绍了利用“大整数随便算”的漏洞“耍赖”得到了一个线性时间的排序算法。这个漏洞真的已经被充分利用了吗？我们还能从里面榨出多少汁水来？令人无法想象的是，线性时间的排序算法远远没有挖掘到理想大整数运算的巨大潜力，事实上我们能做到常数时间的排序！问题和解答仍然来自Using your Head is Permitted，在这里向Michael Brand表示深深的膜拜。
    自然，说“常数时间排序”是有前提条件的，否则即使读入输出也得耗费线性的时间。不过，我们可以假设所有待排序的数都已经打包进一个大整数里，输出时也无需解包，直接返回另一个大整数即可。在这样的情况下，我们完全可以用常数时间完成排序。换句话说，我可以用O(1)的时间，“一下子”就把0100 0111 0001 0010变成0001 0010 0100 0111，不管这个大整数里面装了多少个数。为了方便大家阅读和思考，我们再取一些名字，方便描述。我们把由多个数构成的大整数叫做“整数串”。整数串中所含的数都是二进制，它们用空格隔开。整数串中每个数的位数都必须相等，位数不够用零补足。我们把这个位数叫做“定宽”，本文例子的定宽都是4。

查看更多 »

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

查看更多 »

    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动画来，虽然这样将很难观察出细节，但对总体的把握效果将更好。