【题目链接】

ybt 1443：【例题4】Addition Chains
OpenJudge 百练 2248:Addition Chains
洛谷 UVA529 Addition Chains
在洛谷中无法直接提交，还需要到原网站注册账号才能提交。也可以选择在vjudge中提交。
vjudge uva529
注：以UVA529题目为准，$1\le n\le 10000$

【题目考点】

1. 迭代加深搜索

【解题思路】

给定一个序列，一开始只有一个1。两次从序列中选择数（可以两次选出同一个数），将两数相加得到的数加入序列。问要想在序列中得到数值$n$，序列的最小长度是多少。

示例
长为1的序列：1
长为2的序列：1 2
长为3的序列：1 2 4; 1 2 3
长为4的序列：1 2 3 4; 1 2 3 5; 1 2 3 6; 1 2 4 5; 1 2 4 6; 1 2 4 8

下一个生成的数，是由序列中已有的数决定的。因此搜索的状态必须包含已确定的整数构成的序列。
每次搜索，决定序列中的一个数。我们可以让每次生成的数一定大于这个序列中的最后一个数，保证序列是升序的，这样可以避免重复搜索到相同的序列。
将每个序列当做一个结点，当前序列增加一个数后变为下一个序列，视为在两个结点之间有一条边，这就是本问题的解空间树。

该题要找到序列长度最短的，序列的最后一个数（也就是最大值）为n的序列。在解空间树中，每经过一条边，序列的长度加1。
因此该问题在解空间树上可以描述为：从树的根结点出发，经过最短的路径找到最大值为n的结点。
最短路径问题，可以使用广搜（BFS）或迭代加深搜索（IDDFS）完成。
该问题的状态为一个整数序列，占用内存空间较大。广搜对空间占用较大，使用广搜可能会空间超限。因此使用迭代加深搜索解决本问题。

主函数中每次搜索逐次增加最大搜索层数。每趟搜索过程中，限定最大的搜索层数，如果搜索层数达到最大搜索层数，则结束搜索。
搜索到某一层时，当前序列为$v$，有$s$个元素，各元素为$v_0,v_1,...,v_{s-1}$，是升序序列。在序列中两次选出的元素加和可以得到下一个要添加进序列中的元素。
（如果使用vector保存$v$序列，那么$v_{s-1}$就是v.back()）。
为了保证序列是升序的，新的元素必须满足大于$v_{s-1}$。为了能够更加容易满足这一点，应该从后向前遍历：$i$从$s-1$循环到0，取出第一个元素$v_i$；第二个元素下标$j$应该从$i$开始，$j$从$i$循环到0，取出第二个元素$v_j$。
如果发现$v_i+v_j\le v_{s-1}$，那么此次j的循环应该结束（因为后面的$v_j$会更小，都会满足$v_i+v_j\le v_{s-1}$）（优化搜索顺序）
同时新添加的元素不能大于$n$，因为目标就是在序列中得到数值$n$。如果新的元素已经大于$n$，后面生成的数都会大于n，不会得到数值n。（可行性剪枝）
在确定第$k$个数前，已经确定的数有$k-1$个，当前这一趟搜索的最大搜索层数为$maxDep$，也就是这一趟搜索得到的序列都有$maxDep$个数，看是否存在第$maxDep$个数是$n$的情况。接下来还需要生成$maxDep-(k-1)=maxDep-k+1$个数字
对于当前序列，最大的数是$v_{s-1}$
后面第1个生成可以得到的最大数为$2v_{s-1}$
后面第2个生成可以得到的最大数为$2^2{v}_{s-1}$
后面第3个生成可以得到的最大数为$2^3{v}_{s-1}$
…
后面第$maxDep-k+1$个生成可以得到的最大数为$2^{maxDep-k+1}{v}_{s-1}$
，该数值必须大于等于n。
因此如果$2^{maxDep-k+1}{v}_{s-1}<n$，则后面即便每次都添加可能添加的最大的数，得到的第$maxDep$个数的最大值也小于$n$，即第maxDep个数字不可能为n，因此可以剪枝。（最优性剪枝）
当已经确定了$maxDep$个数后，看序列末尾数值$v_{s-1}$是否为$n$，如果是，则找到解，输出整个序列。并记录已找到解，只要找到解，就结束迭代加深搜索。

【题解代码】

解法1：迭代加深搜索

#include <bits/stdc++.h>
using namespace std;
int n;
bool hasAns;
vector<int> v;//是否已找到解 
//确定序列中第k个数字，序列中最多有maxDep个数字 
void dfs(int k, int maxDep) 
{
	if(k > maxDep)
	{
		if(v.back() == n)//如果最后一个数字（最大数字）为n，则找到解 
		{
			cout << v[0]; 
			for(int i = 1; i < v.size(); ++i)//输出序列，UVA要求末尾不能有空格。 
				cout << ' ' << v[i];
			cout << '\n';
			hasAns = true;
		}
		return;
	}
	if(hasAns)//如果已经找到解，就返回 
		return;
	if(v.back()*(1<<maxDep-k+1) < n)//每多一个数字，其最大值为前一个数字的2倍。后面还有maxDep-k+1个数字，所能达到的最大值为 v.back()*2^{maxDep-k+1}，该值必须>=n才可能达到n。 
		return;
	for(int i = v.size()-1; i >= 0; --i)
	{
		for(int j = i; j >= 0; --j)
		{
			if(v[i]+v[j] <= v.back())//保证v中是升序序列 
				break;
			if(v[i]+v[j] <= n)
			{
				v.push_back(v[i]+v[j]);
				dfs(k+1, maxDep);
				v.pop_back();
			}
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	while(cin >> n && n != 0)
	{
		hasAns = false;
		for(int d = 1; !hasAns; d++)
		{
			v.clear();
			v.push_back(1);
			dfs(2, d);//第1个数已经确定了，从确定第2个数开始 
		} 
	}
	return 0;
}