NOIP 2012 普及组初赛 第28题 排列数

【题目】

NOIP 2012 普及组初赛 第28题 排列数
完善程序 （排列数）
输入两个正整数 n,m(1字典序从小到大输出所有这样的排列。
例如： 输入：3 2
输出：
1 2
1 3
2 1
2 3
3 1
3 2

#include 
#include 
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;	
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

【题目考点】

1. 循环

2. 标志位

【解题思路】

求排列数，我们学过用深搜解决，但看该题的解法不像深搜。我们需要一点一点搞清该代码所用的算法。

cin>>n>>m;
memset(used,false,sizeof(used));
for(i=1;i<=m;i++)
{
	data[i]=i;
	used[i]=true;	
}
1
2
3
4
5
6
7

先输入n与m，要在1~n中输出m个数字的排列。
看变量名，就能猜出这个变量名的意思，data[i]是第i个数据，used[i]意思就应该是第i个数是否已经使用过。初值是使用过。
flag是什么意思还待定。
只要flag为真，就进行while循环，进入while循环内部

for(i=1;i<=m-1;i++) cout<<data[i]<<" ";
cout<<data[m]<<endl;
flag= [    ①    ] ;
1
2
3

先是输出是data下标1~m，这表明data保存的是要输出的数字排列。输出的第一个排列就是1,2,…,m。
然后重新给flag设值。能进入while循环，flag一定是true。而这里要为flag重新设值，那一定是设为false。所以①填false。

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;	
		}
1
2
3
4
5
6
7
8
9
10
11

然后i从m循环到1，②处做了一些事情，先向下看。j从data[i]+1循环到n，如果j没有用过，就把j设为用过。然后给i的位置重新设值。
看到这里，大概就能看出题目代码要做的事情。data数组保存一个排列，而该段代码就是让data某一位变大，使其变为字典序下的下一个排列。

假设n是5，m是3，在1~5中选3个数字做排列，先是123，而后改变最后一位变为124，接着是125

因此此时要改变的就是data[i]这个数，需要将data[i]原有的值设为“没用过”，②处应该填used[data[i]] = false
然后从data[i]+1开始，找一个没有用过的数字j，作为data[i]的新的值。所以③处应该填j。
可见flag表示是否有某位置的值发生改变。如果某位置的值改变了，flag变为true，会运行进入下一段。否则不进入下一段，i--，进入下一次循环，改变data中i前一个位置的值。

if(flag)
{
	for(k=i+1;k<=m;k++)
		for(j=1;j<= [   ④   ];j++)
		if(!used[j])
		{
			data[k]=j;
			used[j]=true;
			break;
		}
	[     ⑤   ];
}
1
2
3
4
5
6
7
8
9
10
11
12

此时考虑，如果第i位的值已经改变了，接下来就需要将第i+1到最后一位的值变为可能的字典序最小的序列。

在1~5中选3个数字做排列，已经数到145，接着改变倒数第二位，把4变为5，而后最后一位需要变为字典序最小的且没用过的2，所以下一个排列为152，然后153，154。
接下来需要改变第1位，把第1位变为2，而后需要把后两位变为字典序最小的13，因此下一个排列为213

从第i+1位置开始，为每个位置都赋予当前没用过的数字中的最小值。
j从1开始，最大可以取到n，④位置填n。
⑤位置处于对i的循环之内，对k、j的循环之外。如果进入了if(flag)下的代码块，说明某位置的值改变了，并且整个data数组已经变为字典序下的下一个排列了。
那么接下来应该再次从末尾开始向前取找一个值可以变化的位置。因此应该跳出当前对i的循环，在更外层while(flag)的作用下，重新进度对i的循环，从末尾开始向前找一个位置，改变这个位置的值。因此⑤处填break。
如果已经找到了最后一个排列，那么不会有任何位置的值被改变，flag就是false，会跳出while循环。

在1~5中选3个数字做排列，如果排列已经是543，整段代码运行下来，flag都不会为true。

【答案】

① false
② used[data[i]]=false
③ j
④ n
⑤ break