The Stern-Brocot Number System
时间: 1ms 内存:64M
描述:
The Stern-Brocot tree is a beautiful way for constructing the set of
all non-negative fractionswhere 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;
}
题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。