编程介的小学生 2019-12-31 01:10 采纳率: 20.5%
浏览 97

Fraction Tree 分形的问题

Problem Description
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:

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.

Input
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).

Output
For each set of data the program prints the answer.

Sample Input
2
1 5 7
2 LRRL

Sample Output
LRRL
5 7

  • 写回答

0条回答 默认 最新

    报告相同问题?

    悬赏问题

    • ¥20 iqoo11 如何下载安装工程模式
    • ¥15 flask项目,怎么使用AJAX传数据库数据到echarts图表的data里,实现异步加载数据。
    • ¥15 本题的答案是不是有问题
    • ¥15 关于#r语言#的问题:(svydesign)为什么在一个大的数据集中抽取了一个小数据集
    • ¥15 C++使用Gunplot
    • ¥15 这个电路是如何实现路灯控制器的,原理是什么,怎么求解灯亮起后熄灭的时间如图?
    • ¥15 matlab数字图像处理频率域滤波
    • ¥15 在abaqus做了二维正交切削模型,给刀具添加了超声振动条件后输出切削力为什么比普通切削增大这么多
    • ¥15 ELGamal和paillier计算效率谁快?
    • ¥15 蓝桥杯单片机第十三届第一场,整点继电器吸合,5s后断开出现了问题