算法分析与设计——2.8 半数集问题

算法分析与设计——2.8 半数集问题

问题描述：给定一个自然数n，由自然数n开始可以依次产生半数集set(n)中的数如下：
                   (1)n属于set(n)
                   (2)在n的左边添加一个自然数，但该数不能超过最近添加的数的一半
                   (3)按此规则，直到不能添加为止
                   例如：set(6)={6,16,26,36,126,136}=6

算法设计：对于给定的自然数n，计算set(n)中的元素个数

输入：自然数n

输出：元素个数和元素内容

算法思想：以6为例。按照规则，新加入的数字小于等于6的一半——3。所以6进行一轮，添加了1，2，3三个数字组合为16，26，36。接下来发现只有26和36可以按照规则继续加数字。

根据规则，对每一个数n最多可以添加n/2个数字且不重复，如果把每一个自然数看作树的节点，那么对一棵树上的节点来说都有n/2个子节点。符合分治策略的使用条件。有如下递归式：