The Stern-Brocot Number System

code

6 年前

时间： 1ms 内存：64M

描述：

The Stern-Brocot tree is a beautiful way for constructing the set of
all non-negative fractions where m

and n are relatively prime. The idea is to start with two fractions

,
and then repeat the following operation as many times as desired:

Insert
between two adjacent fractions

and

.

For example, the first step gives us one new entry between

and
,

,,

and the next gives two more:

,,,,

The next gives four more:

,,,,,,,,

The entire array can be regarded as
an infinite binary tree structure whose top levels look like this-

This construction preserves order, and thus we cannot possibly get the same
fraction in two different places.

We can, in fact, regard the Stern-Brocot tree as a number system for
representing rational numbers,
because each positive, reduced fraction occurs exactly once. Let us use
the letters ``L'' and ``R'' to stand for going
down 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

down to
, then right to
,
then right to
, then left to
.
We can consider LRRL to be a
representation of
. Every positive fraction gets represented in this
way as a unique string of L's and R's.

Well, almost every fraction.
The fraction
corresponds to
the empty string.
We will denote it by I, since that looks something
like 1 and stands for ``identity."

In this problem, given a positive rational fraction,
represent it in the Stern-Brocot number system.

输入：

The input file contains multiple test cases. Each test case consists of a line containing two positive integers m and n, where m and n are relatively prime. The input terminates with a test case containing two 1's for m and n, and this case must not be processed.

输出：

For each test case in the input file, output a line containing the representation of the given fraction in the Stern-Brocot number system.

示例输入：

5 7
878 323
1 1

示例输出：

LRRL
RRLRRLRLLLLRLRRR

提示：

参考答案（内存最优[752]）：

#include <stdio.h>
int main()
{
    long long n,m,nl,ml,nr,mr,n0,m0;
    while(scanf("%lld%lld",&m,&n)!=EOF)
    {
        if(n==1&&m==1)
            break;
        n0=m0=1;
        ml=nr=0;
        mr=nl=1;
        while(!(m==m0&&n==n0))
        {
            if(m0*n<n0*m)
            {
                printf("R");
                ml=m0;
                nl=n0;
                m0=m0+mr;
                n0=n0+nr;
            }
            else
            {
                printf("L");
                mr=m0;
                nr=n0;
                m0=m0+ml;
                n0=n0+nl;
            }
        }
        printf("\n");
    }
    return 0;
}

参考答案（时间最优[0]）：

#include <stdio.h>
int main()
{
    long long n,m,nl,ml,nr,mr,n0,m0;
    while(scanf("%lld%lld",&m,&n)!=EOF)
    {
        if(n==1&&m==1)
            break;
        n0=m0=1;
        ml=nr=0;
        mr=nl=1;
        while(!(m==m0&&n==n0))
        {
            if(m0*n<n0*m)
            {
                printf("R");
                ml=m0;
                nl=n0;
                m0=m0+mr;
                n0=n0+nr;
            }
            else
            {
                printf("L");
                mr=m0;
                nr=n0;
                m0=m0+ml;
                n0=n0+nl;
            }
        }
        printf("\n");
    }
    return 0;
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。