前言

  • 关于DFS：
    DFS算法是沿着搜索树的根节点，一直遍历完该搜索树之后再回溯继续搜索的一种算法。缺点是可能会出现答案在搜索树层数很浅，在靠后的子树中，但由于搜索次序需要遍历完一棵搜索树所有的节点，所以导致效率低下。
  • 关于BFS：
    BFS算法是沿着搜索树的根节点，按层遍历完该搜索树所有节点的一种算法。缺点是可能会出现答案在搜索树层数很深的地方，导致效率低下。且如果是满二叉树这样的搜索树很可能会使在BFS的过程中队列爆掉。在层数很多的时候会占用很多的空间。
  • 关于迭代加深：
    迭代加深算法其实是一种结合了DFS和BFS两种算法特点的搜索算法。我们会预设搜索的层数，然后仅在该层数以内进行DFS。这一算法很有效的避免了DFS可能会出现的效率低下的问题。
    而似乎这样的算法思路和BFS相同，而且由于拓展层数的时候会重复搜索，所以反而更慢了。但其实，迭代加深有效的避免了使用大量空间的问题，相对于普通的BFS也是有优势的。

题目

链接

2024-01-07_20-19-26

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;
const int N = 1e4 + 5;
long long n, maxd, ans[N];
bool dfs(int k) {
    if (k > maxd) return ans[k - 1] == n;
    if (ans[k - 1] * (long long)pow(2, maxd - k + 1) < n) return 0;  // 最优化剪枝：后面每一项最多是前一项的2倍
    for (int i = 0; i < k; i++)
        for (int j = i; j < k; j++) {
            long long t = ans[i] + ans[j];
            if (t > n) break;               // 可行性剪枝：ans单调递增，如果t>n则后面的j都会大于n；
            if (t <= ans[k - 1]) continue;  // 保证ans单调递增
            ans[k] = t;
            if (dfs(k + 1)) return 1;
        }
    return 0;
}
int main() {
    ans[0] = 1;
    while (cin >> n) {
        for (maxd = 0;; maxd++) {//一点一点加大深度
            if (dfs(1)) {
				cout << maxd << endl;
				cout << 1 << " ";
                for (int i = 1; i <= maxd; i++)
					cout << ans[i] << " ";
                cout << '\n';
                break;
            }
        }
    }
    return 0;
}