C++之小学奥数(2)

求出第k小排列

题目描述

给出两个正整数n，k（n<8，k<n!）求出第k小的n个数的排列。 //也就是说要求全排列出来后的第k个数

输入

只有一行：两个整数，n（n<8）,k小于n的阶乘

输出

输出该排列

样例输入

4 3

样例输出

题目分析

当n==4时，所有的全排列(数)如下：

1234,1243,1324,1342,1423,1432;

2134,2143,2314,2341,2413,2431;

3124,3142,3214,3241,3412,3421;

4123,4132,4213,4231,4312,4321.

所以输出的是第k(k==3)小的1324。

思路解析

首先运用全排列思想定义search函数，其次定义output函数使total进行计数，若total==k(即该排列是第k小的时候)，输出答案。

实现代码

代码如下：

#include<cstdio>    
#include<cstring>  
bool check[8]; 
int num[8];   // 
int n,k,total; //n,k即题目要求的n,k;total计算当前是第几个排列 
void output()
{  
    total++;     //计算当前是第几个排列 
    if(total==k)
    {
     for(int i=1;i<=n;i++)      //输出第k大的数 
         printf("%d",num[i]);
    }
}  
void search(int x)  
{   
    for(int i=1;i<=n;i++) 
        if(!check[i])      //判断该数是否被标记 
        {
            num[x]=i;       //存储方案 
            check[i]=1;      //标记该数 
            if(x==n) output(); 
            else search(x+1); 
            check[i]=0;      //回溯 
            /*num[x]=0;*/    //可省略 
        }  
}  
main()    
{  
    scanf("%d%d",&n,&k);
    search(1); 
}

感想总结

全排列的思想真的很方便，能够帮助我们完成很多题。

触类旁通

题目描述

给出两个正整数n，k（n<8，k<n!）求出第k大的n个数的排列。

输入

只有一行：两个整数，n（n<8）,k小于n的阶乘

输出

输出该排列

样例输入

4 3