sijing

递推的方法推导错排算法

                            递推的方法推导错排算法:  
                                          当n个编号元素放在n个编号位置,元素编号与位置编号各不对应的方法数用M(n)表示,
                                          那么M(n-1)就表示n-1个编号元素放在n-1个编号位置,各不对应的方法数,其它类推.  
                     第一步:把第n个元素放在一个位置,比如位置k,一共有n-1种方法;  
                     第二步:放编号为k的元素,这时有两种情况.
                                                   ①把它放到位置n,那么,对于剩下的n-2个元素,就有M(n-2)种方法;
                                                   ②不把它放到位置n,这时,对于这n-1个元素,有M(n-1)种方法。 
         综上得到

M(n) = ( n - 1 ) [ M ( n - 2 ) + M ( n - 1 ) ]

特殊地,M ( 1 ) = 0 , M ( 2 ) = 1

  
                                                               

posted on 2010-05-08 17:36 宇骐 阅读(304) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2010年8月>
25262728293031
1234567
891011121314
15161718192021
22232425262728
2930311234

导航

统计

常用链接

留言簿

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜