Stern–Brocot tree

Правка en1, от 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?

Теги binary tree

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский Butskhrikidze 2019-02-27 12:29:16 184
en1 Английский Butskhrikidze 2019-02-27 12:28:48 760 Initial revision (published)