回溯法

7-20 全排列

对于1~n这n个不同的数,按照一定的顺序把这n个数排列起来(每个数出现一次,且不重复, n<10),将所有的排列列出,称为全排列。

输入格式:

一个数n。

输出格式:

1~n的全排列,每个排列一行(按字典序输出)。

输入样例:

1
3

输出样例:

1
2
3
4
5
6
1 2 3 
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

EXP:

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
#include<bits/stdc++.h>
using namespace std;
int n,x[100],vis[100];
void dfs(int t)
{
if(t==n+1)
{
for(int j=1;j<=n;j++)
cout<<x[j]<<" ";
cout<<endl;
return;
}
for(int i=1;i<=n;i++){
if(!vis[i]){
x[t]=i;
vis[i]=1;
dfs(t+1);
vis[i]=0;
}
}
}
int main()
{
cin>>n;
dfs(1);
}

7-21 n queens

有一个有n行n列的棋盘,你需要在棋盘上放置n个皇后,同一行没有两个皇后(包括对角线)。

输入规格:

输入一个整数 n 表示 n 个皇后。

输出规格:

将一个解决方案放在一行中(例如,在 4 个皇后中,一个解决方案是 2 4 1 3,这意味着第一行皇后将放在第 2 列,第 2 行皇后将放在第 4 列,并且依此类推),然后在最后一行输出总解决方案编号。

输入示例:

1
4

输出示例:

1
2
3
2 4 1 3 
3 1 4 2
2

EXP:

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
#include<bits/stdc++.h>
using namespace std;
int n,x[100],cnt=0;
bool check(int t)
{
for(int i=1;i<t;i++){
if((x[i]==x[t])||(t-x[t]==i-x[i])||(t+x[t]==i+x[i]))
return false;
}
return true;
}
void dfs(int t)
{
if(t==n+1)
{
for(int j=1;j<=n;j++)
cout<<x[j]<<" ";
cnt++;
cout<<endl;
return;
}
for(int i=1;i<=n;i++){
x[t]=i;
if(check(t)){
dfs(t+1);
}
}
}
int main()
{
cin>>n;
dfs(1);
cout<<cnt;
}

7-22 逆序数

设x1,x2,x3…,xn是集合{1,2,3,…,n}的一个排列,排列中逆序对的对数称为逆序数,(如1432的逆序数为3,即有3对逆序对,分别为:43,42,32)。则当x3=4时(即第3个数为4),所有排列的逆序数的和为多少?(n=6时,为2020年全国高中数学联赛浙江赛区初赛试题填空第10题)

输入格式:

输入一个n(n<10)。

输出格式:

输出逆序数的和。

输入样例:

1
6

输出样例:

1
912

EXP:

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
#include<bits/stdc++.h>
using namespace std;
int n,x[100],vis[100],cnt=0;
void dfs(int t)
{
if(t==n+1)
{
if(x[3]==4){
for(int j=1;j<=n;j++)
for(int k=j+1;k<=n;k++)
if(x[j]>x[k])
cnt++;
}
return;
}
for(int i=1;i<=n;i++){
x[t]=i;
if(!vis[i]){
vis[i]=1;
dfs(t+1);
vis[i]=0;
}
}
}
int main()
{
cin>>n;
dfs(1);
cout<<cnt;
}

7-23 整数拆分

一个正整数n拆分成若干个正整数的和(至少两个数,n<=100)。

输入格式:

一个正整数n

输出格式:

若干行,每行一个等式(数与数之间要求非降序排列)。最后一行给出解的总个数

输入样例:

在这里给出一组输入。例如:

1
4

输出样例:

1
2
3
4
5
4=1+1+1+1
4=1+1+2
4=1+3
4=2+2
4

最后一行的4表示总共有4个解。

EXP:

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
#include<bits/stdc++.h>
using namespace std;
int n,x[1000],cnt=0;
void dfs(int s,int t)
{
if(s==0)
{
cout<<n<<"=";
for(int i=1;i<t-1;i++){
cout<<x[i]<<"+";
}
cout<<x[t-1];
cout<<endl;
cnt++;
return;
}
for(int k=x[t-1];k<=s;k++){
if(k<n){
x[t]=k;
//s=s-k;
dfs(s-k,t+1);//dfs(s,t-1) //判断下一个数是否符合
//s=s+k;
}
////这里回溯的隐含的,s==0,则不进入循环;同时回溯到循环内,k++,继续循环
}
}
int main()
{
cin>>n;
x[0]=1;
dfs(n,1);
cout<<cnt;
}

扫一扫,分享到微信

微信分享二维码

请我喝杯咖啡吧~

支付宝
微信