Problem3209--加法链

3209: 加法链

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 0  Solved: 0
[Status] [Submit] [Creator:]

Description

对于整数n的一个加法链是指存在一个整数序列有如下四种属性：
①a0=1
②am=n
③a0<a1<a2...<am-1<am
④对于任意的K(1≤K≤m)存在两个整数(可是是相同的两个整数也可以是不同的)i和j(0≤i,j≤k-1),满足ak=ai+aj
给定一个整数n,你的任务是为n构建一个最小长度的加法链，如果有多组满足条件的解， 优先选择字典序较大的序列。

Input

输入包含多组测试数据，对于每组测试数据是一个整数n，1≤n≤100，当输入为0的时候表示输入结束

Output

对于每组测试用例，输出满足要求的整数序列，数字之间用一个空格隔开。

Sample Input Copy 

5
7
12
15
77
0

Sample Output Copy 

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

Source/Category

迭代加深搜索 level8 
[Submit] [Status]