python學習實例（5）

#============================================
#5.1 計算思維是什么
#============================================#<程序: 找假幣的第一種方法> by Edwin Sha
def findcoin_1(L):if len(L) <=1:print("Error: coins are too few"); quit()i=0while i<len(L):if L[i] < L[i+1]: return (i)elif L[i] > L[i+1]: return (i+1)i=i+1print("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 countif n < 1:print('False')elif n == 1:print ("%d:\t%s -> %s" % (count, A, C))count += 1elif 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: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)//2lmin,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 variablesprint("X1=",X1,"   X2=",X2)  #看看輸出是什么？知道遞歸是如何執行的。X1=msort(X1); X2=msort(X2)return(merge(X1,X2))#<程序: 全加器>
def FA(a,b,c):  # Full addercarry = (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+ywhile len(x) < len(y): x = [False]+xwhile len(y) < len(x): y = [False]+yif 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=0for i in n:s=s+iprint('找給顧客的硬幣數最少為：',s)
def greedy(T):if T==0:returnelif T>=v[0]:T=T-v[0]; n[0]=n[0]+1greedy(T)elif v[0]>T>=v[1]:T=T-v[1]; n[1]=n[1]+1greedy(T)elif v[1]>T>=v[2]:T=T-v[2]; n[2]=n[2]+1greedy(T)else:T=T-v[3]; n[3]=n[3]+1greedy(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=yelse:   a=y;b=xif 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 LAsc=[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]的索引放在Xfor k in X:     #Asc[i]= max Asc[k]+1, for each k in Xif Asc[i] < Asc[k]+1: Asc[i]=Asc[k]+1; Tra[i]=kprint("Asc:",Asc)print("Tra:",Tra)max=0   #找到Asc中的最大值for i in range(1,len(Asc)):if Asc[i]>Asc[max]: max=iprint("最長遞增子序列的長度是",Asc[max])#將最長遞增數列存到XX=[L[max]]; i=max;while (Tra[i] >=0):X=[L[Tra[i]]]+Xi=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]=Falsereturn 0elif (j>=w[n])and(knap_r(n-1,j-w[n])+v[n]>knap_r(n-1,j)):x[n]=Truereturn knap_r(n-1,j-w[n])+v[n]else:x[n]=Falsereturn 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=mfor i in range(n,0,-1):if a[i][j]>a[i-1][j]:x[i]=Truej=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]=2global successif(i==fsh1)and(j==fsh2): success=1if(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]=3return successif(__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):  	#找到一個因數iprint(i)L.append(i)factors(x//i,L)		#遞歸找break				#跳出for循環else:  #cannot find a factor, so x is a primeL.append(int(x))print(int(x))
L=[]
factors(18,L)

?

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/445548.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/445548.shtml
英文地址，請注明出處：http://en.pswp.cn/news/445548.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！

相關文章

一個用LaTeX寫長除法計算過程的示例

一個用LaTeX寫長除法計算過程的示例

源碼 \begin{array}{lr} & x1 \\ x1 \!\!\!\!\!\! & \overline{)x^2 2x 1} \\ & \underline{x^2\ \ x\ \ \ \ \ \ \ } \\ & x 1 \\ & \underline{x1} \\ & 0 \end{array}效果 x1x1???????????)x22x1￣x2x￣x1x1￣0\begin{array}…
閱讀更多...
AltiumDesigner中PCB如何添加 Logo

AltiumDesigner中PCB如何添加 Logo

AltiumDesigner中PCB如何添加 Logo 轉載2015-10-29 00:07:55標簽&#xff1a;it文化教育首先用到的畫圖軟件&#xff0c;當然是大家熟悉的Altium Designer了&#xff0c;呵呵&#xff0c;相信很多人都用過這款畫圖軟件吧&#xff08;現在電路設計一直在用&#xff09;&#xff…
閱讀更多...
python學習實例（6）

python學習實例（6）

# #6.6 文件系統&#xff08;File System&#xff09; ## #6.6.3 Python中的文件操作 ##<程序&#xff1a;讀取文件os.py> f open("./Task1.txt",r); fls f.readlines() for line in fls:line line.strip(); print (line) f.close()#<程序&#xff1a;讀…
閱讀更多...
網絡視頻ts格式文件下載及將其合成單一視頻文件

網絡視頻ts格式文件下載及將其合成單一視頻文件

一些網站會將視頻分割成n個ts文件。 用貓抓chrome插件&#xff0c;抓取index.m3u8&#xff0c;可得到眾多ts文件下載地址。 可用迅雷打包下載ts文件以及index.m3u8文件&#xff0c;但有時會出現下載不了的情況&#xff0c;懷疑是請求報頭的問題上。 若迅雷下載不了&#xff…
閱讀更多...
PCB布局，布線技巧總結

PCB布局，布線技巧總結

PCB布局 在設計中&#xff0c;布局是一個重要的環節。布局結果的好壞將直接影響布線的效果&#xff0c;因此可以這樣認為&#xff0c;合理的布局是PCB設計成功的第一步。 布局的方式分兩種&#xff0c;一種是交互式布局&#xff0c;另一種是自動布局&#xff0c;一般是在自動布…
閱讀更多...
python學習實例（7）

python學習實例（7）

# #第8章 信息安全&#xff08;Information Security&#xff09;的python程序 ## #8.3 措施和技術 ## #8.3.1 密碼學 ##非對稱加密#<程序&#xff1a;把n分解成p*q> import math n 221 m int(math.ceil(math.sqrt(n))) flag 0 for i in range(2,m1,1):if n % i 0:pr…
閱讀更多...
什么是TTL電平、CMOS電平、RS232電平

什么是TTL電平、CMOS電平、RS232電平

工作中遇到一個關于電平選擇的問題,居然給忘記RS232電平的定義了,當時無法反應上來,回來之后查找資料才了解兩者之間的區別,視乎兩年多的時間,之前非常熟悉的一些常識也開始淡忘,這個可不是一個好的現象.:-),還是把關于三種常見的電平的區別copy到這里.做加深記憶的效果之用.. …
閱讀更多...
RFI濾波器電路

RFI濾波器電路

RFI濾波器電路 最實用解決方案是通過使用一個差分低通濾波器在儀表放大器前提供 RF 衰減濾波器。該濾波器需要完成三項工作&#xff1a;盡可能多地從輸入端去除 RF能量&#xff0c;保持每個輸入端和地之間的 AC 信號平衡&#xff0c;以及在測量帶寬內保持足夠高的輸入阻抗以避免…
閱讀更多...
使用Ultra Librarian 生成PCB庫文件

使用Ultra Librarian 生成PCB庫文件

第一步&#xff1a;找到對應芯片的CAD文件&#xff0c;以OPA350為例&#xff1a; http://www.ti.com/product/opa350 第二步&#xff1a; 下載上圖右邊連接的 Ultra Librarian.zip &#xff0c; 然后根據提示&#xff0c;安裝。 安裝好后打開Ultra Librarian&#xff0c;會出現…
閱讀更多...
借漢諾塔理解棧與遞歸

借漢諾塔理解棧與遞歸

我們先說&#xff0c;在一個函數中&#xff0c;調用另一個函數。 首先&#xff0c;要意識到&#xff0c;函數中的代碼和平常所寫代碼一樣&#xff0c;也都是要執行完的&#xff0c;只有執行完代碼&#xff0c;或者遇到return&#xff0c;才會停止。 那么&#xff0c;我們在函…
閱讀更多...
簡單迷宮問題

簡單迷宮問題

迷宮實驗是取自心理學的一個古典實驗。在該實驗中&#xff0c;把一只老鼠從一個無頂大盒子的門放入&#xff0c;在盒子中設置了許多墻&#xff0c;對行進方向形成了多處阻擋。盒子僅有一個出口&#xff0c;在出口處放置一塊奶酪&#xff0c;吸引老鼠在迷宮中尋找道路以到達出口…
閱讀更多...
qt超強繪圖控件qwt - 安裝及配置

qt超強繪圖控件qwt - 安裝及配置

qwt是一個基于LGPL版權協議的開源項目&#xff0c; 可生成各種統計圖。它為具有技術專業背景的程序提供GUI組件和一組實用類&#xff0c;其目標是以基于2D方式的窗體部件來顯示數據&#xff0c; 數據源以數值&#xff0c;數組或一組浮點數等方式提供&#xff0c; 輸出方式可以是…
閱讀更多...
BFPRT

BFPRT

在一大堆數中求其前k大或前k小的問題&#xff0c;簡稱TOP-K問題。而目前解決TOP-K問題最有效的算法即是BFPRT算法&#xff0c;其又稱為中位數的中位數算法&#xff0c;該算法由Blum、Floyd、Pratt、Rivest、Tarjan提出&#xff0c;最壞時間復雜度為O(n)O(n)。 讀者要會快速排序…
閱讀更多...
180°舵機的使用步驟

180°舵機的使用步驟

一.步驟 1.首先查看舵機的運行參數&#xff0c;包括工作的電壓和電流&#xff0c;轉1&#xff08;60&#xff09;需要的脈寬是多少。 2.根據舵機提供的參數&#xff0c;算出需要的PWM的周期和脈寬的范圍。 3.通過單片機或者其他數字電路產生相應的PWM波&#xff0c;便可以驅…
閱讀更多...
Qt開源項目

Qt開源項目

圖像處理&#xff1a; Krita digikam inkscape 編輯器&#xff1a; LiteIDE QDevelper KDeveloper Monkey Studio TeXstudio 繪圖&#xff1a; ZeGrapher QtiPlot qcustomplot QWT HotShots Inkscape 三維建模&#xff1a; QCAD FreeCAD OpenModelica LibreCAD 音樂&#xff1a…
閱讀更多...
使用Python作為計算器

使用Python作為計算器

數值 1.python支持基本的數學運算符&#xff0c;而且應用python你可以像寫數學公式那樣簡單明了。 eg: >>> 2 2 4 >>> 50 - 5*6 20 >>> (50 - 5*6) / 4 5.0 >>> 8 / 5 # division always returns a floating point number 1.6 2.除法…
閱讀更多...
java整體打印二叉樹

java整體打印二叉樹

一個調的很好的打印二叉樹的代碼。 用空格和^v來表示節點之間的關系。 效果是這樣&#xff1a; Binary Tree: v7v v6v ^5^ H4H …
閱讀更多...
前綴樹

前綴樹

是一種哈希樹的變種。典型應用是用于統計&#xff0c;排序和保存大量的字符串&#xff08;但不僅限于字符串&#xff09;&#xff0c;所以經常被搜索引擎系統用于文本詞頻統計。它的優點是&#xff1a;利用字符串的公共前綴來減少查詢時間&#xff0c;最大限度地減少無謂的字符…
閱讀更多...
學習4層板設計

學習4層板設計

今天是第一天嘗試設計四層PCB板&#xff0c;以前只畫過雙層板&#xff0c;所以今天花了好多時間來熟悉多層板的設計方法&#xff0c;現在做一下整理&#xff0c;也方便其他同胞少走彎路~~~我用的軟件是Altium Designer 6&#xff08;AD6&#xff09;步驟如下&#xff1a; 1、隨…
閱讀更多...
PCB設計的基本步驟

PCB設計的基本步驟

一.方案的設計 1.與客戶溝通&#xff0c;確定電路的功能和相關設計指標&#xff08;如&#xff1a;電源&#xff0c;功耗等&#xff09;。 2.畫出項目的硬件功能框圖。 3.設計出多種方案&#xff0c;并對多種方案進行對比&#xff0c;最終選出最合適的方案。 4.根據上述所…
閱讀更多...
最新文章

Copyright @ 2022~2023