题解 P1157 【组合的输出】

谁来挑战我的短代码!!嘻~~

其实小生还怪不好意思的,从来就没弄懂递推和回溯……

这道题的重点:

1:存储:这道题很烦的要我们把每次挑出来的组合都输出;所以我建了一个数组,来储存1~r个数;

2:回溯:这里我设了一个计数器t,只要还没到r个数,就继续套函数,到下一遍;

3:判断:(1)如果没有if(i>a[t-1])这一句的话,就会输出所有的排列,而不是组合,因为当t=r时,函数输出并回溯,a[t]就会等于a[t-1];

就拿n=5;r=3举例:比如现在第一遍挑数结束t=3,必然会输出第1,2,3种组合1 2 3,1 2 4,1 2 5然后函数回溯,现在数组a中a[1]=1;a[2]=2;a[3]=3;回到t=2;继续for(i=t;i<=n;i++)的循环由于是第二次,所以i++,i变成3;所以a[2]=3;现在数组变成a[1]=1;a[2]=3;a[3]=5;

现在t!=r;所以进入函数p(t+1);开始循环,i=t=3并把a[t]赋值为3,现在就变成了a[1]=1;a[2]=3;a[3]=3;但组合不能出现相同的数;为避免回溯时发生重复,判断i是否大于上一个数,只要保证后面的数比前面的数大,就可以输出;

(2)有可能没听懂?小生再用另一种方式讲一遍:如果我们要手算出所有组合,你会怎么做?

第一种肯定是从1开始加1 也就是1 2 3;

第二、三种发现3后面还有4 5;所以1 2 4,1 2 5;

第四种发现1 2 开头的没了,2+1,开始做1 3……以此类推这就是我们的

1
2
3
4
for(i=t;i<=n;i++)
{if(i>a[t-1])
{a[t]=i;
if(t!=r)p(t+1);

每次都要加1嘛,所以后面的数肯定比前面的大,也就解释了if(i>a[t-1])的判断和p(t+1)的找下一个;找完1 2 找1 3 也就是t=r并且这个层次的3,4,5都循环后,回溯到t=2并i++;再找1 3开头的,以此类推

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
#include<iostream>//P1157
#include<cstdio>
#include<cstring>
#include<string>
#include<iomanip>
#include <algorithm>
#include<cmath>
#include<vector>
#include<set>
using namespace std;
int a[23],n,r;
int p(int t)
{
int i,j;
for(i=t;i<=n;i++)
{if(i>a[t-1])
{a[t]=i;
if(t!=r)p(t+1);//感觉程序已经没什么好解释的了
else{for(j=1;j<=r;j++)printf("%3d",a[j]);cout<<endl;}}}
return 0;
}
int main()
{
cin>>n>>r;
p(1);
return 0;
}

如果还是没听懂,拿纸和笔自己推一遍就明白了

顺便说一句代码如果看着长请自动忽略头文件…………

顺手留赞,小生万分感激<^_^>