Input
Output
Sample Input
5 7 12 15 77 0
Sample Output
1 2 4 5 1 2 4 6 7 1 2 4 8 12 1 2 4 5 10 15 1 2 4 8 9 17 34 68 77
题意:x【1】 = 1，x【m】 = n，给一个n，求出m最小的序列并输出
思路：这种最短的问题很容易直接想到bfs，但是写法可能不是很经常遇到，网上也有bfs写法的代码，就不给出代码了，主要就是bfs的路径记录，用个vector储存路径，并且每个路径记录前置路径，当达到答案n时，路径肯定最短，然后沿着记录的前置路径递归
其次可以有dfs，dfs的话有两种，一种是迭代加深，就是枚举搜索深度，如果没搜索到答案，就增加深度重新搜索，这种方法主要用在确定答案可以在较小深度的情况，时间复杂度类似bfs，但是空间复杂度小
最后就是dfs的剪枝版本了，剪枝的话其实是一个最优性剪枝（极限思想）和搜索顺序，搜索顺序正常从大到小，我们发现从打一个数x1递增到x2，所需要的最小步数是>=log（x2-x1），这样如果当前步数+log（x2-x1） > 当前记录的答案，这就说明这一定不是最优
迭代加深：
#include<iostream> #include<cstdio> #include<string.h> using namespace std; int ans[105]; bool vis[100]; int n; bool dfs(int last,int lim) { bool vis[105]; memset(vis,0,sizeof(vis)); if(last == lim) { if(ans[last] == n) return 1; return 0; } for(int i=last; i>=1; i--) { for(int j=i; j>=1; j--) { int tmp = ans[i] + ans[j]; if(tmp <= n && !vis[tmp]) { if(tmp < ans[last]) return 0; vis[tmp] = 1; ans[last+1] = tmp; if(dfs(last+1,lim)) return 1; } } } return 0; } int main() { while(~scanf("%d",&n) && n) { ans[1] = 1; for(int i=1; i<=100; i++) { if(dfs(1,i)) { for(int j=1; j<=i; j++) { printf(j == i?"%d\n":"%d ",ans[j]); } break; } } } }
dfs剪枝：
#include<iostream> #include<cstdio> #include<string.h> using namespace std; int ans[105]; int t_ans[105]; int b[105]; bool vis[100]; int n,m; void init() { m = n; b[n] = 0; t_ans[1] = 1; for(int i=n-1;i>=1;i--) { b[i] = b[min(i+i,n)] + 1; } } void dfs(int last) { bool vis[105]; memset(vis,0,sizeof(vis)); if(last + b[t_ans[last]] > m)return; if(t_ans[last] == n) { if(last <= m) { m = last; for(int i=1;i<=last;i++) { ans[i] = t_ans[i]; } } return; } for(int i=last; i>=1; i--) { for(int j=i; j>=1; j--) { int tmp = t_ans[i] + t_ans[j]; if(tmp <= n && !vis[tmp]) { if(tmp < t_ans[last]) return; vis[tmp] = 1; t_ans[last+1] = tmp; dfs(last+1); } } } return; } int main() { while(~scanf("%d",&n) && n) { init(); dfs(1); for(int i=1;i<=m;i++) { printf(i == m?"%d\n":"%d ",ans[i]); } } }
Addition Chains POJ - 2248 （bfs / dfs / 迭代加深）
原文：https://www.cnblogs.com/iwannabe/p/10587908.html
