半数集问题半数集问题.ppt

半数集问题 问题描述 例如，set(6)={6,16,26,126,36,136}。半数集 set(6)中有6 个元素。 注意半数集是多重集。 输入：整数n 输出：半数集元素个数 对问题的理解与分析 第一次改进后仍存在缺点 观察发现的几个特点 1 相同的树形结构： 每两相邻规模的树拓扑结构完全相同，当规模递增２后，树的拓扑结构才改变 　猜想１：奇数的半数集合元素个数等于其前一个偶数的半数集合元素个数，即 f(n)=f(n-1) (n%2=1) 这样一来，奇数的半数集合元素个数问题转化为了求偶数的半数集合元素个数问题。 2 相似的树形结构 3 子结构的组合 观察发现的几个特点 1 相同的树形结构 2 相似的树形结构 3 子结构的组合 猜想2 ：偶数的半数集合元素个数等于其前一个数的半数集合元素个数加上其半数的半数集合元素个数 f(n)=f(n/2)+f(n-1) (n%2=0) 等价公式的证明 第二次改进后的算法 int comp(int n) { int i; for( i=2;i=n;i++) { if(i%2==0) a[i]=a[i/2]+a[i-1]; else a[i]=a[i-1]; } return a[n]; } 时间复杂度O（n） * 问题描述 给定一个自然数n，由n开始可以依次产生 半数集set(n)中的数如下。 (1) n∈set(n)； (2) 在n的左边加上一个自然数，但该自然数不能超过最近添加的数的一半； (3) 按此规则进行处理，直到不能再添加自然数为止。 6 1 2 3 1 1 求解半数集元素的个数就相当于求解以元素n为根节点的树的节点总数 {6} {6, } {6,16,26,36, } 16,26,36 126,136 令f(n)表示以n为树根的节点总数 f(n)=1+ 据此，可很容易设计出求f(n)的递归算法如下：int comp(int n) { int ans=1； if(n1) for(int i=1；i=n/2；i++) ans+=comp(i)； return ans；} 对于此递归过程，是存在有缺陷的，即有很多的重复子问题计算。比如说：当n=4时，f(4)=1+f(1)+f(2)，而f(2)=1+f(1)，因此，在计算f(2)的时候又要重复计算一次f(1)。更进一步，当n较大时，类似的重复子问题计算将会变得非常多。 显然算法时间复杂度太高，至少是 改进的递归算法 可以对如上的递归算法进行改进，用数组来存储已计算过的子问题结果，就可以避免重复，提高算法效率。添加一个数组 a 用于保留计算过程中小规模问题的结果, a[ i ]就代表半数集set( i )中元素的个数。改进的递归算法如下：int comp(int n){ int ans=1； if(a[n]0) //避免重复计算的判断语句（在主函数中将数组a的元素全部初始化为0） return a[n]； //否则递归计算 for(int i=1;i=n/2;i++) ans+=comp(i)； //保存，在下次遇到时可直接使用，避免再次计算 a[n]=ans； return ans；} 1 2 3 4 5 1 1 1 2 1 2 1 1 6/7 1 2 3 1 1 8/9 1 2 3 1 1 4 1 2 1 1 2 3 4 5 1 1 1 2 1 2 1 1 6/7 1 2 3 1 1 8/9 1 2 3 1 1 4 1 2 1 *