九度oj 1113

第一次尝试使用了递归的方法，提交后发现超时。代码如下 #include<stdio.h> int count(int n,int m){ int sum=0,sum1=0,sum2=0; if(n*2<=m){ sum1=count(n*2,m); } if(n*2+1<=m){ sum2=count(n*2+1,m); } sum=sum1+sum2+1; return sum; } int main(){ int n,m,sum; while(scanf("%d %d",&m,&n) != EOF){ if(n==0 && m==0) break; sum=count(m,n); printf("%d\n",sum); } return 0; } 之所以首先使用了递归的方法，是因为二叉树的特性使得它的很多操作都可以通过递归来实现。但是在本题中，由于题目规模太大，所以会导致超时。而且，本题的所有节点的值是很规律的，只需找到子树的最左子节点及最右子节点即可。递归方法在此属于多此一举。用新思路编写代码如下 #include<stdio.h> int main(){ int m,n; while(scanf("%d %d",&m,&n) != EOF){ if(m==0 && n==0) break; int num,sum,left,right; num=sum=1; left=m*2; //左孩子节点的数值 right=m*2+1; //右孩子节点的数值 while(right<=n){ //若为满二叉树，则right可以取到n num=num*2; //从节点m向下，每向下一层，节点数量翻倍 sum+=num; //将每层节点数相加，得到子节点总数 left=left*2; right=right*2+1; //最左节点和最右节点 } if(left<=n){ //不是满二叉树，right超出n的范围 sum=sum+(n-left+1); //加上最下面一层的子节点个数 } printf("%d\n",sum); } return 0; }