当前位置:编程学习 > C/C++ >>

递归方法求全排列

[cpp]
/*****************************************************************\
全排列问题 例如,
输入: 
3
1 2 3
输出:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
\*****************************************************************/ 
#include<stdio.h>  
#include<string.h>  
#include<assert.h>  
 
const int maxn = 100; 
 
int num[maxn]; 
bool used[maxn]; 
int ans[maxn]; 
 
void output(int n) 

    for(int i=0; i<n; i++) 
    { 
        if(i < n-1) 
            printf("%d ", ans[i]); 
        else 
            printf("%d\n", ans[i]); 
    } 

 
void fullPerm(int n, int dep) 

    if(dep >= n) 
    { 
        output(dep); 
        return; 
    } 
    for(int i=0; i<n; i++) 
    { 
        if(!used[i]) 
        { 
            used[i] = true; 
            ans[dep] = num[i]; 
            fullPerm(n, dep+1); 
            used[i] = false; 
        } 
    } 

 
void test() 

    int n = 0; 
    while(scanf("%d", &n) != EOF) 
    { 
        if(n == 0) break; 
        for(int i=0; i<n; i++) 
            scanf("%d", &num[i]); 
        memset(used, false, sizeof(used)); 
        memset(ans, -1, sizeof(ans)); 
        fullPerm(n, 0); 
    } 

 
int main() 

    test(); 
    return 0; 

/*****************************************************************\
全排列问题 例如,
输入:
3
1 2 3
输出:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
\*****************************************************************/
#include<stdio.h>
#include<string.h>
#include<assert.h>

const int maxn = 100;

int num[maxn];
bool used[maxn];
int ans[maxn];

void output(int n)
{
 for(int i=0; i<n; i++)
 {
  if(i < n-1)
   printf("%d ", ans[i]);
  else
   printf("%d\n", ans[i]);
 }
}

void fullPerm(int n, int dep)
{
 if(dep >= n)
 {
  output(dep);
  return;
 }
 for(int i=0; i<n; i++)
 {
  if(!used[i])
  {
   used[i] = true;
   ans[dep] = num[i];
   fullPerm(n, dep+1);
   used[i] = false;
  }
 }
}

void test()
{
 int n = 0;
 while(scanf("%d", &n) != EOF)
 {
  if(n == 0) break;
  for(int i=0; i<n; i++)
   scanf("%d", &num[i]);
  memset(used, false, sizeof(used));
  memset(ans, -1, sizeof(ans));
  fullPerm(n, 0);
 }
}

int main()
{
 test();
 return 0;
}

 

补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,