从前慢现在也慢

这个屌丝很懒，什么也没留下！

热门标签

回溯算法总结_python输入正整数n(n<10),输出abcd...n个不同字母的全排列,输出时按升序每行显示

作者：从前慢现在也慢 | 2024-07-14 16:22:10

踩

python输入正整数n(n<10),输出abcd...n个不同字母的全排列,输出时按升序每行显示

问题 A: 全排列问题

题目描述

输出自然数1到n所有不重复的排列，即n的全排列，要求所产生的任一数字序列中不允许出现重复的数字。

输入

输入 n(1≤n≤9)

输出

由1～n组成的所有不重复的数字序列，每行一个序列。每个数字占5列。

样例输入

4
1

样例输出

    1    2    3    4
    1    2    4    3
    1    3    2    4
    1    3    4    2
    1    4    2    3
    1    4    3    2
    2    1    3    4
    2    1    4    3
    2    3    1    4
    2    3    4    1
    2    4    1    3
    2    1    4    3 
    3    1    2    4
    3    1    4    2
    3    2    1    4
    3    2    4    1
    3    4    1    2
    3    4    2    1
    4    1    2    3
    4    1    3    2
    4    2    1    3
    4    2    3    1
    4    3    1    2
    4    3    2    1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#include <iostream>
int usedArr[10], res[10], n;
using namespace std;
void permute(int k) {
    if (k == n) {
        for (int i = 1; i <= n; i++)
            printf("%5d", res[i]);
        puts("");
        return;
    }
    for (int i = 1; i <= n; ++i) {
        if (!usedArr[i]) {
        	usedArr[i] = 1; // //判断是否用过
            res[k+1] = i;
            permute(k + 1);
            usedArr[i] = 0;
        }
    }
}
int main() {
    cin >> n;
    for(int i = 0;i<10;i++){//初始化数列
        usedArr[i] = 0;
        res[i] = 0;
    }
    permute(0);
    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

问题 B: 输出N个不同字母的全排列

题目描述

输入正整数n（n＜10），输出ABCD…n个不同字母的全排列，输出时按升序每行显示一个结果

输入

正整数N（N＜10）

输出

N个字母的全排列，升序排列，每行一个

样例输入

【测试样例1】
1
【测试样例2】
2
【测试样例3】
3
【测试样例4】
4
1
2
3
4
5
6
7
8

样例输出

【测试样例1】
A
【测试样例2】
AB
BA
【测试样例3】
ABC
ACB
BAC
BCA
CAB
CBA
【测试样例4】
ABCD
ABDC
ACBD
ACDB
ADBC
ADCB
BACD
BADC
BCAD
BCDA
BDAC
BDCA
CABD
CADB
CBAD
CBDA
CDAC
CDCA
DABC
DACB
DBAC
DBCA
DCAB
DCBA
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

#include <iostream>
int usedArr[10], res[10], n;
using namespace std;
void permute(int k) {
    if (k == n) {
        for (int i = 1; i <= n; i++)
            printf("%c",res[i]);
        puts("");
        return;
    }
    for (int i = 1; i <= n; ++i) {
        if (!usedArr[i]) {
        	usedArr[i] = 1; // //判断是否用过
            res[k+1] = 64+i;
            permute(k + 1);
            usedArr[i] = 0;
        }
    }
}
int main() {
    cin >> n;
    for(int i = 0;i<10;i++){//初始化数列
        usedArr[i] = 0;
        res[i] = 0;
    }
    permute(0);
    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

问题 C: 组合的输出

题目描述

排列与组合是常用的数学方法，其中组合就是从n个元素中抽出r个元素(不分顺序且r<＝n)，我们可以简单地将n个元素理解为自然数1，2，…，n，从中任取r个数。

现要求你用递归的方法输出所有组合。

例如n＝5，r＝3，所有组合为：

l 2 3 l 2 4 1 2 5 l 3 4 l 3 5 1 4 5 2 3 4 2 3 5 2 4 5 3 4 5

输入

一行两个自然数n、r(1<n<21，1<＝r<＝n)。

输出

所有的组合，每一个组合占一行且其中的元素按由小到大的顺序排列，每个元素占三个字符的位置，所有的组合也按字典顺序。

样例输入

5 3
1

样例输出

#include <iostream>
int usedArr[21], res[21], n, r;
using namespace std;
void permute(int k,int r) {
    if (k == r + 1) {
        for (int i = 1; i <= r; i++)
            printf("%3d",res[i]);
        puts("");
        return;
    }
    for (int i = res[k-1]; i <= n; i++) {
        if (!usedArr[i]) {
        	usedArr[i] = 1; // //判断是否用过
            res[k] = i;
            permute(k + 1,r); 
            usedArr[i] = 0;
        }
    }
}
int main() {
    cin >> n >> r;
    res[0]=1;
    permute(1,r);
    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

问题 D: 排列棋子

题目描述

将M个白棋子与N个黑棋子排成一行，可以排成多种不同的图案。例如：2个白棋子和2个黑棋子，一共可以排成如下图所示的6种图案（根据组合数计算公式：）

说明: http://10.60.64.213:8080/JudgeOnline/images/4736_2.bmp

请你编写一段程序，输出M个白棋子与N个黑棋子能够组成的所有图案。

为了避免程序输出结果过多导致严重超时，特别限制：1≤M,N≤6

输入

两个正整数M,N表示白棋子与黑棋子的数量，并且满足1≤M,N≤6

输出

M个白棋子与N个黑棋子可以排列的所有图案。
要求：每行输出一种图案，白棋子用0表示，黑棋子用1表示，按升序输出

样例输入

【测试样例1】
2 1
【测试样例2】
2 2
【测试样例3】
2 3
1
2
3
4
5
6

样例输出

#include <iostream>
int usedArr[13], res[13], m, n,flag = 1;
int chess[13];
using namespace std;
void permute(int k) {
    if (k == m + n + 1) {
        for (int i = 1; i <=  m+n; i++)
            printf("%d",res[i]);
        puts("");
        flag = 0;
        return;
    }
    for (int i = 1; i <= m+n; i++) {
        if (!usedArr[i] && (res[k] != chess[i] || flag) ) {
        	flag = 1;
        	usedArr[i] = 1; // //判断是否用过
            res[k] = chess[i];
            permute(k + 1); 
            usedArr[i] = 0;
        }
    }
}
int main() {
	// M个白棋子与N个黑棋子
    cin >> m >> n;
    for (int i = 1; i <= m; i++)
        chess[i] = 0;
    for (int i=m+1; i <= m + n; i++)
        chess[i] = 1;
    permute(1);
    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

问题 E: 有重复元素的排列问题

题目描述

设R={ r1, r2 , …, rn}是要进行排列的n个小写字母。其中小写字母r1, r2 , …, rn可能相同。试设计一个算法，列出R的所有不同排列。

给定n 以及待排列的n 个小写字母。计算出这n 个小写字母的所有不同排列。

输入

输入数据的第1 行是小写字母个数n，1≤n≤500。接下来的1 行是待排列的n个元素。

输出

计算出的n个小写字母的所有不同排列并按字典序输出。文件最后1行中的数是排列总数。

样例输入

4
aacc
1
2

样例输出

aacc
acac
acca
caac
caca
ccaa
6
1
2
3
4
5
6
7

#include<iostream>
using namespace std;
char res[501], c;
int letters[27]={0}, n, count;
void permute(int start) {
    if (start > n) { // 其实就是start == n+1 说明数字都遍历完了，可以输出 
        for (int i = 1; i <= n; i++)
			printf("%c", res[i]);
        puts("");
        count++;
        return;
    }
    for (int i = 1; i <= 26; i++) // 因为每个字符位置都有26种可能 
        if (letters[i] > 0) { // 确定字母数>1 ,是可用状态 
            res[start] = char(i + 96); // 把字母存入res数组 
            letters[i]--; // 然后字母用掉一个letters[i]要-- 
            permute(start + 1); // 然后下一个坑继续 
            letters[i]++; // 这里是回溯 
        }
}
int main() {
    cin >> n; //96
    // 统计每个字母出现的次数 比如 letters[3] = 2 就表示输入的字符串c出现了两次 
    for (int i = 1; i <= n; i++) {
        cin >> c; //('a' - 1)
        letters[c - 96]++;
    }

    permute(1);
    cout << count << endl;
    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

问题 F: N皇后问题(Queen.cpp)

题目描述

在N*N的棋盘上放置N个皇后（n<=10）而彼此不受攻击（即在棋盘的任一行，任一列和任一对角线上不能放置2个皇后），编程求解所有的摆放方法。

输入

输入：n

输出

每行输出一种方案，每种方案顺序输出皇后所在的列号，每个数占5列。若无方案，则输出no solute!

样例输入

4
1

样例输出

    2    4    1    3
    3    1    4    2
1
2

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n;
int res[11];
bool limit=false;
int ct=0;
void getQueens(int current,int n){
	if (current == n){
		limit=true;
		for(int i=0;i<n;i++){
			printf("%5d",res[i]+1);
		}
		puts("");
	}
	
	for (int i = 0; i < n; i++) {
		bool flag = true;
        if(ct-1 < current){
            res[i] = i;
            ++ct;
        }else {
            res[current] = i;
		}
        for (int j = 0; j < current; j++) {
            // 这里判断皇后是否在y=x  
			// 或者 y=-x 上 或者同一列， 同一行不考虑
            if (res[j]==res[current] ||
                    abs(current - j) == abs(res[current]- res[j])) {
                flag = false;
            }
        }
        if (flag) {
            getQueens(current + 1, n);
        }	
	}
	
} 

int main(int argc, char** argv) {
	int n;
	cin >> n;
	getQueens(0,n);
	if(!limit)
		cout << "no solute!";
	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

问题 G: 4连通迷宫

题目描述

给定一个M*M(2≤M≤9)的迷宫，迷宫用0表示通路，1表示围墙。

迷宫的入口和出口分别位于左上角和右上角，入口和出口显然都是0。

在迷宫中移动可以沿着上、下、左、右四个方向进行，前进格子中数字为0时表示可以通过，为1时表示围墙不可通过，需要另外再找找路径。

请统计入口到出口的所有路径（不重复），并输出路径总数。若从入口无法到达出口，请输出0。

输入

第一行输入1个正整数M(≤M≤9)，表示迷宫是M行M列。

第2行到第n+1行是一个M阶的0-1方阵。

输出

统计入口到出口的所有路径（不重复），并输出路径总数。若从入口无法到达出口，请输出0。

样例输入

样例输出

1
1

#include <iostream>
using namespace std; 

int n;
bool f[10][10];
int fx[5] = {0,0,0,-1,1};
int fy[5] = {0,-1,1,0,0}; 
// 深搜存储路径：将xy点存储到r数组下标为k的位置 
int c=0;
void dfs(int x,int y){

	// 如果到了终点 
	if(x == 1 && y == n){
		c++;
		return;
	} 
	
	// 尝试不同的方向
	int tx,ty;
	for(int i=1;i<=4;i++){
		tx = x + fx[i];
		ty = y + fy[i];
		
		// 判断新的方向可达
		if(tx>=1 && tx<=n && ty >=1 && ty <=n && !f[tx][ty]){
				// 标记tx,ty点走过了
				f[tx][ty]=true; 
				dfs(tx,ty);
				// 回溯
				f[tx][ty]=false; 
			} 
	} 
}
int main(int argc, char** argv) {
	cin >> n;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++) 
			cin >> f[i][j];
	f[1][1] = true;
	dfs(1,1);
	cout << c; 
	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

问题 H: 8连通迷宫

题目描述

给定一个M*M(2≤M≤9)的迷宫，迷宫用0表示通路，1表示围墙。

迷宫的入口和出口分别位于左上角和右上角，入口和出口显然都是0。

在迷宫中移动可以沿着上、下、左、右、左上、右上、左下、右下八个方向进行，前进格子中数字为0时表示可以通过，为1时表示围墙不可通过，需要另外再找找路径。

请统计入口到出口的所有路径（不重复），并输出路径总数。若从入口无法到达出口，请输出0。

输入

第一行输入1个正整数M(≤M≤9)，表示迷宫是M行M列。

第2行到第n+1行是一个M阶的0-1方阵。

输出

统计入口到出口的所有路径（不重复），并输出路径总数。若从入口无法到达出口，请输出0。

样例输入

样例输出

4
1

#include <iostream>
using namespace std; 

int n;
bool f[10][10];
int fx[9] = {0,0,0,-1,1,-1,-1,1,1 };
int fy[9] = {0,-1,1,0,0,-1,1,-1,1 }; 
// 深搜存储路径：将xy点存储到r数组下标为k的位置 
int c=0;
void dfs(int x,int y){

	// 如果到了终点 
	if(x == 1 && y == n){
		c++;
		return;
	} 
	
	// 尝试不同的方向
	int tx,ty;
	for(int i=1;i<=8;i++){
		tx = x + fx[i];
		ty = y + fy[i];
		
		// 判断新的方向可达
		if(tx>=1 && tx<=n && ty >=1 && ty <=n && !f[tx][ty]){
				// 标记tx,ty点走过了
				f[tx][ty]=true; 
				dfs(tx,ty);
				// 回溯
				f[tx][ty]=false; 
			} 
	} 
}
int main(int argc, char** argv) {
	cin >> n;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++) 
			cin >> f[i][j];
	f[1][1] = true;
	dfs(1,1);
	cout << c; 
	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

问题 I: 拆分自然数

题目描述

任何一个大于1的自然数n(n <= 10)，总可以拆分成若干个小于n的自然数之和。

当n=7共14种拆分方法：

7=1+1+1+1+1+1+1

7=1+1+1+1+1+2

7=1+1+1+1+3

7=1+1+1+2+2

7=1+1+1+4

7=1+1+2+3

7=1+1+5

7=1+2+2+2

7=1+2+4

7=1+3+3

7=1+6

7=2+2+3

7=2+5

7=3+4

输入

输入自然数n

输出

输出拆分的方案。

样例输入

7
1

样例输出

1+1+1+1+1+1+1
1+1+1+1+1+2
1+1+1+1+3
1+1+1+2+2
1+1+1+4
1+1+2+3
1+1+5
1+2+2+2
1+2+4
1+3+3
1+6
2+2+3
2+5
3+4
1
2
3
4
5
6
7
8
9
10
11
12
13
14

#include <iostream>
using namespace std;

int n;
int res[11]={1};
int print(int start) {
	for(int i=1; i<start; i++)
		cout<<res[i]<<"+";
	cout<<res[start]<<endl;
}
void dfs(int nn,int start) {
	for(int i=res[start-1]; i<=nn; i++) {
		if(i<n) { // 避免出现7=7
			res[start]=i;
			nn-=i;
			if(nn==0) { // 拆分完
				print(start);
			} else {
				dfs(nn,start+1);
			}
			// 回溯
			nn+=i;
		}
	}
}

int main() {
	cin >> n;
	dfs(n,1);
	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

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/从前慢现在也慢/article/detail/825523