POJ 2499 Binary Tree（水题）

【题意简述】：二叉树，根节点为（1,1），现在每个节点设为（a,b）它的左孩子是就是（a+b，b），同理右孩子就是（a，a+b）。现在已知这个节点了，求其从根节点开始经过几次向左的发展，几次向右的发展！

【思路】：我们可以通过一个逆向的思维去解决这道题，起点就是输入的数据，终点就是根节点！这个时候我们就可以从测试数据里找一些规律，我们不难发现使用辗转相除就能解决这个问题！（其实我最开始用的还是辗转相减，导致我TLE，但仔细一想便不难得知，辗转相减与辗转相除，本就是“一家”啊！！经过改正后，顺利AC！）

详见代码：

//228K 16Ms
#include<iostream>
using namespace std;

int main()
{
	int t,a,b;
	int suml,sumr;
	cin>>t;
	int count = 1;
	while(t--)
	{
		cin>>a>>b;
		suml = 0,sumr = 0;
		while(1){
			if(a>b){
				suml+=a/b;
				a = a % b;
				//循环终止条件！ 
				if(a == 0){
					suml = suml-1;
					break;
				}
			}
			else
			{
				sumr+=b/a;
				b = b % a;
				if(b == 0)
				{
					sumr = sumr-1;
					break;
				}
			}
		}
		cout<<"Scenario #"<<count<<":"<<endl;
		cout<<suml<<" "<<sumr<<endl;
		cout<<endl;
		count++;
	}
	return 0;
}

POJ 2499 Binary Tree（水题）,布布扣,bubuko.com

POJ 2499 Binary Tree（水题）

原文：http://blog.csdn.net/u013749862/article/details/22754815