Chinaunix首页 | 论坛 | 博客
  • 博客访问: 116950
  • 博文数量: 37
  • 博客积分: 2510
  • 博客等级: 少校
  • 技术积分: 306
  • 用 户 组: 普通用户
  • 注册时间: 2008-04-01 11:02
文章分类
文章存档

2011年(1)

2009年(1)

2008年(35)

我的朋友

分类:

2008-04-02 10:01:27

组合算法  

本程序的思路是开一个数组,其下标表示1到m个数,数组元素的值为1表示其下标  
代表的数被选中,为0则没选中。    
首先初始化,将数组前n个元素置1,表示第一个组合为前n个数。    
然后从左到右扫描数组元素值的“10”组合,找到第一个“10”组合后将其变为  
“01”组合,同时将其左边的所有“1”全部移动到数组的最左端。    
当第一个“1”移动到数组的m-n的位置,即n个“1”全部移动到最右端时,就得  
到了最后一个组合。    
例如求5中选3的组合:    

1 1 1 0 0 //1,2,3
1 1 0 1 0 //1,2,4
1 0 1 1 0 //1,3,4
0 1 1 1 0 //2,3,4
1 1 0 0 1 //1,2,5
1 0 1 0 1 //1,3,5
0 1 1 0 1 //2,3,5
1 0 0 1 1 //1,4,5
0 1 0 1 1 //2,4,5
0 0 1 1 1 //3,4,5

全排列算法  
   
从1到N,输出全排列,共N!条。  
分析:用N进制的方法吧。设一个N个单元的数组,对第一个单元做加一操作,满N进  
一。每加一次一就判断一下各位数组单元有无重复,有则再转回去做加一操作,没  
有则说明得到了一个排列方案。

/*****以下内容由busycai添加: *****/

 

例如:求1-3的全排列,共3!条
设数组初始状态为0 0 0,以下
为计算全排列的步骤:
0 0 0 +1
1 0 0 +1
2 0 0 +1
3 0 0 满3进1 ->
0 1 0 +1
1 1 0 +1
2 1 0 +1
3 1 0 满3进1 ->
0 2 0 +1
1 2 0 +1
2 2 0 +1
3 2 0 满3进1 ->
0 3 0 满3进1 ->
0 0 1 +1
1 0 1 +1
2 0 1 +1
3 0 1 满3进1 ->
0 1 1 +1
1 1 1 +1
2 1 1 +1
3 1 1 满3进1 ->
0 2 1 +1
1 2 1 +1
2 2 1 +1
3 2 1 满3进1 ->
0 3 1 满3进1 ->
0 0 2 +1
1 0 2 +1
2 0 2 +1
3 0 2 满3进1 ->
0 1 2 +1
1 1 2 +1
2 1 2 +1
3 1 2 满3进1 ->
0 2 2 +1
1 2 2 +1
2 2 2 +1
3 2 2 满3进1 ->
0 3 2 满3进1 ->
0 0 3 满3进1 ->
0 0 0

共6个YES,每一个对应一种排列。

阅读(2492) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~
评论热议
请登录后评论。

登录 注册