学步园

转载请注明来自souldak，微博:@evagle

思路真赞

Google of Greater China Test for New Grads of 2014 Round A 第2题，题目： 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

转载请注明来自souldak，微博:@evagle

Google of Greater China Test for New Grads of 2014 Round A 第2题，题目： 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