3500: 1443：【例题4】Addition Chains

内存限制：128 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：10 解决：5

题目描述

给定一个目标数字 n，需要找到一个数列 a0,a1,…,am，使得 a0=1，am=n，并且每一个 ak(1≤k≤m) 都可以通过数列中之前的两个元素相加得到。程序需要找到这样的数列，并输出其中一个满足条件的数列。

输入

每行输入一个正整数 n，输入以 0 结束。

输出

对于每组数据，输出满足条件的长度最小的数列。

样例输入 复制 

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

来源/分类

提交提交记录统计露一手!