The Stern-Brocot Number System

The Stern-Brocot Number System

时间: 1ms        内存:64M

描述:

The Stern-Brocot tree is a beautiful way for constructing the set of
all non-negative fractions $ {m \over n}$ where m

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

$ \left(\vphantom{ {0 \over 1}, {1 \over 0} }\right.$$ {0 \over 1}$,$ {1 \over 0}$$ \left.\vphantom{ {0 \over 1}, {1 \over 0} }\right)$
and then repeat the following operation as many times as desired:

Insert
$ {{m+m'} \over {n+n'}}$ between two adjacent fractions

$ {m \over n}$ and

$ {m' \over n'}$ .

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

$ {0 \over 1}$ and
$ {1 \over 0}$,

$\displaystyle {0 \over 1}$,$\displaystyle {1 \over 1}$,$\displaystyle {1 \over 0}$

and the next gives two more:

$\displaystyle {0 \over 1}$,$\displaystyle {1 \over 2}$,$\displaystyle {1 \over 1}$,$\displaystyle {2 \over 1}$,$\displaystyle {1 \over 0}$

The next gives four more:

$\displaystyle {0 \over 1}$,$\displaystyle {1 \over 3}$,$\displaystyle {1 \over 2}$,$\displaystyle {2 \over 3}$,$\displaystyle {1 \over 1}$,$\displaystyle {3 \over 2}$,$\displaystyle {2 \over 1}$,$\displaystyle {3 \over 1}$,$\displaystyle {1 \over 0}$

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

$ {1 \over 1}$
down to
$ {1 \over 2}$, then right to
$ {2 \over 3}$,
then right to
$ {3 \over 4}$, then left to
$ {5 \over 7}$.
We can consider LRRL to be a
representation of
$ {5 \over 7}$. Every positive fraction gets represented in this
way as a unique string of L's and R's.

Well, almost every fraction.
The fraction
$ {1 \over 1}$ 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;
}

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

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注