NOIP 提高 2012 第一轮 第 30 题：完善程序（排列数）第 4 空

题目

1.（排列数）输入两个正整数 $n, m (1 \leq n \leq 20, 1 \leq m \leq 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;
						}
				⑤;
			}
		}
	}
}

④处应填（ ）

答案

n

题解

考点定位

本题（排列数第④空）考「重填扫描上界」,对应大纲 4.3.1 生成排列（难度【2】）。

解题过程

④处后缀重填扫描到数字上界：

``cpp for (j = 1; j <= n; j++) ``

答案：n。

易错提醒

① 从小到大填保证后缀字典序最小；② 上界是值域 n 不是位置数。