题目描述
将 $1$ , $2$ , $\cdots$ , $9$ 共 $9$ 个数分成 $3$ 组，分别组成 $3$ 个三位数，且使这 $3$ 个三位数构成 $1:2:3$ 的比例，试求出所有满足条件的 $3$ 个三位数。
本题为提交答案题，您可以写程序或手算在本机上算出答案后，直接提交答案文本，也可提交答案生成程序。
输出格式
若干行，每行 $3$ 个数字。按照每行第 $1$ 个数字升序排列。
解决思路
很多大佬都是用循环模拟的，在这里我就不赘述了。我想介绍一种新的思路，就是深度优先搜索+回溯。
$dfs$ 作为一种暴力的算法，在一些只提交答案的题目中很占优势（不必在意时间复杂度）。
这道题的思路就是依次搜索 $3$ 个三位数上每一位的数字，当搜索完 $9$ 个数字后，判断是否符合题意并输出就行了。
代码实现
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
#include <iostream>
using namespace std;
int a[10];//存储三个三位数
bool b[10];//判断数字是否使用过
void print()//判断+输出结果
{
int b = 100 * a[1] + 10 * a[2] + a[3]; // 计算第一个三位数
int c = 100 * a[4] + 10 * a[5] + a[6]; // 计算第二个三位数
int d = 100 * a[7] + 10 * a[8] + a[9]; // 计算第三个三位数
if (d == 3 * b && c == 2 * b) // 如果b:c:d=1:2:3
{
for (int i = 1; i <= 7; i += 3) // 循环步长为3
cout << a[i] << a[i + 1] << a[i + 2] << " ";
cout << endl;
}
return;
}
void dfs(int k)
{
int maxn = 9; // 搜索1-9
if (k == 1) // 若是第一个数的百位数
maxn = 3; // 搜索1-3
else if (k == 4) // 若事第二个数的百位数
maxn = 6; // 搜索1-6
for (int i = 1; i <= maxn; i++)
{
if (b[i]) // 如果i被使用过
continue; // 跳过该轮循环
a[k] = i;
b[i] = 1; // 将i标记为使用过
if (k == 9) // 如果搜完了
print(); // 判断+输出
else
dfs(k + 1); // 继续下一位数搜索
a[k] = 0; // 回溯
b[i] = 0; // 回溯
}
return;
}
int main()
{
dfs(1); // 从第一个数搜起
return 0;
}
