半数单集问题解析.pptVIP

1.问题描述 2.算法设计 3.代码 4. 数据输入及结果输出 半数单集问题 1.问题描述 给定一个自然数n，由n开始可以依次产生半数集set(n)中的数如下： n set(n)；(0n201) (2) 在n的左边加上一个自然数，但该自然数不能超过最近添加的数的一半； 按此规则进行处理，直到不能再添加自然数为止。 注意：该半数集不是多重集，集合中已经有的元素不再添加到集合中。 2.算法设计 算法设计：对于给定的自然数n，计算半数集set(n)中的元素个数。 这是一个典型的递归问题，通过调用自身来解决问题。 递归有两个关键： 退出递归的条件 递归的层次问题 在这个问题中，要算出set(n)的元素个数，需要先算出 set(1) 到 set(n/2),就形成了递归关系。 1 1 1 2 1 1 1 4 3 2 1 1 1 3 2 1 1 2 1 2 1 1 9 6 5 4 3 2 1 2.算法设计 在本题中仅是计算元素的个数，例如：set(6)={6,16,26,126,36,136}。 6 16 26 126 36 136 给定的最初的一个自然数6，元素个数为1 进入递归函数：在6的左边加上一个自然数，这个自然数的值0n=3，也就是说，这个自然数可选1,2,3。本次递归选1 ，由于1/2=0，所以不进入下次递归，元素个数加1 。 继续进行循环，6左边的自然数为2，得到26，由于2/2=1，所以进行递归，元素个数加1，并且下次递归中的自然数n=1，得到126，元素个数加1 ，然后退出这次递归。 继续进行循环，6左边的自然数为3，得到36，由于3/2=1，元素个数加1，进行下次递归，并且下次递归中的自然数n=1，得到136，元素个数加1。然后退出这次递归，返回到第一次递归中，第一次递归中的循环结束，程序结束。 2.算法设计 因为半数集不是多重集，所以集合中已有的元素不再重复添加到集合中去，所以题目中要排除重复问题。 由于0n201，那么0n/2 100，因此在计算的时候可能产生重复的元素是2位数。 一个两位数x重复产生的条件是，在1位数y=x%10的半数集中已经产生x，因此就有x/10 y/2 ，即2(x/10) x%10。 例如：set(24)={24,124,224,1224,324,1324,424,1424,12424,…, 1224,11224,21224,121224,31224,131224,41224,141224,241224, 1241224,…} 1+2+24 12+24 2.算法设计 3.代码 int?a[300]={0}; long?HalfSet(int?n)?? {?? ????if(a [n]0)?? ????????return?a[n];?? ????else?? ????{?? ????????a[n]=1;?? ????????for(int?i=1;i=n/2;i++)?? {?? ????????????a [n]+=HalfSet(i);? if((i10) (2*(i/10)=i%10)) a[n]-=a[i/10]; ?? }? ????????return?a[n];?? ????}?? 将数组初始化为0，来存储算出的阶段性结果 数组中每个元素不为0时，退出递归 利用递归算出半数集中set(1)到set(n/2)中的元素个数和。 剔除其中重复的元素，得到最终半数单集中的元素个数。 返回到上一次递归 int?a[300]={0}; long?HalfSet(int?n)?? {?? ????if(a [n]0)?? ????????return?a[n];?? ????else?? ????{?? ????????a[n]=1;?? ????????for(int?i=1;i=n/2;i++)?? {?? ????????????a [n]+=HalfSet(i);? if((i10) (2*(i/10)=i%10)) a [n]-=a[i/10]; ?? }? ????????return?a[n];?? ????}?? 3.代码 设T(n)为该分治法解规模为n的问题所需的计算时间，则有： 当n=1时，T(n)=O(1); 当n1时， T(n)=n/2 * T(n/2) 计算得，T(n)=2^(logn(logn-