康拓逆展开 以你之姓@ 2022-06-17 08:41 145阅读 0赞 康托展开的逆运算: \{1,2,3,4,5\}的全排列已经从小到大排序,要找出第16个数: 1. 首先用16-1得到15 2. 用15去除4! 得到0余15 3. 用15去除3! 得到2余3 4. 用3去除2! 得到1余1 5. 用1去除1! 得到1余0 有0个数比它小的数是1 所以第一位是1 有2个数比它小的数是3,但1已经在之前出现过了所以是4 有1个数比它小的数是2,但1已经在之前出现过了所以是3 有1个数比它小的数是2,但1,3,4都出现过了所以是5 最后一个数只能是2 所以这个数是14352 前提是在它后面的数,意思就是它前面比它小的不算进去 #include<cstdio> #include<algorithm> using namespace std; int f[10]={1,1,2,6,24,120,720,5040,40320,362880}; int s[10]; void kt(int sum,int n) { int i,j; bool v[10]={0}; sum--; for(i = 0;i < n; i++) { //得到有t个数比它小(数的范围是1到n),假设t=0,那就是在1 到 n 中 有 0个数比它小的,那这个数(即它) 只能是1了,因为只有 1 有0个数比它小; int t = sum / f[n - 1 - i]; for(j = 1; j <=n; j++)//这个从小到大的for就巧妙了,从小到大数t个数,就可以得到 满足条件的那个数(这里的条件是指 :有t个数比它小) { if(!v[j])//这里就是那个前提,他前面比它小的不算 { if(t == 0) break; t--; } } s[i] = j;//j就是找到的,最后把s这个数组全部输出就是要求的排列 v[j] = 1; sum %= f[n - 1 - i]; } } int main() { int n,m; while(~scanf("%d %d",&n,&m)) { kt(n,m); for(int i=0;i<m;i++) printf("%d",s[i]); printf("\n"); } return 0; }
还没有评论,来说两句吧...