NOIP 普及 2012 第一轮 第 32 题：按字典序生成排列：第 1 空

题目

完善程序
（排列数） 输入两个正整数 $n,m(1<n<20,1<m<n)$，在 $1\sim 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;
}

①处应填（ ）

答案

false

题解

考点定位

本题（完善程序「排列数」第①空）考「是否还有后继」,对应大纲 4.3.1 生成排列（难度【4】）。

程序思路：data 存当前排列，逐个产生字典序下一个排列；flag 标记是否还有下一个。

解题过程

①处输出当前排列后，假设没有下一个（后面找到才置 true）：

``cpp flag = false; ``

答案：false。

易错提醒

① 「先假后真」的写法：初始 flag=false，找到可增位时置 true；② 与下文的 if(flag) 呼应。