A61818. $信息学奥赛练习题：Addition Chains【$

编程题

知识点

多组输入剪枝优化迭代加深搜索数列构造

题目描述

信息学奥赛练习题：Addition Chains 【题目描述】 已知一个数列a 0,a 1 \dots\dotsa m ，其中a 0 =1,a m =n; a 0 <a 1 <a 2 <\dots\dots<a m - 1 <a m 。对于每个k(1<=k<=m)满足a k =a i +a j(0<=i,j<=k - 1),这里i与j可以相等。 现给定n的值，要求m的最小值（并不要求输出）及这个数列的值（可能存在多个数列，只输出任意一个满足条件的就可以）。 【输入】 多组数据，每行给定一个正整数n。输入以0结束。 【输出】 对于每组数据，输出满足条件的长度最小的数列。 【输入样例】 571215770 【输出样例】 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

上一题去做题下一题