题目描述
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:
输入
暂无
输出
暂无
样例输入
5 7
878 323
1 1
样例输出
LRRL
RRLRRLRLLLLRLRRR
参考代码
#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;
}
解析
暂无