csu2140—A Rational Sequence（递归）

题目链接：传送门

H(1946): A Rational Sequence

Submit Page      Summary      Time Limit: 1 Sec       Memory Limit: 128 Mb       Submitted: 21       Solved: 14    

---

Description

An infinite full binary tree labeled by positive rational numbers is defined by:

The label of the root is 1/1.The left child of label p/q is p/(p+q).The right child of label p/q is (p+q)/q.

The top of the tree is shown in the following figure: A rational sequence is defined by doing a level order (breadth first) traversal of the tree (indicated by the light dashed line). So that:

F(1)=1/1,F(2)=1/2,F(3)=2/1,F(4)=1/3,F(5)=3/2,F(6)=2/3,… F(1)=1/1,F(2)=1/2,F(3)=2/1,F(4)=1/3,F(5)=3/2,F(6)=2/3,… Write a program to compute the nth element of the sequence, F(n). Does this problem sound familiar? Well it should! But we changed it a little!

Input

The first line of input contains a single integer P, (1 <= P <= 1000), which is the number of data sets that follow. Each data set should be processed identically and independently. Each data set consists of a single line of input. It contains the data set number, K, and the index, N, of the sequence element to compute (1 <= N <= 2147483647).

Output

For each data set there is a single line of output. It contains the data set number, K, followed by a single space which is then followed by the numerator of the fraction, followed immediately by a forward slash (‘/’) followed immediately by the denominator of the fraction. Inputs will be chosen so neither the numerator nor the denominator will overflow an 32-bit unsigned integer.

Sample Input

4 1 1 2 4 3 11 4 1431655765

Sample Output

1 1/1 2 1/3 3 5/2 4 2178309/1346269

解题思路：对于二叉树的结点n，左结点为2n，右结点为2n+1

对于当前给出的结点编号递归向上回到起点，然后从起点向下计算出结点的数值

额，当时竟然找了半天规律，太菜了

#include <cstdio> #include <cstring> #include <cmath> #include <iostream> #include <queue> #include <set> #include <string> #include <stack> #include <algorithm> #include <map> using namespace std; typedef long long ll; const int N = 10007; const int M = 100000000; const int INF = 0x3fffffff; const int mod = 1e9+7; const double Pi = acos(-1.0); const double sm = 1e-9; typedef pair<int,int> PA; PA getValue( int p ) { PA s; if( p == 1 ) return PA(1,1); PA t = getValue(p/2); if( p%2 == 0 ){ s.first = t.first; s.second = t.first+t.second; }else{ s.first = t.first+t.second; s.second = t.second; } return s; } int main() { int T; scanf("%d",&T); while( T-- ){ int n,m; scanf("%d%d",&n,&m); PA ans = getValue(m); printf("%d %d/%d\n",n,ans.first,ans.second); } return 0; }