有理数树
题目描述
二叉树指的是一种树形结构，它的每个结点有至多两个子节点。
现在有一个由有理数组成的无穷二叉树形状如下：
1/1 ______|______ | | 1/2 2/1 ___|___ ___|___ | | | | 1/3 3/2 2/3 3/1
在p/q结点位置的左子节点为p/(p+q)，右子结点为(p+q)/q
现在已知所有有理数在这个二叉树内都存在，且仅出现一次。我们按照树的层次进行遍历，可以得到一个序列1/1, 1/2, 2/1, 1/3, 3/2, 2/3, 3/1, ...
请你解决以下问题：对于给定一个有理数，求它在上述序列中的位置
关于输入
首先输入一个整数T，表示测试样例的数目。
接下来是T行，每行包含两个整数，分别代表有理数的分子与分母
关于输出
对于每一行输入，请输出有理数在序列中的位置，位置从1开始计数,并且结果保证是在int的范围内
例子输入
2 1 2 3 2
例子输出
2 5
提示信息
可以使用递归解法
解题分析
注意到，子左节点的位置是父节点位置的两倍，子右节点的位置是父节点位置的两倍加一，故写出递归程序。
代码分析
#include <iostream>
using namespace std;
int f(int p,int q){
if(p==1 && q==1) return 1;
else if(p/q){
p=p-q;
return 2*f(p,q)+1;
}
else{
q=q-p;
return 2*f(p,q);
}
}
int main() {
int T; cin>>T;
while(T--){
int p,q;
cin>>p>>q;
cout<<f(p,q)<<endl;
}
return 0;
}
