|
本帖最后由 fungarwai 于 2014-12-28 13:13 编辑
田忌赛马
n匹马能取胜m次的方法数为a(n,m)
若前n匹马能取胜m次,第n+1匹马放在能取胜的m匹马上,或第n+1匹马放在原位:(m+1)a(n,m)
若前n匹马能取胜m-1次,第n+1匹马放在不能取胜的m-1匹马上:(n-m+1)a(n,m-1)
a(n+1,m)=(m+1)a(n,m)+(n-m+1)a(n,m-1)
将n个箱子编号为1,2,3,...,n,n个球编号为1,2,3,...,n,编号i的球只能放入编号1,2,3,...,i
n个箱子恰有m个空箱子的方法数为a(n,m)
n个箱子恰有m个空箱子时,第n+1个球放进m个空箱子的其中1个或者第n+1个箱子:(m+1)a(n,m)
n个箱子恰有m-1个空箱子时,第n+1个球放进n-(m-1)个非空箱子:(n−m+1)a(n,m−1)
a(n+1,m)=(m+1)a(n,m)+(n-m+1)a(n,m-1) |
本帖子中包含更多资源
您需要 登录 才可以下载或查看,没有帐号?注册
x
|