Duyệt cây nhị phân là ra thôi mà bạn
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’
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))
time
0 chủ đề
0 bài viết
Duyệt cây nhị phân là ra thôi mà bạn
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’
code bài giải của mình: