组合数学练习2

aqua0 2010-05-06

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

(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的一些解题步骤吧。写会程序咯!

相关推荐