杭电oj网站ACM2005

来源：蜘蛛抓取(WebSpider) 时间：2018-04-23 16:19 标签： 杭电oj网站

/*思路：用递推法1）如果前n-1个格匼法，则第一个格颜色和第n-1个格的颜色不同则此时第n个格的颜色是只有一种可能颜色（因为和第一个格的颜色不能相同，还有和其相邻嘚第n-1格的颜色也不能相同）
2）如果前n-1个格不合法第n-1个格和第一个格的颜色相同，且前n-2个格合法第n格子不能和第n-1个格和第一个格相同，所以第n个格的选择有2种*/

当n个编号元素放在n个编号位置元素编号与位置编号各不对应的方法数用D(n)表示，那么D(n-1)就表示n-1个编号元素放在n-1个编号位置各不对应的方法数，其它类推.

第一步把第n个元素放在一个位置，比如位置k一共有n-1种方法；

第二步，放编号为k的元素这时有两種情况：⑴把它放到位置n，那么对于剩下的n-1个元素，由于第k个元素放到了位置n剩下n-2个元素就有D(n-2)种方法；⑵第k个元素不把它放到位置n，這时对于这n-1个元素，有D(n-1)种方法；

我要回帖

更多关于 杭电oj网站 的文章

 

随机推荐