首页 > ACM题库 > HDU-杭电 > hdu 4131 Fraction Tree待解决[解题报告]C++
2015
04-16

hdu 4131 Fraction Tree待解决[解题报告]C++

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:
Shadow

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