枚举算法是最朴素的算法之一。
枚举算法也称之为穷举算法，就是按照问题本身的性质，一一列举出该问题所有可能的解，并在列举的过程中，逐一检验每个可能解是否是问题的真正解。若是则采纳这个解；否则抛弃它。
其中很重要的两点是不重、不漏，注意枚举算法是计算机可求解问题的本质方法，其特点为全面且实现简单，效率则相对较低，效率提升空间大。
例题
设\(S\)为由所有正整数按从小到大的顺序组成的序列，即\(S=1234567891011 \dots\)，记\(S\)中第一次出现\(1\)为位置\(1\)，求S的第\(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
| int f(int n) {
int base = 1;
int l = 1, step = 9, lnum = 1;
for (; base <= 8; base++) {
if (n >= l && n <= l + step - 1) {
break;
}
else {
l += step;
step *= (10 * (base + 1));
step /= base;
lnum *= 10;
}
}
if (base > 9) {
return -1;
}
int target = (n - l) / base + lnum;
int targetIndex = (n - l + 1) % base;
targetIndex = (!targetIndex ? base : targetIndex);
vector<int> v;
while (target){
v.push_back(target % 10);
target /= 10;
}
return v[v.size() - targetIndex];
}
|
