Блог пользователя Sayakiss

Misunderstood the problem but miraculously got an AC
Автор Sayakiss, 13 лет назад, По-английски

Given a node in Stern-brocot Tree,the task is to output its path to the root.

At my first attempt to solve this problem, I glanced through the description and mistake it for Calkin-Wilf Tree(probably because I just knew Calkin-Wilf tree at that time),and I just output the path in Calkin-Wilf tree,and got an Ac.Just then I noticed the difference between the tree in my mind and the problem's.The appearance of these two trees is entirely different,but the path is the same!How it could happen?
I tried to prove the correctness of my solution,but failed at last.(I got no positive result although spending several hours on it)
can anyone explain this miracle?

The path to root of Calkin-Wilf Tree is quite simple.
a node(a,b),the father is：
(a-b,b) a>b
(a,b-a) a<b
(1,1) a==b (it's the root!)
if you are familiar with the Euclidean Algorithm,the repeated subtraction obviously can be replaced by modulo operation for efficiency.
this is my code:

  • #include<cstdio>  
  • int main()  
  • {  
  •     int a,b;  
  •     while(scanf("%d%d",&a,&b)&&(a!=1||b!=1))  
  •     {  
  •         for(;a&&b;)  
  •         {  
  •             int t;  
  •             if (a>b)  
  •             {  
  •                 t=a/b;  
  •                 if (!(a%b)) t--;  
  •                 for(int i=0;i<t;i++) putchar('R');  
  •                 a%=b;  
  •             }  
  •             else  
  •             {  
  •                 t=b/a;  
  •                 if (!(b%a)) t--;  
  •                 for(int i=0;i<t;i++) putchar('L');  
  •                 b%=a;  
  •             }  
  •         }  
  •         puts("");  
  •     }  
  • }  





    • Проголосовать: нравится
    • 0
    • Проголосовать: не нравится

    13 лет назад, # |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    The first thing you should notice is actually you have made TWO mistakes when you read the problem description in UVA, not ONE. 

    The first mistake you make is as you mentioned, the structure in the problem is a Stern-brocot Tree, not Calkin-Wilf Tree. However, there is another mistake: The task is to output its path FROM the root TO the node given.

    So if we change the problem to the Calkin-Wilf Tree I'm sure you cannot get an AC; A simple counter example is 3/2, your program will output "RL" instead of "LR";

    But two mistakes help you find the exact algorithm to solve this problem!

    To explain the algorithm, we have to analysis the structure of  Stern-brocot Tree. From the wikipedia, we can find that the most interesting property is the relationship between the tree and continued fractions.

    Every positive rational number q may be expressed as a continued fraction of the form

    What can we get from all above?

    Imagine a path from the root to a node, say "LLRRRLLLRRR", to simplify the sequence, we will write it as

    "L^2 R^3 L^3 R^3"

    The fact is for a rational number  q=[ a0 ; a1 , a2, ... , a(n-1) , 1 ], the path from the root to q is just

    "R^a0 L^a1 R^a2 L^a3.....R^a(n-2) L^a(n-1)"  (n%2==0)

    or  "R^a0 L^a1 R^a2 L^a3.....L^a(n-2) R^a(n-1)" (n%2==1)

    See Discrete Mathematics Concrete Mathematics for a proof (Chapter 4.5 and Chapter 6.7)


    Finally, the algorithm to calculate a0 ,a1,... and a(n-1) is the algorithm to solve the problem, and Believe me, it is just the algorithm you designed in your code...


    → Ответить