主题：[原创]算法学习笔记。
林杰杰
[专家分：8970] 发布于 2008-01-16 22:17:00
本版人气实在不咋滴。。。
俺把俺学习《算法设计与分析基础》的一些笔记发在这里吧。哈哈，没人看到，不用怕被笑。
这本书才开始读。
只看了前面几个章节，同时把里面提到的算法用Python实现出来。放在这里，希望对大家有用。
同时，本帖锁住，是为了内容的连贯性。反正看样子一年半载的也沉不下去。。。。
回复列表 （共4个回复）
沙发
林杰杰 [专家分：8970] 发布于 2008-01-16 22:20:00
蛮力法
蛮力法是一种简单直接的解决问题的方法，常常直接基于问题的描述和所涉及的概念定义。
选择排序
程序代码：
# -*- coding: cp936 -*-
# S:要排序的列表
def SelectionSort(S):
if S == []:
return []
n = len(S)
i = 0
while i < n - 1:
t = i
j = i + 1
while j < n:
if S[j] < S[t]:
t = j
j += 1
S[i], S[t] = S[t], S[i]
i += 1
return S
if __name__ == "__main__":
S = []
print S
S = SelectionSort(S)
print S
S = [89, 45, 68, 90, 29, 34, 17]
print S
S = SelectionSort(S)
print S
冒泡排序
程序代码：
# -*- coding: cp936 -*-
# S: 要排序的序列
def BubbleSort(S):
if S == []:
return []
n = len(S)
i = 0
while i < n - 1:
j = i + 1
flag = False
while j < n:
if S[i] > S[j]:
S[i], S[j] = S[j], S[i]
flag = true
j += 1
if flag:
return S
i += 1
return S
if __name__ == "__main__":
S = []
print S
S = SelectionSort(S)
print S
S = [17, 29, 34, 45, 68, 189, 90]
print S
S = SelectionSort(S)
print S
顺序查找
程序代码：
# -*- coding: cp936 -*-
# S: 被查找的数列
# e: 要查找的元素
def SequenceSearch(S, e):
i = -1
for x in S:
i += 1
if x == e:
return i
return -1
if __name__ == "__main__":
S = [17, 29, 34, 45, 68, 189, 90]
e = 10
print SequenceSearch(S, e)
e = 17
print SequenceSearch(S, e)
e = 40
print SequenceSearch(S, e)
e = 45
print SequenceSearch(S, e)
e = 90
print SequenceSearch(S, e)
e = 100
print SequenceSearch(S, e)
板凳
林杰杰 [专家分：8970] 发布于 2008-01-16 22:20:00
蛮力字符串匹配
程序代码：
# -*- coding: cp936 -*-
# S: 被查找的数列
# e: 要查找的元素
def BruteForceStringMatch(S, P):
ns = len(S)
np = len(P)
i = 0
while i < ns - np:
j = 0
while j < np:
if S[i + j] == P[j]:
j += 1
else:
break
else:
return i
i += 1
return -1
if __name__ == "__main__":
S = "NOBODY_NOTICED_HIM"
P = "NOT"
print BruteForceStringMatch(S, P)
P = "NUT"
print BruteForceStringMatch(S, P)
最近对蛮力算法
程序代码：
# -*- coding: cp936 -*-
# 点类
class Point:
def __init__(self, x, y):
self.x = x
self.y = y
def __repr__(self):
return "[%d, %d]" % (self.x, self.y)
def __eq__(self, P):
return type(self) == type(P) and self.x == P.x and self.y == P.y
def distanceSquareWith(self, P):
return (P.x - self.x) ** 2 + (P.y - self.y) ** 2
# 要计算最近点对的点序列
def BruteForceClosestPoints(S):
n = len(S)
if n < 2:
raise "点数少于2个"
p1 = S[0]
p2 = S[1]
minDis = p1.distanceSquareWith(p2)
i = 0
while i < n - 1:
j = i + 1
while j < n:
dis = S[j].distanceSquareWith(S[i])
if dis < minDis:
p1 = S[i]
p2 = S[j]
minDis = dis
j += 1
i += 1
return [p1, p2]
# 生成随机点序列
def getRandomPoints(n):
from random import randint;
S = []
i = 0
while i < n:
x = randint(0, 20)
y = randint(0, 20)
p = Point(x, y)
j = 0
while j < i:
if p == S[j]:
break
j += 1
else:
S.append(p)
i += 1
return S
if __name__ == "__main__":
S = getRandomPoints(6)
p1, p2 = tuple(BruteForceClosestPoints(S))
print S
print "%s - %s" % (p1, p2)
3 楼
林杰杰 [专家分：8970] 发布于 2008-01-16 22:21:00
凸包
程序代码
# -*- coding: cp936 -*-
# 点类
class Point:
def __init__(self, x, y):
self.x = x
self.y = y
def __repr__(self):
return "[%d, %d]" % (self.x, self.y)
def __eq__(self, P):
return type(self) == type(P) and self.x == P.x and self.y == P.y
# 线类
class Line:
def __init__(self, p1, p2):
self.p1 = p1
self.p2 = p2
def __repr__(self):
return "[%s, %s]" % (self.p1, self.p2)
def calcPointPos(self, P):
a = self.p2.y - self.p1.y
b = self.p1.x- self.p2.x
c = self.p1.x * self.p2.y - self.p1.y * self.p2.x
return a * P.x + b * P.y - c
4 楼
林杰杰 [专家分：8970] 发布于 2008-01-16 22:21:00
接楼上的。。。居然一个函数都贴不下？
# 生成一个点序列
def getRandomPoint(n):
from random import randint
S = []
i = 0
while i < n:
x = randint(0, 20)
y = randint(0, 20)
P = Point(x, y)
j = 0
while j < i:
if P == S[j]:
break
j += 1
else:
S.append(P)
i += 1
return S
# 计算序列有凸包
def getConvexHull(S):
CH = []
n = len(S)
i = 0
while i < n:
j = i + 1
while j < n:
L = Line(S[i], S[j])
k = 0
f = ""
while k < n:
r = L.calcPointPos(S[k])
if r != 0:
if r < 0:
if f != "":
if f != "-":
break
else:
f = "-"
else:
if f != "":
if f != "+":
break
else:
f = "+"
k += 1
else:
CH.append(L)
j += 1
i += 1
return CH
if __name__ == "__main__":
n = 6
S = getRandomPoint(n)
CH = getConvexHull(S)
# 点集
print "点集："
print S
# 线段
print "线段"
print CH
我来回复
您所在位置：