python學(xué)習(xí)實(shí)例（5）

#============================================

#5.1 計(jì)算思維是什么

#============================================

#<程序: 找假幣的第一種方法> 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('請輸入盤子個(gè)數(shù)：')

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函數(shù)> 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)

#============================================

#<程序：最小值_循環(huán)>

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是個(gè)數(shù)組

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) 可以列出程序執(zhí)行的順序]

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) #看看輸出是什么？知道遞歸是如何執(zhí)行的。

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

#<程序：二進(jìn)制加法-二分法算法> 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) #依賴關(guān)系！

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('找給顧客的硬幣數(shù)最少為：',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('請輸入正整數(shù)x的值：')

x=int(x_str)

y_str=input('請輸入正整數(shù)y的值：')

y=int(y_str)

print(x,'和',y,'的最大公約數(shù)是：', 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 動(dòng)態(tài)規(guī)劃(Dynamic Programming)

#============================================

#<程序：最長遞增子序列_動(dòng)態(tài)規(guī)劃>

def LIS(L): #LIS (L)：Longest Increasing Sub-list of List L

Asc=[1]*len(L);Tra=[-1]*len(L) #設(shè)定起始值

#Asc[i] 存放從L[0]到L[i]以L[i]為最大值的最長遞增子序列的長度，

# 這個(gè)最長數(shù)列肯定以L[i]結(jié)尾

#Tra[i] 存此最長數(shù)列的前一個(gè)索引，以后好連起整個(gè)遞增序列。

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])

#將最長遞增數(shù)列存到X

X=[L[max]]; i=max;

while (Tra[i] >=0):

X=[L[Tra[i]]]+X

i=Tra[i]

print("最長遞增子數(shù)列=",X)

L=[5,2,4,7,6,3,8,9]

LIS(L)

#<程序：直接用遞歸函數(shù)計(jì)算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]是物品的價(jià)值

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("最大價(jià)值為：",knap_r(n,j))

print("物品的裝入情況為：",x[1:])

#<程序：背包問題_動(dòng)態(tài)規(guī)劃>

w=[0,4,5,2,1,6] #w[i]是物品的重量

v=[0,45,57,22,11,67] #v[i]是物品的價(jià)值

n=len(w)-1

m=8 #背包的容量

x=[False for raw in range(n+1)]#x[i]為True，表示物品被放入背包

#a[i][j]是i個(gè)物品中能夠裝入容量為j的背包的物品所能形成的最大價(jià)值

a=[[0 for col in range(m+1)] for raw in range(n+1)]

def knap_DP(n,m):

#創(chuàng)建動(dòng)態(tài)規(guī)劃表

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 談?dòng)?jì)算思維的美

#============================================

#++++++++++++++++++++++++++++++++++++++++++++

#5.7.3 問題復(fù)雜度的研究之美

#++++++++++++++++++++++++++++++++++++++++++++

#<程序: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): #一個(gè)個(gè)找

if (x %i ==0): #找到一個(gè)因數(shù)i

print(i)

L.append(i)

factors(x//i,L) #遞歸找

break #跳出for循環(huán)

else: #cannot find a factor, so x is a prime

L.append(int(x))

print(int(x))

L=[]

factors(18,L)

Python

版權(quán)聲明：本文內(nèi)容由網(wǎng)絡(luò)用戶投稿，版權(quán)歸原作者所有，本站不擁有其著作權(quán)，亦不承擔(dān)相應(yīng)法律責(zé)任。如果您發(fā)現(xiàn)本站中有涉嫌抄襲或描述失實(shí)的內(nèi)容，請聯(lián)系我們jiasou666@gmail.com 處理，核實(shí)后本網(wǎng)站將在24小時(shí)內(nèi)刪除侵權(quán)內(nèi)容。

版權(quán)聲明：本文內(nèi)容由網(wǎng)絡(luò)用戶投稿，版權(quán)歸原作者所有，本站不擁有其著作權(quán)，亦不承擔(dān)相應(yīng)法律責(zé)任。如果您發(fā)現(xiàn)本站中有涉嫌抄襲或描述失實(shí)的內(nèi)容，請聯(lián)系我們jiasou666@gmail.com 處理，核實(shí)后本網(wǎng)站將在24小時(shí)內(nèi)刪除侵權(quán)內(nèi)容。