全排列和组合数函数的实现

    在实验室闲的无聊,随意写了个全排列和组合数的函数模板,就当娱乐一下。这2个函数本身实现很简单,唯一要注意的就是都用到了“回溯”的技巧。

全排列n!:
 1 #include <iostream>
 2 using namespace std;
 3 
 4 void Perm(int k,int n,int a[]){
 5     if(k==n){
 6         for(int i=0;i<n;i++)
 7             cout<<a[i]<<' ';
 8         cout<<endl;
 9         return;
10     }
11     for(int i=k;i<n;i++){
12         swap(a[k],a[i]);
13         Perm(k+1,n,a);
14         swap(a[i],a[k]);      //回溯
15     }
16 }
17 int main(){
18     int i,n,a[10];
19     while(cin>>n,n){
20         for(i=0;i<n;i++) a[i]=i+1;
21         Perm(0,n,a);
22     }
23     return 0;
24 }

组合数C(n,k):
 1 #include <iostream>
 2 using namespace std;
 3 
 4 bool visited[10];
 5 void dfs(int pos,int cnt,int n,int k,int a[]){
 6     if(cnt==k){
 7         for(int i=0;i<n;i++)
 8             if(visited[i]) cout<<a[i]<<' ';
 9         cout<<endl;
10         return;
11     }
12     if(pos==n) return;
13     if(!visited[pos]){
14         visited[pos]=true;
15         dfs(pos+1,cnt+1,n,k,a);
16         visited[pos]=false;    //回溯
17     }
18     dfs(pos+1,cnt,n,k,a);
19 }
20 int main(){
21     int i,n,k,a[10];
22     while(cin>>n>>k,n||k){
23         for(i=0;i<n;i++) a[i]=i+1;
24         dfs(0,0,n,k,a);
25     }
26     return 0;
27 }

posted on 2009-04-24 16:48 极限定律 阅读(1185) 评论(0)  编辑 收藏 引用 所属分类: ACM/ICPC


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


<2009年4月>
2930311234
567891011
12131415161718
19202122232425
262728293012
3456789

导航

统计

常用链接

留言簿(10)

随笔分类

随笔档案

友情链接

搜索

最新评论

阅读排行榜

评论排行榜