现在,我在心里想一个不超过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立体图,包括看对眼、立体眼镜、左右两幅图(一只眼睛看一个)等等。后来,网上出现了一种只需要一只眼睛就能体验的














