30/09/2018, 18:04

bác nào giỏi thuật toán hoặc ôn thi olympic hay ACM giúp em bài này với

minh tran viết 20:07 ngày 30/09/2018

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

Minh Hoàng viết 20:16 ngày 30/09/2018

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’

Gió viết 20:10 ngày 30/09/2018

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))
Bài liên quan
0