微软OneNote客户预览版学习工具下载(暂未上线):教学好帮手
857
2022-05-29
#============================================
#5.1 计算思维是什么
#============================================
#<程序: 找假币的第一种方法> by Edwin Sha
def findcoin_1(L):
if len(L) <=1:
print("Error: coins are too few"); quit()
i=0
while i
if L[i] < L[i+1]: return (i)
elif L[i] > L[i+1]: return (i+1)
i=i+1
print("All coins are the same")
return(len(L)) #should not reach this point
#<主要程序>
import random
n=int(input("Enter the number of coins >=2: "))
w_normal=random.randint(2,5)
index_faked=random.randint(0,n-1) # 0<= index <=n-1
L=[]
for i in range(0,n):
L.append(w_normal)
L[index_faked]=w_normal-1
print(L)
print("The index of faked coin:",findcoin_1(L))
#============================================
#5.2 递归(Rcurrence)的基本概念
#============================================
#<程序:递归加法>
def F(a):
if len(a) ==1: return(a[0]) #终止条件非常重要
return(F(a[1:])+a[0])
a=[1,4,9,16]
print(F(a))
#<程序:汉诺塔_递归>
count=1
def main():
n_str=input('请输入盘子个数:')
n=int(n_str)
Hanoi(n,'A','C','B')
def Hanoi(n, A, C, B):
global count
if n < 1:
print('False')
elif n == 1:
print ("%d:\t%s -> %s" % (count, A, C))
count += 1
elif n > 1:
Hanoi (n - 1, A, B, C)
Hanoi (1, A, C, B)
Hanoi (n - 1, B, C, A)
if(__name__=="__main__"):
main()
#<程序:merge函数> by Edwin Sha
def merge(L1,L2):
if len(L1) ==0: return(L2)
if len(L2) ==0: return(L1)
if L1[0] < L2[0]:
return([L1[0]]+merge(L1[1:len(L1)],L2))
else:
return([L2[0]]+merge(L1,L2[1:len(L2)]))
X=merge([1,4,9],[10])
print(X)
#============================================
#5.3 分治法(Divide-and-Conquer Algorithm)
#============================================
#<程序:最小值_循环>
def M(a):
m=a[0]
for i in range(1,len(a)):
if a[i]
m=a[i]
return m
a=[4,1,3,5]
print(M(a))
#<程序:最小值_递归> a是个数组
def M(a):
print(a)
if len(a) ==1: return a[0]
return (min(a[len(a)-1], M(a[0:len(a)-1])))
L=[4,1,3,5]
print(M(L))
#<程序:最小值_分治>
def M(a):
#print(a) 可以列出程序执行的顺序]
if len(a) ==1: return a[0]
return ( min(M(a[0:len(a)//2]),M(a[len(a)//2:len(L)])))
L=[4,1,3,5]
print(M(L))
#<程序:最小值和最大值_分治>
A=[3,8,9,4,10,5,1,17]
def Smin_max(a):
if len(a)==1:
return(a[0],a[0])
elif len(a)==2:
return(min(a),max(a))
m=len(a)//2
lmin,lmax=Smin_max(a[:m])
rmin,rmax=Smin_max(a[m:])
return min(lmin,rmin),max(lmax,rmax)
print("Minimum and Maximum:%d,%d"%(Smin_max(A)))
#<程序:归并排序merge sort>
def msort(L):
k=len(L)
if k==0: return(L)
if k==1: return(L)
X1=L[0:k//2]; X2=L[k//2:k] #X1,X2 are local variables
print("X1=",X1," X2=",X2) #看看输出是什么?知道递归是如何执行的。
X1=msort(X1); X2=msort(X2)
return(merge(X1,X2))
#<程序: 全加器>
def FA(a,b,c): # Full adder
carry = (a and b) or (b and c) or (a and c)
sum = (a and b and c) or (a and (not b) and (not c)) \
or ((not a) and b and (not c)) or ((not a) and (not b) and c)
return carry, sum
#<程序:二进制加法-二分法算法> by Edwin Sha
def add_divide(x,y,c=False):
# x, y are lists of True or False, c is True or False
# return carry and a list of x+y
while len(x) < len(y): x = [False]+x
while len(y) < len(x): y = [False]+y
if len(x) ==1:
ctemp, stemp=FA(x[0],y[0],c)
return (ctemp, [stemp])
if len(x) ==0: return c, []
c1,s1=add_divide(x[len(x)//2:len(x)],y[len(y)//2:len(y)],c)
c2,s2=add_divide(x[0:len(x)//2],y[0:len(y)//2],c1) #依赖关系!
return(c2,s2+s1)
#============================================
#5.4 贪心算法(Greedy Algorithm)
#============================================
#<程序:找零钱_贪心>
v=[25,10,5,1]
n=[0,0,0,0]
def change():
T_str=input('要找给顾客的零钱,单位:分:')
T=int(T_str)
greedy(T)
for i in range(len(v)):
print('要找给顾客',v[i],'分的硬币:',n[i])
s=0
for i in n:
s=s+i
print('找给顾客的硬币数最少为:',s)
def greedy(T):
if T==0:return
elif T>=v[0]:
T=T-v[0]; n[0]=n[0]+1
greedy(T)
elif v[0]>T>=v[1]:
T=T-v[1]; n[1]=n[1]+1
greedy(T)
elif v[1]>T>=v[2]:
T=T-v[2]; n[2]=n[2]+1
greedy(T)
else:
T=T-v[3]; n[3]=n[3]+1
greedy(T)
if(__name__=="__main__"):
change()
#<程序:GCD_贪心>
def main():
x_str=input('请输入正整数x的值:')
x=int(x_str)
y_str=input('请输入正整数y的值:')
y=int(y_str)
print(x,'和',y,'的最大公约数是:', GCD(x,y))
def GCD(x,y):
if x>y: a=x;b=y
else: a=y;b=x
if a%b ==0: return(b)
return(GCD(a%b,b))
if(__name__=="__main__"):
main()
#============================================
#5.5 动态规划(Dynamic Programming)
#============================================
#<程序:最长递增子序列_动态规划>
def LIS(L): #LIS (L):Longest Increasing Sub-list of List L
Asc=[1]*len(L);Tra=[-1]*len(L) #设定起始值
#Asc[i] 存放从L[0]到L[i]以L[i]为最大值的最长递增子序列的长度,
# 这个最长数列肯定以L[i]结尾
#Tra[i] 存此最长数列的前一个索引,以后好连起整个递增序列。
for i in range(1,len(L)):
X=[]
for j in range(0,i):
if L[i] > L[j]: X.append(j) #所有比L[i]小L[j]的索引放在X
for k in X: #Asc[i]= max Asc[k]+1, for each k in X
if Asc[i] < Asc[k]+1: Asc[i]=Asc[k]+1; Tra[i]=k
print("Asc:",Asc)
print("Tra:",Tra)
max=0 #找到Asc中的最大值
for i in range(1,len(Asc)):
if Asc[i]>Asc[max]: max=i
print("最长递增子序列的长度是",Asc[max])
#将最长递增数列存到X
X=[L[max]]; i=max;
while (Tra[i] >=0):
X=[L[Tra[i]]]+X
i=Tra[i]
print("最长递增子数列=",X)
L=[5,2,4,7,6,3,8,9]
LIS(L)
#<程序:直接用递归函数计算Asc(k)>
def Asc(k):
if k==0: return(1)
X=[]
for i in range(0,k):
if L[k] > L[i]: X.append(Asc(i)) #记录所有比L[k]小的Asc()
if len(X) >0: return (max(X)+1)
else: return(1)
def LIS_R(L):
X=[]
for k in range(0, len(L)):
X.append(Asc(k))
print(X)
print(max(X))
L=[5,2,4,7,6,3,8,9]
LIS_R(L)
#<程序:背包问题_递归>
w=[0,4,5,2,1,6] #w[i]是物品的重量
v=[0,45,57,22,11,67] #v[i]是物品的价值
n=len(w)-1
j=8 #背包的容量
x=[False for raw in range(n+1)]#x[i]为True,表示物品被放入背包
def knap_r(n,j):
if (n==0)or(j==0):
x[n]=False
return 0
elif (j>=w[n])and(knap_r(n-1,j-w[n])+v[n]>knap_r(n-1,j)):
x[n]=True
return knap_r(n-1,j-w[n])+v[n]
else:
x[n]=False
return knap_r(n-1,j)
print("最大价值为:",knap_r(n,j))
print("物品的装入情况为:",x[1:])
#<程序:背包问题_动态规划>
w=[0,4,5,2,1,6] #w[i]是物品的重量
v=[0,45,57,22,11,67] #v[i]是物品的价值
n=len(w)-1
m=8 #背包的容量
x=[False for raw in range(n+1)]#x[i]为True,表示物品被放入背包
#a[i][j]是i个物品中能够装入容量为j的背包的物品所能形成的最大价值
a=[[0 for col in range(m+1)] for raw in range(n+1)]
def knap_DP(n,m):
#创建动态规划表
for i in range(1,n+1):
for j in range(1,m+1):
a[i][j]=a[i-1][j]
if (j>=w[i]) and(a[i-1][j-w[i]]+v[i]>a[i-1][j]):
a[i][j]=a[i-1][j-w[i]]+v[i]
#回溯a[i][j]的生成过程,找到装入背包的物品
j=m
for i in range(n,0,-1):
if a[i][j]>a[i-1][j]:
x[i]=True
j=j-w[i]
Mv=a[n][m]
return Mv
#============================================
#5.6 以老鼠走迷宫为例
#============================================
#<程序:老鼠走迷宫_递归>
m=[[1,1,1,0,1,1,1,1,1,1],
[1,0,0,0,0,0,0,0,1,1],
[1,0,1,1,1,1,1,0,0,1],
[1,0,1,0,0,0,0,1,0,1],
[1,0,1,0,1,1,0,0,0,1],
[1,0,0,1,1,0,1,0,1,1],
[1,1,1,1,0,0,0,0,1,1],
[1,0,0,0,0,1,1,1,0,0],
[1,0,1,1,0,0,0,0,0,1],
[1,1,1,1,1,1,1,1,1,1]]
sta1=0;sta2=3;fsh1=7;fsh2=9;success=0
def LabyrinthRat():
print('显示迷宫:')
for i in range(len(m)): print(m[i])
print('入口:m[%d][%d]:出口:m[%d][%d]'%(sta1,sta2,fsh1,fsh2))
if (visit(sta1,sta2))==0: print('没有找到出口')
else:
print('显示路径:')
for i in range(10):print(m[i])
def visit(i,j):
m[i][j]=2
global success
if(i==fsh1)and(j==fsh2): success=1
if(success!=1)and(m[i-1][j]==0): visit(i-1,j)
if(success!=1)and(m[i+1][j]==0): visit(i+1,j)
if(success!=1)and(m[i][j-1]==0): visit(i,j-1)
if(success!=1)and(m[i][j+1]==0): visit(i,j+1)
if success!=1: m[i][j]=3
return success
if(__name__=="__main__"):
LabyrinthRat()
#============================================
#5.7 谈计算思维的美
#============================================
#++++++++++++++++++++++++++++++++++++++++++++
#5.7.3 问题复杂度的研究之美
#++++++++++++++++++++++++++++++++++++++++++++
#<程序:Find all the factors of x and put them in list L>
import math
def factors(x,L):
y=int(math.sqrt(x)) #x的平方根
for i in range(2,y+1): #一个个找
if (x %i ==0): #找到一个因数i
print(i)
L.append(i)
factors(x//i,L) #递归找
break #跳出for循环
else: #cannot find a factor, so x is a prime
L.append(int(x))
print(int(x))
L=[]
factors(18,L)
版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。