九度oj 1113

最新推荐文章于 2018-06-03 21:21:02 发布

Miya_coding

最新推荐文章于 2018-06-03 21:21:02 发布

阅读量620

点赞数

分类专栏：九度oj机试题文章标签：九度oj 机试

本文链接：https://blog.csdn.net/Miya_coding/article/details/61414126

版权

九度oj机试题专栏收录该内容

7 篇文章

订阅专栏

第一次尝试使用了递归的方法，提交后发现超时。代码如下

#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;
}