Stern–Brocot tree

Revision en1, by Butskhrikidze, 2019-02-27 12:28:48

see tutorial about stern-brocot's tree Tutorial. this is infinity binary tree which nodes are irreducible fractions. enumerate nodes of tree using BFS. it is given one number n and one fraction . Your task is to determine what fraction is written on the node LCA(n, ) where LCA is Lowest Common Ancestor of nodes n and . (in first case node is defined by its number and in second case node is defined by fraction). 0 < a, b < 109 and 0 < n < 1018. see example of tree what is efficient method for finding what fraction is written on the node by its fraction and vice versa?

Tags binary tree

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English Butskhrikidze 2019-02-27 12:29:16 184
en1 English Butskhrikidze 2019-02-27 12:28:48 760 Initial revision (published)