题目描述题目要求构造一个加法链即一个以111开头、以nnn结尾的严格递增序列且序列中每个元素都是它前面某两个元素之和这两个元素可以是同一个。要求链的长度最短。若有多个解输出任意一个。输入格式输入包含多个测试用例每行一个整数nnn1≤n≤100001 \le n \le 100001≤n≤10000。输入以n0n 0n0结束。输出格式对于每个nnn输出一行包含加法链中的数字用空格分隔。样例输入5 7 12 15 77 0输出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题目分析本题的核心是使用迭代加深搜索IDDFS\texttt{IDDFS}IDDFS寻找最短加法链。搜索策略从111开始依次确定下一个数。每个新数必须是已有某两个数之和可以是同一个。使用深度限制从可能的最小深度开始递增直到找到解。剪枝若当前深度下剩余步数内最大可能达到的值仍小于nnn则剪枝即使用当前最大值每次翻倍最大可能值 当前值×2剩余步数\times 2^{剩余步数}×2剩余步数。复杂度分析n≤10000n \le 10000n≤10000深度不超过202020搜索空间可控。代码实现// Addition Chains// UVa ID: 529// Verdict: Accepted// Submission Date: 2016-12-21// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intpart[40]{1},bestPart[40]{1},maxDepth,n;voiddfs(intdepth){if(depthmaxDepth){for(intidepth-1;i0;i--){intnextpart[depth-1]part[i];if(nextn){part[depth]next;if(part[depth]nmaxDepthdepth){memcpy(bestPart,part,sizeof(part));maxDepthdepth;}for(intjdepth1;jmaxDepth;j)next*2;if(nextn)dfs(depth1);}}}}intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);while(cinn,n0){if(n1)maxDepth0;elsemaxDepth20;dfs(1);for(inti0;imaxDepth;i){if(i0)cout ;coutbestPart[i];}cout\n;}return0;}