算法分析与设计PPT03-递归与分治 - 9 半数集问题.ppt

1、3.2.8 半数集问题半数集问题给定一个自然数给定一个自然数n，由，由n开始可以依次产生半数集开始可以依次产生半数集set(n)中的数如下。中的数如下。(1)n set(n)；(2)在在n的左边加上一个自然数，但该自然数不能超过最近的左边加上一个自然数，但该自然数不能超过最近添加的数的一半；添加的数的一半；(3)按此规则进行处理，直到不能再添加自然数为止。按此规则进行处理，直到不能再添加自然数为止。例如，例如，set(6)=6，16，26，126，36，136。半数半数集集set(6)中有中有6个元素。个元素。l 注意半数集是注意半数集是多重集多重集。对于给定的自然数对于给定的自然数n，编程计

2、算半数集，编程计算半数集set(n)中的元素个数中的元素个数。13.2.8 半数集问题半数集问题第一次半数集第一次半数集112212312412512612忽略原始数字忽略原始数字1212345612131424，1241525，1251626，12636，1362数字数字12为例为例设设set(n)中的元素个数为中的元素个数为 ，则显然有：，则显然有：)(nf2/1)(1)(niifnf算法算法3.12 计算半数集问题的递归算法计算半数集问题的递归算法int comp(int n)int ans=1;if(n1)for(int i=1;i0)return an;/已经计算已经计算for(int i=1;i=n/2;i+)ans+=comp(i);an=ans;/保存结果保存结果return ans;4