算法导论书上有个练习，让证明n个元素的第2个最小的元素可以用n + ceil(lg n) - 2次比较找出来，给的提示只是：把最小的也找出来。

我想了好久，终于出来了。思路是：n-1次比较找出最小，然后再用ceil(lg n)-1次比较就找到第2个最小。具体见这一页。

继续考虑Lottery问题的第三类（有序、可重复），一个同学根据下边的图列出了一个递归方程如下：

T(n, m) = \left\{ \begin{array}{ll} T(n - 1, m) + T(n, m - 1) & a \geq 2, b \geq 2\\ 1 & n = 1\\ n & m = 1 \end{array} \right.

设前n个自然数填充m个空，按照要求有T(n, m)种填充方法。图中只给出了n=3, m=3的情况，树的高度为m，从根到每一个叶节点的路径上的标号序列就是一种方法，所以叶节点的个数即为填充方法的个数。用蓝线将图分成两半，则可以发现，左边的子树与T(3, 2)相同，右边子树结构与T(2, 3)相同。可以想象对任意n>=2, m>=2这个式子都成立。

一行行列举T(n, m)的值（按每行m+n的值相等），就可以发现跟杨辉三角很相似。可以证明这个方程的解就是

C_{n+m-1}^m

不过，可不可以在不知道结果的情况下把它解出来呢？

前几天上Topcoder，第二个题（Lottery）就让我比较郁闷。

输入是一些彩票的描述，有名字、可选数字、空格数、是否有序、是否唯一这些项目，有多种彩票，以字符串数组类型输入，要求在输出中按照各种彩票的可能个数大小对这些彩票排序。给定可选数字n，空格数m，则问题就是在1, 2, … , n中选择m个来填空，并按照是否有序（非降序，如：1,2,2,3）、是否允许重复的限制来计算可能的答案数。

这其实就不算个算法题。首先就是要分析输入字符串，生成可以操作的问题对象（需要定义类），考察的是对语言运用的熟练程度。然后要根据问题限制求出排列数，考察的是对排列组合的掌握。最后是排序，如果用Java，实现一个Comparable接口，还是写一个实现了Comarator接口的类，随便了，不过前一个更方便。如果用C++，那么就写一个回调函数。这考察的又是语言。

可怜我就在排列组合那里出了问题。现在每次遇到数学问题的时候就没信心，总是觉得学得太差了，好像以前学过的东西都忘了。这个问题，如果不考虑是否有序的话还算简单，很容易想出来，但是考虑到有序，就不知道从何处下手了。

问了一下数学比较牛的xl，他马上给出了答案。

我问的是后两种情况，最后一种给出答案我就明白了，n个数里取出m个，按顺序就只有一种放法了。第三种情况，他说也是猜的，看来数学好，感觉也是对的。后来在Wikipedia上找到了解释，这是个很普通的问题吗？我没想到会很容易在上面找到该问题的解释，呵呵。那里已经给出了非常好的讲解，这里就不再赘述了。挺有意思的，自己凭空想，怎么也想不明白是怎么回事。