题目链接:http://acm.bnu.edu.cn/bnuoj/problem_show.php?pid=17668
题目大意:
给定一个数,按要求输出元素最少的序列。其中ak = ai + aj ( )
。
解题思路:
迭代加深搜索:
限定搜索的深度k,然后开始进行DFS搜索,如果搜索完没有解,深度k = k + 1,继续上诉搜索,直到找到可行解。
#include<iostream> #include<fstream> #include<cstdio> #include<cstring> #include<cmath> #include<map> #include<queue> #include<stack> #include<vector> #include<set> #include<ctype.h> #include<algorithm> #include<string> #define PI acos(-1.0) #define maxn 1000 #define INF 1<<25 #define mem(a, b) memset(a, b, sizeof(a)) typedef long long ll; using namespace std; int a[20], n, b[20], depth; bool flag; void dfs(int t) { int i, j; if (flag) return ; if (t == depth) { if (a[t] == n) flag = true; return ; } for (i = 0; i <= t; i ++) for (j = i; j <= t; j++) if (a[i] + a[j] > a[t] && a[i] + a[j] <= n) { int sum = a[i] + a[j]; for (int k = t + 1; k < depth; k++) sum *= 2; // 剪枝 if (sum < n) continue; a[t + 1] = a[i] + a[j]; dfs(t + 1); if (flag) return ; } } int main () { a[0] = 1, a[1] = 2; while(scanf("%d", &n) != EOF) { if (!n) break; int m = 1; depth = 0; while(m < n) { depth++; m *= 2; } flag = false; while(1) { dfs(0); if (flag) break; depth++; } for (int i = 0; i < depth; i++) printf("%d ", a[i]); printf("%d\n", a[depth]); } return 0; }