一. intro

Posted on | In | Visitors: 
1
对应本书第一章。

0.简介

这本书的豆瓣评分高达9.3，python作为接近算法伪码的一种脚本语言，其实用它写算法是极好的，可以将注意力集中在算法本身。
但是由于python性能的问题，用python写算法不算太主流，因此市面上介绍算法的书也多以使用c/c++或者Java居多。
这本书几乎是用python介绍算法豆瓣评分最高的一本书了，网上可以下到pdf，但最好的阅读方式是直接使用这本书的网站。这本书可以直接在网站上运行示例程序。self check的部分还有作者视频讲解，这才是编程类书籍的未来嘛！

这里我记录每章的学习笔记，同时记录每章课后作业的个人解决代码，统一使用python3。

1.intro

笔记

这章主要给python做了个简短介绍，魔术方法部分以前没有仔细学习过，看看感觉挺好用，可以让自定义的方法看起来像内建的方法。

python官方文档关于operator的表格


两个不错的学习链接：

作业

作业链接

q1 to q9

完善处理分式的Fraction类。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
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):
        # q5 检查分子分母是否都是整数
        if not isinstance(top, int) or not isinstance(bottom, int):
            raise Exception("top or bottom of Fraction is not int type!")
        # q2 初始化时直接约分
        common = gcd(top,bottom)
        self.num = top//common
        self.den = bottom//common
        

    def __str__(self):
        return str(self.num)+"/"+str(self.den)

    def show(self):
        print(self.num,"/",self.den)

    def __add__(self,other):
        # q2
        newnum = self.num*other.den + \
                 self.den*other.num
        newden = self.den * other.den
        return Fraction(newnum,newden)

    def __eq__(self, other):
        firstnum = self.num * other.den
        secondnum = other.num * self.den

        return firstnum == secondnum
    
    # q1
    def getNum(self):
        return self.num
    
    def getDen(self):
        return self.den
    
    # q3
    def __sub__(self, other):
        newnum = self.num*other.den - \
                 other.num*self.den
        newden = self.den * other.den
        return Fraction(newnum, newden)
    
    def __mul__(self, other):
        return Fraction(self.num*other.num, self.den*other.den)
    
    def __truediv__(self, other):
        return Fraction(self.num*other.den, self.den*other.num)
    
    # q4
    def __gt__(self, other): 
        if self.num*other.den > self.den*other.num:
            return True
        else:
            return False
        
    def __ge__(self, other): 
        if self.num*other.den >= self.den*other.num:
            return True
        else:
            return False
        
    def __lt__(self, other): 
        if self.num*other.den < self.den*other.num:
            return True
        else:
            return False
        
    def __le__(self, other): 
        if self.num*other.den < self.den*other.num:
            return True
        else:
            return False
        
    def __ne__(self, other): 
        if self.num*other.den != self.den*other.num:
            return True
        else:
            return False
    
    # q7
    def __radd__(self,other_int):
        """
        Python will first try (4).__add__(myobj), 
        and if that returns NotImplemented Python will check if 
        the right-hand operand implements __radd__, and if it does, 
        it will call myobj.__radd__(4) rather than raising a TypeError.
        """
        newnum = self.num + \
                 self.den*other_int
        return Fraction(newnum,self.den)
    
    # q8
    def __iadd__(self, other):
        """a = iadd(a, b) is equivalent to a += b."""
        newnum = self.num*other.den + \
                 self.den*other.num
        newden = self.den * other.den
        return Fraction(newnum, newden)
        
    # q9
    def __repr__(self):
        """
        In short, the goal of __repr__ is to be unambiguous and __str__ is to be readable.
        也就是说，__repr__是用于输出更多的关于对象的信息的，而__str__是为了print好看的。
        """
        return "num:{}, den:{}".format(self.num, self.den)
1
2
3
4
x = Fraction(1,2)
y = Fraction(2,3)
print(x+y)
print(x == y)
1
2
7/6
False
1
2
3
# q1
print(x.getNum())
print(x.getDen())
1
2
1
2
1
2
3
# q2
z = Fraction(10, 5)
print(z)
1
2/1
1
2
# q3
print(x/y)
1
3/4
1
2
3
4
5
6
# q4
print(x>y)
print(x>=y)
print(x<y)
print(x<=y)
print(x!=y)
1
2
3
4
5
False
False
True
True
True
1
2
# q5
Fraction(1.1, 2)
1
2
3
4
5
6
7
8
9
10
11
12
13
Exception                                 Traceback (most recent call last)
<ipython-input-7-49b67a4c3ca5> in <module>()
      1 # q5
----> 2 Fraction(1.1, 2)

<ipython-input-1-501ce21d5123> in __init__(self, top, bottom)
     14         # q5 检查分子分母是否都是整数
     15         if not isinstance(top, int) or not isinstance(bottom, int):
---> 16             raise Exception("top or bottom of Fraction is not int type!")
     17         # q2 初始化时直接约分
     18         common = gcd(top,bottom)

Exception: top or bottom of Fraction is not int type!
1
2
3
4
5
6
# q6
w=Fraction(1, -2)
print(w)
print(w.getNum())
print(w.getDen())
print(w>x)
1
2
3
4
-1/2
-1
2
False
1
2
# q7
print(1+x)
1
3/2
1
2
3
# q8
x += y
print(x)
1
7/6
1
2
3
# q9

print(repr(x))
1
num:7, den:6

数字电路部分：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
# 作者实现的部分
 
class LogicGate:
    """逻辑门总类"""
    def __init__(self,n):
        self.name = n
        self.output = None

    def getName(self):
        return self.name

    def getOutput(self):
        self.output = self.performGateLogic()
        return self.output


class BinaryGate(LogicGate):
    """两个输入引脚的门"""
    def __init__(self,n):
        LogicGate.__init__(self,n)

        self.pinA = None
        self.pinB = None

    def getPinA(self):
        if self.pinA == None:
            return int(input("Enter Pin A input for gate "+self.getName()+"-->"))
        else:
            return self.pinA.getFrom().getOutput()

    def getPinB(self):
        if self.pinB == None:
            return int(input("Enter Pin B input for gate "+self.getName()+"-->"))
        else:
            return self.pinB.getFrom().getOutput()
    

    def setNextPin(self,source):
        """有其他逻辑门连接该门的输入"""
        if self.pinA == None:
            self.pinA = source
        else:
            if self.pinB == None:
                self.pinB = source
            else:
                print("Cannot Connect: NO EMPTY PINS on this gate")


class AndGate(BinaryGate):
    """与门"""
    def __init__(self,n):
        BinaryGate.__init__(self,n)

    def performGateLogic(self):

        a = self.getPinA()
        b = self.getPinB()
        if a==1 and b==1:
            return 1
        else:
            return 0

class OrGate(BinaryGate):
    """或门"""
    def __init__(self,n):
        BinaryGate.__init__(self,n)

    def performGateLogic(self):

        a = self.getPinA()
        b = self.getPinB()
        if a ==1 or b==1:
            return 1
        else:
            return 0

class UnaryGate(LogicGate):
    """单个输入引脚的门"""
    def __init__(self,n):
        LogicGate.__init__(self,n)

        self.pin = None

    def getPin(self):
        if self.pin == None:
            return int(input("Enter Pin input for gate "+self.getName()+"-->"))
        else:
            return self.pin.getFrom().getOutput()

    def setNextPin(self,source):
        """有其他逻辑门连接该门的输入"""
        if self.pin == None:
            self.pin = source
        else:
            print("Cannot Connect: NO EMPTY PINS on this gate")


class NotGate(UnaryGate):
    """非门"""
    def __init__(self,n):
        UnaryGate.__init__(self,n)

    def performGateLogic(self):
        if self.getPin():
            return 0
        else:
            return 1


class Connector:
    """引线"""
    def __init__(self, fgate, tgate):
        self.fromgate = fgate
        self.togate = tgate

        tgate.setNextPin(self)

    def getFrom(self):
        return self.fromgate

    def getTo(self):
        return self.togate


def main():
    g1 = AndGate("G1")
    g2 = AndGate("G2")
    g3 = OrGate("G3")
    g4 = NotGate("G4")
    c1 = Connector(g1,g3)
    c2 = Connector(g2,g3)
    c3 = Connector(g3,g4)
    print(g4.getOutput())
    print(g4.getPin())

main()
1
2
3
4
5
6
7
8
9
10
Enter Pin A input for gate G1-->1
Enter Pin B input for gate G1-->1
Enter Pin A input for gate G2-->1
Enter Pin B input for gate G2-->1
0
Enter Pin A input for gate G1-->1
Enter Pin B input for gate G1-->1
Enter Pin A input for gate G2-->1
Enter Pin B input for gate G2-->1
1

q10

实现NAND, NOR, 和 XOR

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
# q10 

class NANDGate(BinaryGate):
    """与非门"""
    def __init__(self,n):
        BinaryGate.__init__(self,n)

    def performGateLogic(self):

        a = self.getPinA()
        b = self.getPinB()
        if a ==1 and b==1:
            return 0
        else:
            return 1
        
class NORGate(BinaryGate):
    """或非门"""
    def __init__(self,n):
        BinaryGate.__init__(self,n)

    def performGateLogic(self):

        a = self.getPinA()
        b = self.getPinB()
        if a ==0 and b==0:
            return 1
        else:
            return 0
        
class XORGate(BinaryGate):
    """异或门"""
    def __init__(self,n):
        BinaryGate.__init__(self,n)

    def performGateLogic(self):

        a = self.getPinA()
        b = self.getPinB()
        if a == b:
            return 0
        else:
            return 1

q11

实现half-adder

half adder的定义可参考wikipedia

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class InGate(UnaryGate):
    """输入门"""
    def __init__(self,n):
        UnaryGate.__init__(self,n)

    def performGateLogic(self):
        if self.getPin():
            return 1
        else:
            return 0

class HalfAdder(BinaryGate):
    
    def __init__(self, n):
        BinaryGate.__init__(self, n)
        self.i1 = InGate("I1")
        self.i2 = InGate("I2")
        self.x1 = XORGate("X1")
        self.a1 = AndGate("A2")
        c1 = Connector(self.i1, self.x1)
        c2 = Connector(self.i2, self.x1)
        c3 = Connector(self.i1, self.a1)
        c4 = Connector(self.i2, self.a1)
         
    def setNextPin(self,source):
        if self.i1.pin == None:
            self.i1.pin = source
        elif self.i2.pin == None:
            self.i2.pin = source
        else:
            print("Cannot Connect: NO EMPTY PINS on this gate")

    def getSum(self):
        return self.x1.getOutput()
    
    def getCarry(self):
        return self.a1.getOutput()
        
half_adder = HalfAdder("Half_Adder")
print(half_adder.getSum())
print(half_adder.getCarry())
1
2
3
4
5
6
Enter Pin input for gate I1-->1
Enter Pin input for gate I2-->0
1
Enter Pin input for gate I1-->1
Enter Pin input for gate I2-->0
0

上面的实现还是有些缺点，就是因为输出有两个，所以相同的输入要输两次。

q12

实现full adder

$$ S=A\oplus B\oplus
C_{in}$$
$$ {\displaystyle C_{\text{out}}=(A\cdot B)+(C_{\text{in}}\cdot
(A\oplus B))} $$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
# q12

class FullAdder(LogicGate):

    def __init__(self, n):
        LogicGate.__init__(self, n)
        self.i1 = InGate("I1")
        self.i2 = InGate("I2")
        self.i3 = InGate("I3")
        self.x1 = XORGate("X1")
        self.x2 = XORGate("X2")
        self.a1 = AndGate("A1")
        self.a2 = AndGate("A2")
        self.o1 = XORGate("O1")
        c1 = Connector(self.i1, self.x1)
        c2 = Connector(self.i2, self.x1)
        c3 = Connector(self.x1, self.x2)
        c4 = Connector(self.i3, self.x2)
        c5 = Connector(self.x1, self.a1)
        c6 = Connector(self.i3, self.a1)
        c7 = Connector(self.i1, self.a2)
        c8 = Connector(self.i2, self.a2)
        c9 = Connector(self.a1, self.o1)
        c10 = Connector(self.a2, self.o1)
         
    def setNextPin(self,source):
        if self.i1.pin == None:
            self.i1.pin = source
        elif self.i2.pin == None:
            self.i2.pin = source
        elif self.i3.pin == None:
            self.i3.pin = source
        else:
            print("Cannot Connect: NO EMPTY PINS on this gate")

    def getSum(self):
        return self.x2.getOutput()
    
    def getCarry(self):
        return self.o1.getOutput()
        
full_adder = FullAdder("Full_Adder")
print(full_adder.getSum())
print(full_adder.getCarry())
1
2
3
4
5
6
7
8
9
10
Enter Pin input for gate I1-->1
Enter Pin input for gate I2-->0
Enter Pin input for gate I3-->0
1
Enter Pin input for gate I1-->1
Enter Pin input for gate I2-->0
Enter Pin input for gate I3-->0
Enter Pin input for gate I1-->1
Enter Pin input for gate I2-->0
0