Cần giúp đỡ bài tập thuật toán tạo phân số

[ptit (time)]

[mrmike612 (minh tran)]

Duyệt cây nhị phân là ra thôi mà bạn

[Rok_Hoang (Minh Hoàng)]

Viết một hàm so sánh phân số.
Đặt L=0/1;M=1/1;R=1/0 (tổ chức cấu trúc dữ liệu là đc). Chúng ta so sánh M cho tới khi (M==input) thì thôi.
Nếu input> M thì L=M;M=M+R; => xuất ‘R’
Nếu input< M thì R=M;M=M+L; => xuất ‘L’

[Gio (Gió)]

code bài giải của mình:

import fractions
class Fraction(object):
 def __init__(self,p,q):
  g=fractions.gcd(p,q)
  self.p=p//g
  self.q=q//g
 def __str__(self): return "{0}/{1}".format(self.p,self.q)
 def __add__(self,other):
  return Fraction(self.p+other.p,self.q+other.q)
 def __eq__(self,other): return self.p==other.p and self.q==other.q
 def __lt__(self,other): return self.p*other.q<self.q*other.p
 def __gt__(self,other): return not(self==other or self<other)


def solve(p,q):
 left=Fraction(0,1)
 right=Fraction(1,0)
 goal=Fraction(p,q)
 s=''
 while True:
  mid=left+right
  #print(mid)
  if mid==goal: return s
  elif mid>goal: 
   right=mid
   s+="L"
  else:
   left=mid
   s+="R"
 return s

print(solve(8,5))