杭电1027 IgnatiusAndhe Princess II
是一个全排列，解题使用到数学知识 字典序，详细解释例子在我的 文件 里的《字典序》，可以直接用调用函数库里的next_permutation（），其头文件是<algorithm>
代码如下：
#include<iostream>
using namespace std;
#include<algorithm>
int main()
{
int arr[1001];
int n,m,i;
while(scanf("%d%d",&n,&m) != EOF)
{
for(i = 0; i <= n; i++)
{
arr[i] = i;
}
m--;
while(m--)
{
next_permutation(arr+1,arr+n+1);
}
for( i = 1; i < n; i++)
{
printf("%d ", arr[i]);
}
printf("%d\n",arr[n]);
}
return 0;
}
还可以用如下方法：
1.确定ca！> m时ca 的最小值
2.sa = ca！/ ca是（ca-1）的阶乘数，m/sa确定从倒数第ca个数开始数第几个数与倒数第ca个数交换
3.要注意的是：第二步交换之后要保证后面ca-1个数要从小到大排列
4.这时m=m-sa*（int（m/sa））
5.重复这一过程，直到m==1时结束
1 #include <iostream>
2 using namespace std;
3 int fa,fb,sa,sb;
4 int ans[1002];
5 int n,m;
6 void sw(int x,int y)
7 {
8 int tem;
9 tem=ans[y];
10 ans[y]=ans[x];
11 for(;x>y+1;x--)
12 {
13 ans[x]=ans[x-1];
14 }
15 ans[y+1]=tem;
16 }
17 void changehan(int x,int y,int z)
18 {
19 int temp=1,ca=1;
20 int na,nb,ma,mb;
21 sw(x,y);
22 if(z==1)
23 {
24 return;
25 }
26 while(z>temp)
27 {
28 ca++;
29 temp*=ca;
30 }
31 sa=ca;
32 na=temp/sa;nb=z/na;ma=z%na;
33 if(ma==0)
34 {
35 nb--;
36 }
37 mb=z-nb*na;
38 //cout<<n-sa+1+nb<<" "<<n-sa+1<<endl;
39 changehan(n-sa+1+nb,n-sa+1,mb);
40 }
41 int main()
42 {
43 int i,na,nb,ma,mb;
44 while(scanf("%d%d",&n,&m)!=EOF)
45 {
46 int temp=1,ca=1;
47 for(i=1;i<=n;i++)
48 {
49 ans[i]=i;
50 }
51 if(m==1)
52 {
53 for(i=1;i<=n;i++)
54 {
55 cout<<i;
56 if(i<n)cout<<" ";
57 else cout<<endl;
58 }
59 continue;
60 }
61 while(m>temp)
62 {
63 temp*=ca;
64 ca++;
65 }
66 sa=ca-1;sb=sa-1;
67 na=temp/sa;nb=m/na;ma=m%na;ca=n-sb;//na为下一个范围,nb为下个范围的个数
68 if(ma==0)
69 {
70 nb--;
71 }
72 mb=m-nb*na;
73 //cout<<n-sa+1+nb<<" "<<n-sa+1<<endl;
74 changehan((n-sa+1+nb),(n-sa+1), mb);
75 for(i=1;i<=n;i++)
76 {
77 cout<<ans[i];
78 if(i<n)cout<<" ";
79 else cout<<endl;
80 }
81 memset(ans,0,sizeof(ans));
82 }
83 return 0;
84 }