Rational Number Tree

如下面这颗树，生成规则是，左儿子的分子和父节点一样，分母是父节点分子分母之和，右儿子的分母和父节点一样，分子是父节点分子分母之和。

这个数按层遍历得到一个序列：1/1, 1/2, 2/1 , 1/3 , 3/2, 2/3 , 3/1....

1. 现在给定其中一项，然后求出这一项在这个序列中排第几

2. 求序列的第n项，例如第二项是1/2

         1/1

    ______|______

    |           |

   1/2         2/1

 ___|___     ___|___

 |     |     |     |

1/3   3/2   2/3   3/1

 

我们先构造另一颗二进制树，

                 1

       10            11

100   101   110   111

....

即左儿子是父节点序列后面加0，右儿子是父节点序列加1，如果按层遍历然后转换成十进制数，正好是1,2,3,4,5,6,7,..... 所以这个树的值就是按层遍历时候它所在的项的位置。把两棵树结合在一起考虑，将它们的节点一一对应，那给定任何一项，我们只要找到二进制树中对应值就可以得到它是第几项了，现在怎么找呢？

看对应关系，假设父节点p/q, 题目给的树左儿子为p/(p+q),p<p+q, 右儿子，(p+q)/q，p+q>q, 所以给定m/n,如果m>n,则是父节点的右儿子，否则是父节点的左儿子。如果是右儿子，那最后一位对应1，如果是左儿子，最后一位对应0。然后求父节点，根据规则反推即可，如果是左儿子m/(n-m), 如果是右儿子，(m-n)/n。然后递归往上推，直到遇到1/1 结束，1/1是根节点对应的二进制1。其中产生的0,1串就是位置了。

例如求2/3

起始     左儿子还是右儿子   最后一位二进制     父节点

2/3                左                              0                           2/(3-2)

2/1                右                              1                           (2-1)/1

1/1                根节点                      1

这样就得到二进制110，所以它是第6项

复杂度是O(log(n)),n是第几项

 

同理如果要求出第n项的值，先将n转为二进制，然后去掉最高位的1（因为它对应根节点1/1）,然后如果是0，往左走，计算左儿子，如果是1，计算右儿子。循环一直走完所有的二进制位结束，得到的节点就是答案。

例如求第5项，11=1011，第一个1对应的是1/1

二进制位          往左或往右       父节点      节点

   1                                                                   1/1

   0                           左                   1/1            1/2

   1                           右                   1/2            3/2

   1                           右                   3/2            5/2

所以第11项对应的是5/2

复杂度是O(log(n))

因为n最大是2^64，如果用C++ ，一定要用unsigned long long，java没有这个类型，只能用BigInteger

 

package rounda;  
  
import java.io.File;  
import java.io.FileNotFoundException;  
import java.io.FileOutputStream;  
import java.io.IOException;  
import java.math.BigInteger;  
import java.util.Scanner;  
  
public class Problem3 {  
    public void input(Scanner scanner) {  
  
    }  
  
    public void output(int caseNo, FileOutputStream fop) {  
  
    }  
   
  
    public Node walk(Node father, boolean orient) {  
        if (!orient ) {  
            return new Node(father.p,father.p.add(father.q));  
               
        }else{  
            return new Node(father.p.add(father.q),  father.q);  
        }  
    }  
  
    class Node {  
        public BigInteger p;  
        public BigInteger q;  
        public Node(BigInteger p,BigInteger q){  
            this.p = p;  
            this.q=q;  
        }  
        Node(){  
              
        }  
    }  
    public  Node solve(BigInteger n){  
        if(n.compareTo(new BigInteger("1"))==0)  
            return new Node(new BigInteger("1"),new BigInteger("1"));  
        int maxbit=0;  
        for(int i=63;i>=0;i--){  
            if(n.testBit(i)){  
                maxbit=i;  
                break;  
            }  
        }  
        Node node =  new Node(new BigInteger("1"),new BigInteger("1"));  
        for(int i=maxbit-1;i>=0;i--){  
            node = walk(node,n.testBit(i));  
        }  
        return node;  
    }  
    public BigInteger solve(BigInteger p,BigInteger q){  
        Node node = new Node(p,q);  
        String s ="";  
        while(true){  
            if(node.p.compareTo(node.q)>0){  
                s+="1";  
                node.p = node.p.subtract(node.q);  
            }else{  
                s+="0";  
                node.q = node.q.subtract(node.p);  
            }  
            if(node.p.compareTo(new BigInteger("1"))==0&&  
                    node.q.compareTo(new BigInteger("1"))==0){  
                break;  
            }  
        }  
        s+="1";  
        s = new StringBuilder(s).reverse().toString();  
        BigInteger res = new BigInteger("0");  
        for(int i=0;i<s.length();i++){  
            res = res.multiply(new BigInteger("2")).add(new BigInteger((s.charAt(i)-'0')+""));  
        }  
        return res;  
    }  
    public static void main(String[] args) {  
        Scanner scanner;  
        Problem3 pr = new Problem3();  
        scanner = new Scanner(System.in);  
        int T = scanner.nextInt();  
        int count = T;  
        while (count-- > 0) {  
            int type = scanner.nextInt();  
            if (type == 1) {  
                BigInteger n = new BigInteger(scanner.next());  
                Node res = pr.solve(n);  
                System.out.println("Case #"+(T-count)+": "+res.p+" "+res.q);  
            }else{  
                BigInteger p = new BigInteger(scanner.next());  
                BigInteger q = new BigInteger(scanner.next());  
                BigInteger res = pr.solve(p,q);  
                System.out.println("Case #"+(T-count)+": "+res);  
            }  
        }  
  
    }  
  
}  

 

 

补充：综合编程 , 其他综合 ,