2015
04-16

# Fraction Tree

Fraction Tree ,alse called Stern-Brocot Tree.It’s a beautiful way to construct the set of all nonnegative fractions.The idea is to start with irreducible fractions representing zero and infinity,
1/0                  0/1
and then between adjacent fractions n/m and n’/m’ we insert fraction (n+n’)/ (m+m’), then we obtain
1/0         1/1         0/1
Repeating the process, we get
1/0     2/1     1/1     1/2     0/1
and then
1/0  3/1  2/1  3/2  1/1  2/3  1/2  1/3  0/1
and so forth. It can be proven that every irreducible fraction appears at some iteration and no fraction ever appears twice . The process can be represented graphically:

We can,in fact,regard the Stern-Brocot Tree as a number system for representing rational numbers,because each positive,reduced fractio occurs exactly once.Let’s use the letters L and R to stand for going down to the left or right branch as we proceed from the root of the tree to a particular fraction; then a string of L’s and R’s uniquely identifies a place in the tree.For example,LRRL means that we go left from 1/1 down to 1/2,then right to 2/3,then right to 3/4,then left to 5/7.We can consider LRRL to be a representatio of 5/7. Every positive fraction gets represented in this way as a unique string of L’s and R’s.
There are two natural questios:
(1)Given positive integers m and n (m is coprime with n).what’s the string of L’s and R’s that corresponds to m/n?
(2)Given a string of L’s and R’s,what fraction corresponds to it?
Now you need to write a problem to solve them.

The first line of input contains a single integer T – a number of test cases.
Each of the next T(T <= 1000) lines begin with a integer K(which kind of probrlem),if K = 1,following two integers M and N(M,N <= 1000000).else following a string of L’s and R’s(length <= 10).

The first line of input contains a single integer T – a number of test cases.
Each of the next T(T <= 1000) lines begin with a integer K(which kind of probrlem),if K = 1,following two integers M and N(M,N <= 1000000).else following a string of L’s and R’s(length <= 10).

2
1 5 7
2 LRRL

LRRL
5 7

1. #include <stdio.h>
int main(void)
{
int arr[] = {10,20,30,40,50,60};
int *p=arr;
printf("%d,%d,",*p++,*++p);
printf("%d,%d,%d",*p,*p++,*++p);
return 0;
}

为什么是 20,20,50,40,50. 我觉得的应该是 20,20,40,40,50 . 谁能解释下？

2. Often We don’t set up on weblogs, but I would like to condition that this established up really forced me individually to do this! considerably outstanding publish