19-擅长排列的小明

内存限制:64MB
时间限制:1000ms
Special Judge: No

accepted:10
submit:16

题目描述:

小明十分聪明，而且十分擅长排列计算。比如给小明一个数字5，他能立刻给出1-5按字典序的全排列，如果你想为难他，在这5个数字中选出几个数字让他继续全排列，那么你就错了，他同样的很擅长。现在需要你写一个程序来验证擅长排列的小明到底对不对。

输入描述:

第一行输入整数N（1<N<10）表示多少组测试数据，

每组测试数据第一行两个整数 n m (1<n<9,0<m<=n)

输出描述:

在1-n中选取m个字符进行全排列，按字典序全部输出,每种排列占一行，每组数据间不需分界。如样例

样例输入:

复制

样例输出:

1

2

3

12

13

14

21

23

24

31

32

34

41

42

43

分析：
　　根据全排列的性质，一组包含所有组合的全排列（ps:假设该组数由n个元素组成，我们要从中选择m个元素，问它的组合情况），
　　它所对应的前m个元素，就是它的所有选择、组合情况

扩展：
　　equal(A, A+m, B);
　　//用于比较数组A和数组B是否相同，即就是取数组A的前m个元素与数组B做比较

步骤：
　　①、初始化A为1到n组成的数组
　　②、通过STL中的next_permutation()创建数组A的全排列
　　③、如果下一个排列与上一个排列不同就用temp来存放下一个排列

核心代码：

 do

 {

     if(!equal(A, A+m, temp))

     {

         for(int i = ; i < m; ++ i)

         {

             temp[i] = A[i];

             printf("%d", temp[i]);

         }

         printf("\n");

     }

 } while(next_permutation(A, A+n));

C/C++代码实现（AC）：

 #include <iostream>

 #include <algorithm>

 #include <cstring>

 #include <cstdio>

 #include <cmath>

 #include <stack>

 #include <map>

 #include <queue>

 using namespace std;

 const int MAXN = ;

 int A[MAXN];

 void cal_array(int n)

 {

     for(int i = ; i < n; ++ i)

         A[i] = i + ;

 }

 int main()

 {

     int t;

     scanf("%d", &t);

     while(t --)

     {

         int n, m, temp[MAXN] = {};

         scanf("%d%d", &n, &m);

         cal_array(n);

         do

         {

             if(!equal(A, A + m, temp)) // 如果数组A的前m个元素与temp两个数组不想等

             {

                 for(int i = ; i < m; ++ i)

                 {

                     temp[i] = A[i];

                     printf("%d", temp[i]);

                 }

                 printf("\n");

             }

         } while(next_permutation(A, A + n));

     }

     return ;

 }

巴特西

nyoj 19-擅长排列的小明(STL-next_permutation())

19-擅长排列的小明

题目描述:

输入描述:

输出描述:

样例输入:

样例输出:

最新文章

热门文章