一. intro

1
对应本书第一章。

0.简介

https://raw.githubusercontent.com/applenob/algorithm_note/master/res/cover.jpg

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

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

1.intro

笔记

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

python官方文档关于operator的表格

https://raw.githubusercontent.com/applenob/algorithm_note/master/res/table1.png

https://raw.githubusercontent.com/applenob/algorithm_note/master/res/table2.png
两个不错的学习链接:

作业

作业链接

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

https://raw.githubusercontent.com/applenob/algorithm_note/master/res/Halfadder.gif

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))} $$
https://raw.githubusercontent.com/applenob/algorithm_note/master/res/Fulladder.gif

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