一、迭代 #例 1：孤独的根号三 #无限接近法(这种方法对完全平方数也无法完全取到平方根） a=3 x= a/2 while abs((x+a/x)/2-x)>0.00001: x = (x+a/x)/2 print(a,"的平方根为",round((x+a/x)/2,4)) #例 2：斐波那契数列求和 #斐波那契数列：1,1,2,3,5,8,13,21.... a=b=1 sum = 0 for i in range(15): #求 15 位的和 sum = sum + a a=b b=a+b print(sum) #例 3：求 n! #n!=1*2*3*4*5*...*(n-1)*n s=1 for i in range(1,16): #求 15! s = s*i print(s) 二、递归 #例 1：求 n! #n!=1*2*3*4*5*...*(n-1)*n def fac(n): if n == 1: return 1 else: return n*fac(n-1) print(fac(15)) #求 15！ #例 2：汉诺塔问题 def hanoi(n,a,b,c): #a 起始柱,b 中间柱,c 目标柱 if n==1: print("{}->{}".format(a,c)) return else: hanoi(n-1,a,c,b) hanoi(1,a,b,c) hanoi(n-1,b,a,c) return hanoi(3,'A','B','C') #例 3：科赫雪花 import turtle as t def koch(size,n): if n==0: t.fd(size) else: for angle in [0,60,-120,60]: t.left(angle) koch(size/3,n-1) def main(n): t.setup(600,600) t.penup() t.goto(-200,100) t.pendown() t.pensize(2) koch(300,n) t.right(120) koch(300,n) t.right(120) koch(300,n) t.right(120) t.hideturtle() main(3) 三、实践与体验（深度优先搜索和广度优先搜索） 省编作业本（P31） #广度优先算法,输出站点顺序 maxn = 8 #总站点数量 a = [[0,1,0,1,0,0,0,0], [0,0,1,0,0,0,0,0], [0,0,0,0,0,1,0,0], [0,0,0,0,1,0,1,0], [0,0,1,0,0,1,0,0], [0,0,0,0,0,0,0,1], [0,0,0,0,0,0,0,1], [0,0,0,0,0,0,0,0]] #站点之间的连接关系(连通矩阵) q = [0]*200 head = tail = 0 #队首队尾初始化 f = [False]*maxn #用于站点查重 start = 0 q[tail]=[start,-1];tail+=1 #起始站点入队 f[start] = True #去重 layer_q = tail end = 7 ans = 0;flag = False #记录转车次数,达到标志记为 False while head<tail and flag==False: c = q[head][0] #当前站点出队 head += 1 #f[c] = False #清空经过标记 if layer_q == head-1: ans += 1 layer_q = tail #更新位置 for j in range(maxn): if j!=end and a[c][j]==1 and f[j]==False: #j 站点不是终点，但和 C 站点连通，并且未经过 q[tail]=[j,head-1];tail+=1 #入队 f[j]=True #标记 if j==end and a[c][j]==1: q[tail]=[j,head-1];tail+=1 #入队 flag = True break p=tail-1 s = '' while p != -1: s += str(q[p][0])+"<-" #由于在节点增加了指针域，所以可以顺序输出结果 p = q[p][1] print("换乘顺序:"+s+"共换乘:"+str(ans)+"次") #深度优先算法(求全部可行路径) maxn = 8 #总站点数量 a = [[0,1,0,1,0,0,0,0], [0,0,1,0,0,0,0,0], [0,0,0,0,0,1,0,0], [0,0,0,0,1,0,1,0], [0,0,1,0,0,1,0,0], [0,0,0,0,0,0,0,1], [0,0,0,0,0,0,0,1], [0,0,0,0,0,0,0,0]] #站点之间的连接关系 start = 0 #起始站点 end = 7 s = [] #结束站点 #存放中间经过的站点 min_ = 100 #存放最小值 s.append(0) #始发站入栈 def find(start): global end,s,min_ for i in range(maxn): if a[start][i] == 1: s.append(i) if i == end: print(s) #输出换乘顺序 if len(s)<min_: min_ = len(s) else: find(i) s.pop() find(start) print(min_-2) #输出最少换乘次数,总站点数减去起点和终点