#10767. 枚举算法(NOIP2012)排列数

枚举算法(NOIP2012)排列数

(NOIP2012)排列数

输入两个正整数n, m(1<=n<=20,1<=m<=n),在1~n中任取m个数,按字典序从小到大输出所有这样的排列。

例如:

输入:
3 2
输出:
1 2
1 3
2 1
2 3
3 1
3 2
#include<iostream>
#include<cstring>
using namespace std;
const int SIZE=25;
bool used[SIZE];
int data[SIZE];
int n,m,i,j,k;
bool flag;
int main() {
    cin>>n>>m;
    memset(used,false,sizeof(used));
    for (i=1;i<=m;i++) {
        data[i]=i;
        used[i]=true;
    }
    flag=true;
    while (flag) {
        for (i=1;i<=m-1;i++) cout<<data[i]<<" ";
        cout<<data[m]<<endl;
        flag= ① ;
        for (i=m;i>=1;i--) {
            ② ;
            for (j=data[i]+1;j<=n;j++)
                if (!used[j]) {
                    used[j]=true;
                    data[i]= ③ ;
                    flag=true;
                    break;
                }
            if (flag) {
                for (k=i+1;k<=m;k++)
                    for (j=1;j<= ④ ;j++)
                        if (!used[j]) {
                            data[k]=j;
                            used[j]=true;
                            break;
                        }
                ⑤ ;
            }
        }
    }
    return 0;
}

①处应填( )。
{{ select(1) }}

  • 0
  • 1
  • !flag
  • used[m]

②处应填( )。
{{ select(2) }}

  • used[data[i]]=false
  • used[i]=false
  • used[data[i]]=true
  • used[i]=true

③处应填( )。
{{ select(3) }}

  • !flag
  • data[j]
  • j
  • flag

④处应填( )。
{{ select(4) }}

  • n+m
  • k
  • n
  • m

⑤处应填( )。
{{ select(5) }}

  • return 0
  • continue
  • !flag
  • break