Theme NexT works best with JavaScript enabled

人生若只如初见

📢📢📢:博主开学了!封闭中!

回溯法经典例题

编写一个由1-9组成的9位数,并且数字不重复,前N项能被N整除。

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 <iostream>
using namespace std;

int number = 0;
int visited[10] = {1, 0, 0, 0, 0, 0, 0, 0, 0, 0};

void makenumber(int n) {
if (n < 1) {
cout << "ERROR!" << endl;
return;
}
if (n == 10) {
cout << number << endl;
}
for (int j = 1; j <= 9; ++j) {
if (!visited[j]) {
int temp = number;
temp = temp * 10 + j;
if (temp % n == 0) {
number = temp;
visited[j] = 1;
makenumber(n + 1);
number = number / 10;
visited[j] = 0;//BackTracking
}
}
}
}

int main() {
makenumber(1);
return 0;
}

本题主要是采用了递归回溯法,读者需自行分析。我没有进行数学分析,只是盲目的暴力枚举。

-------------------- ⭐本文结束⭐ --------------------