1 专题介绍

本专题用来记录使用迭代加深DFS、双向DFS和IDA*算法求解的问题。

2 训练

题目1：170加成序列

C++代码如下，

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;

int n;
int path[N];

bool dfs(int u, int k) {
    if (u == k) return path[u - 1] == n;
    
    bool st[N] = {0};
    for (int i = u - 1; i >= 0; --i) {
        for (int j = i; j >= 0; --j) {
            int s = path[i] + path[j];
            if (s > n || s <= path[u - 1] || st[s]) continue;
            st[s] = true;
            path[u] = s;
            if (dfs(u + 1, k)) return true;
        }
    }
    return false;
}

int main() {
    path[0] = 1;
    while (cin >> n, n) {
        int k = 1;
        while (!dfs(1, k)) k++;
        
        for (int i = 0; i < k; ++i) cout << path[i] << ' ';
        cout << endl;
    }
    
    return 0;
}

题目2：