《Python数据结构与算法分析》第一章课后习题

Introduction

最近开始学数据结构，打算用python作为语言，看的书是米勒和戴维的《Python数据结构与算法分析》。目前大三，希望能一个月速成，奥利给！！注意到课本中的练习题没有参考答案，我自己写了一份放到这上面，更详细的代码在我的github：https://github.com/Yunzz-goon/PythonForDataStructure
欢迎大家一起交流！！！
第一章还没开始讲算法，先介绍了一下python基本的操作。

练习题

1. 实现简单的方法getNum 和getDen ，它们分别返回分数的分子和分母。

class Fractionn:
    def __init__(self,top,bottom):
        self.fenzi=top
        self.fenmu=bottom
    def __getfenzi__(self):
        print(self.fenzi)
    def __getfenmu__(self):
        print(self.fenmu)

myf=Fractionn(2,5)
myf.__getfenzi__()
myf.__getfenmu__();

2. 如果所有分数从一开始就是最简形式会更好。修改Fraction 类的构造方法，立即使用最大公因数来化简分数。注意，这意味着__add__
   不再需要化简结果。

#q2 & q3 #我们还没有对输入的分母进行error报错---需要注意输入Fraction(a,b),b不能是0

class Fraction:
    def __init__(self,top,bottom):
        n=gcd(top,bottom)
        self.fenzi=top//n
        self.fenmu=bottom//n
        
    def __show__(self):
        print(self.fenzi,'/',self.fenmu)
        
        
    def __add__(self,self2):
        newfenzi=self.fenzi*self2.fenmu+self.fenmu*self2.fenzi
        newfenmu=self.fenmu*self2.fenmu
        Neww=Fraction(newfenzi,newfenmu)
        return Neww
    
    def __sub__(self,self2):
        newfenzi=self.fenzi*self2.fenmu-self.fenmu*self2.fenzi
        newfenmu=self.fenmu*self2.fenmu
        Neww=Fraction(newfenzi,newfenmu)
        return Neww
    
    def __mul__(self,self2):
        newfenzi=self.fenzi*self2.fenzi
        newfenmu=self.fenmu*self2.fenmu
        Neww=Fraction(newfenzi,newfenmu)
        return Neww
        
    
    def __truediv__(self,self2):
        if self2.fenzi==0:
            print("error, contradictory to divising rule, self2 can not be zero.")
            Neww=Fraction(9999999,1)
        else:
            newfenzi=self.fenzi*self2.fenmu
            newfenmu=self.fenmu*self2.fenzi
            Neww=Fraction(newfenzi,newfenmu)
        return Neww
    
    def gcd(m,n):
        while m%n != 0:
            oldm=m
            oldn=n
            m=oldn
            n=oldm%oldn
        return n

        
if __name__=="__main__":
    f=Fractionn(2,10)
    ff=f.__str__()
    print(ff)
    f1=Fractionn(2,10)
    f2=Fractionn(4,-8)
    f1.__add__(f2)
    f1.__sub__(f2)
    f1.__mul__(f2)
    f1.__truediv__(f2)

3. 实现下列简单的算术运算: sub 、mul 和__truediv__ 。(我把第二问第三问写一起了，第三问答案见2. )
4. 实现下列关系运算：gt 、ge 、lt 、le 和__ne__ 。

#q4 
#我们还没有对输入的分母进行error报错---需要注意输入Fraction(a,b),b不能是0
def gcd(m,n):
    while m%n != 0:
        oldm=m
        oldn=n
        m=oldn
        n=oldm%oldn
    return n

class Fraction:
    def __init__(self,top,bottom):
        n=gcd(top,bottom)
        self.fenzi=top//n
        self.fenmu=bottom//n
        
    def __str__(self):
        return str(self.fenzi)+'/'+str(self.fenmu)
        
        
    def __show__(self):
        print(self.fenzi,'/',self.fenmu)
        
    
    def __gt__(self,self2):
        if self.fenzi*self2.fenmu > self.fenmu*self2.fenzi:
            print('%s is greater' %self.__str__())
        else:
            print('%s is not greater' %self.__str__())

    def __ge__(self,self2):
        if self.fenzi*self2.fenmu >= self.fenmu*self2.fenzi:
            print('%s is greater or equal' %self.__str__())
        else:
            print('%s is not greater or equal' %self.__str__())
   
    def __lt__(self,self2):
        if self.fenzi*self2.fenmu < self.fenmu*self2.fenzi:
            print('%s is less' %self.__str__())
        else:
            print('%s is not less' %self.__str__())    
            
    def __le__(self,self2):
        if self.fenzi*self2.fenmu <= self.fenmu*self2.fenzi:
            print('%s is less or equal' %self.__str__())
        else:
            print('%s is not less or equal' %self.__str__())  
    
    def __ne__(self,self2):
        if self.fenzi*self2.fenmu == self.fenmu*self2.fenzi:
            print('%s is equal' %self.__str__())
        else:
            print('%s is not equal' %self.__str__()) 
            
    if __name__=="__main__": 
        f=Fraction(2,10)
        ff=f.__str__()
        print(ff)
        f1=Fraction(2,10)
        f2=Fraction(4,8)
        __gt__(f1,f2)
        __ge__(f1,f2)
        __lt__(f1,f2)
        __le__(f1,f2)
        __ne__(f1,f2)

5. 修改Fraction 类的构造方法，使其检查并确保分子和分母均为整数。如果任一不是整数，就抛出异常。

#q5
class Fractionn:
    def __init__(self,top,bottom):
        if isinstance(top,int) and isinstance(bottom,int):
            self.fenzi=top
            self.fenmu=bottom
        else:
            print("error")

f1=Fractionn(1.1,10)

6 .我们假设负的分数是由负的分子和正的分母构成的。使用负的分母会导致某些关系运算符返回错误的结果。一般来说，这是多余的限制。请修改构造方法，使得用户能够传入负的分母，并且所有的运算符都能返回正确的结果。

#q6
#我们还没有对输入的分母进行error报错---需要注意输入Fraction(a,b),b不能是0
#我们只做了一个gt的，其他的类似。
def gcd(m,n):
   while m%n != 0:
       oldm=m
       oldn=n
       m=oldn
       n=oldm%oldn
   return n

class Fractionn:
   def __init__(self,top,bottom):
       n=gcd(top,bottom)
       self.fenzi=top//n
       self.fenmu=bottom//n
       
   def __str__(self):
       return str(self.fenzi)+'/'+str(self.fenmu)
       
       
   def __show__(self):
       print(self.fenzi,'/',self.fenmu)
       
   def __gt__(self,self2):
       if [x>0 for x in [self.fenmu, self2.fenmu]] or [x<0 for x in [self.fenmu, self2.fenmu]]:
           if self.fenzi*self2.fenmu > self.fenmu*self2.fenzi:
               print('%s is greater' %self.__str__())
           else:
               print('%s is not greater' %self.__str__())
       else:
           if self.fenzi*self2.fenmu < self.fenmu*self2.fenzi:
               print('%s is greater' %self.__str__())
           else:
               print('%s is not greater' %self.__str__())
               
    
if __name__=="__main__":
   f=Fractionn(2,10)
   ff=f.__str__()
   print(ff)
   f1=Fractionn(2,10)
   f2=Fractionn(4,-8)
   f1.__gt__(f2)

Python易错总结：

1. Python 对缩进非常严格，目前我记住的一般规律：在冒号的下一行一定要比上一行多一个tab。By the way, 很多语句都需要冒号，如if，for，while，def，class等，这个点初学者也很容易漏掉，不过漏掉冒号比较容易debug，一般会告诉你：incorrect syntax之类；但是少了缩进相对难搞，bug显示很多样。
2. Python的方法和函数都是用def定义的，具体怎么分辨我还没搞懂，不过是方法的话一般会前后加两个_，注意是前后分别两个，否则会报错：如：Fractionn() takes no arguments. (更新：今天早上看了一个blog，里面大致是介绍了方法和函数的区别。我根据自己的理解总结了一下：方法是在一个类（class）里头使用的，函数是在全局都定义好的，可以粗略理解为方法是在类里头的局部函数。)
3. 方法使用一般是数据.方法，而函数一般是函数(数据)。在类中的方法还有一点奇怪，定义的时候是两个input，如Def _Method_(a1, a2): 但在使用的时候应该是这么调用：a1._Method_(a2)。
4. 一定要记得函数或方法中的return！！！