蓝桥杯练习全排列

从0到9的全排列排列顺序是每一个都与打头的元素进行交换

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 int a[10]={0,1,2,3,4,5,6,7,8,9};
 4 int t;
 5 int j;
 6 int i=0;
 7 void pailie(int q,int z,int n)
 8 {
 9     int k;
10     int m=n;
11     if(q==z)
12     {
13         i++;
14     if(i==n)
15     {
16             for(j=0;j<10;j++)
17             {
18                 printf("%d",a[j]);
19             }
20              
21              printf("
");
22         }
23     }
24 else{
25     for(k=q;k<=z;k++)
26     {
27    //    swap(a[k],a[q]);
28          t=a[q];
29          a[q]=a[k];
30          a[k]=t;
31         pailie(q+1,z,m);
32          t=a[q];
33          a[q]=a[k];
34          a[k]=t;
35     }
36 }    
37     
38 }        
39 int main()
40 {
41     int n;
42     scanf("%d",&n);
43     pailie(0,9,n);
44     return 0;
45 }

问题描述

　　0、1、2三个数字的全排列有六种，按照字母序排列如下：
　　012、021、102、120、201、210
　　输入一个数n
　　求0~9十个数的全排列中的第n个（第1个为0123456789）。

输入格式

　　一行，包含一个整数n

输出格式

　　一行，包含一组10个数字的全排列

样例输入

样例输出

0123456789

数据规模和约定

　　0 < n <= 10!

字典序的排法运用的是模板的方法

#include <iostream>  
#include <algorithm>  
#include <string>  
using namespace std;  
int main()  
{  
    string str = "0123456789";  
    int n,m = 1;  
    scanf("%d",&n);  
    if(n == 1)  
        printf("0123456789");  
    else  
        while (next_permutation(str.begin(), str.end()))  
        {  
            if(m == n - 1)  
            {  
                cout << str << endl;  
                break;  
            }  
            m++;  
        }  
    return 0;  
}

这道题暂时没有思路，就采用了C++的库函数，

next_permutation
这个函数的用法，把起始的和最后的作为参数，得到结果  
上面的那个题

字典序的另一个解法
递归算出的全排列的顺序并不遵循从左到右逐个比较对应字符的前后，字典序还要 
非字典序的解法  答案顺序为123 132 213 231 321 312 
字典序  123 132 213 1231 312 321  
如果想要排成字典序的话需要用深搜的办法，即尽可能多的搜索每一条路径，一旦搜索到某条路的尽头时候，则回溯岛上一个节点，若上一个节点有未被搜索的边则沿着这条边继续深搜
如此反复直到所有的节点都被搜索过   另一种解法

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 using namespace std;
 5 int a[10];
 6 int use[10]={0};
 7 int n=10;
 8 int count=0;
 9 void dfs(int i,int l)
10 {
11     if(i>n)
12     {
13         count++;
14         if(count==l)
15         {
16             for(int j=1;j<n+1;j++)
17             cout<<a[j];
18             cout<<"
" ;
19         }
20         
21     }
22     else
23     {
24         for(int k=0;k<n;k++)//控制是不是还有扩展的节点
25         {
26             if(use[k]==0)
27             {
28               use[k]=1;
29               a[i]=k;
30               dfs(i+1,l);
31               use[k]=0;   
32             } 
33         }
34     }
35 }
36 int main()
37 {
38     int l;
39     scanf("%d",&l);
40     dfs(1,l);
41     return 0;
42  }

蓝桥杯练习 全排列

蓝桥杯练习全排列