组合数学练习2

下个礼拜就要考组合最佳化了，现在在努力复习中，真是比较难的科目，做了一晚上也没做几道习题。

（1）是汉诺塔的问题，根据汉诺塔的问题写出递推函数式，并写出过程。

1>当只有一个盘子的时候，不用想，1次就能够搞定整个过程。

2>当有两个盘子的时候，这个时候需要有辅助的盘子了，首先将上面的那个盘子移动到C，然后将最底下的盘子移动到B，再将C盘中的移动到B，总共3次移动。

3>当有三个盘子的时候，我们可以拿上面的结论来考虑，首先先将上面的两个盘子弄好，则需要3次的移动，然后将最底下的盘子移动到B需要一次，然后2个盘子移动到B还是需要3次。即2*（2个盘子的情况）+1

4>所以an=2*an-1+1(n-1是下标表示)。

5>根据方程可以得到an=2的n次方-1

（2）an,k(n,k都代表的是下标)，表达的是从n个可以区分的物体中选择k个作为子集合，找到合适的递推方程来表达an,k

an,k是的C(n,k)的问题，可以将问题分成两个方面，一个是第一个物体选择了，另外一个是第一个物体没有选择，an-1,k表示的是第一个物体没有被选中，an-1,k-1表示第一个物体被选中了，所以an,k=an-1,k+an-1,k-1初始的条件是an,0=an,n=1(n>=0)

明天继续做题咯，可能会分享下SA的一些解题步骤吧。写会程序咯！