in python_数学 in python
數學算法
本節內容將介紹數學算法。主要包含數學上幾個基本問題，算術分析方法，斐波那契數列問題，篩選算法，以及最大公約數問題。
知識點數學幾個基本問題
算術分析方法
斐波那契數列問題
篩選算法
最大公約數問題
數學上幾個基本問題
在編程界，有這么幾個經典的數學問題，這里給大家簡單介紹下。
3 n+1 問題
對于任意大于 1 的自然數 n，若該數為偶數則將其變為原來的一半，若為奇數則將其變為3 n+1。反復進行上述過程，直到結果為 1 時停止。這就是著名的“3 n+1”問題。要求輸入 n，輸出按“3 n+1”規則變換到 1 所需要的數字變換次數。(n<=10^9)
題目描述：
3 n+1 問題是一個簡單有趣而又沒有解決的數學問題。這個問題是由 L. Collatz 在 1937 年提出的。克拉茲問題(Collatz problem)也被叫做 hailstone 問題、3n+1 問題、Hasse 算法問題、Kakutani 算法問題、Thwaites 猜想或者 Ulam 問題?？死潌栴}的特殊之處在于：盡管很容易將這個問題講清楚，但直到今天仍不能保證這個問題的算法對所有可能的輸入都有效——即至今沒有人證明對所有的正整數該過程都終止。
問題如下：輸入一個正整數 n；
如果 n=1 則結束；
如果 n 是奇數，則 n 變為 3 n+1，否則 n 變為 n/2；
轉入第 2 步。
例子：
input:7
output:[7,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1] 16
參考代碼如下：
def function(num):
mylist=[num]
while num!=1:
if num%2==1: #如果為奇數
num=3*num+1
mylist.append(num)
else: #為偶數
num=num//2
mylist.append(num)
return mylist,len(mylist)-1
print(function(43))
尋找最值問題
在諸多數學問題，最值問題一直是爭論的主題。在求最值的探索的過程，如何更快更好地得到最值，一代又一代理論科學家做出很大的貢獻，逐漸衍化出來很多排序算法。關于排序算法的知識點，我們將在接下來的章節里介紹，這里將只對最大值，最小值進行簡單討論。
最大值求解
給定一個列表 [2, 4, 9, 7, 19, 94, 5]，請編寫 find_max 函數，該函數返回列表的最大值。
這個函數很容易，相信大家一定能夠自行編寫出來。
參考代碼如下：
def find_max(nums):
max = nums[0]
for x in nums:
if x > max:
max = x
print(max)
?
def main():
find_max([2, 4, 9, 7, 19, 94, 5])
?
if __name__ == '__main__':
main()
最小值求解
定一個列表 [2, 4, 9, 7, 19, 94, 5]，請編寫 find_min 函數，該函數返回列表的最小值。
這個函數也很容易，相信大家一定能夠自行編寫出來。
參考代碼如下：
def find_min(nums):
min=nums[0]
for x in nums:
if x
min=x
pritn(min)
?
def main():
find_max([2, 4, 9, 7, 19, 94, 5])
?
if __name__ == '__main__':
main()
最大公約數/最小公倍數
在介紹最大公約數和最小公倍數之前，我們先來介紹下歐幾里得算法
歐幾里得算法
歐幾里得算法又稱輾轉相除法，用來求兩個正整數的最大公約數。以 1997 和 615 為例，用歐幾里得算法求解如下：
1997=615*3+152
615=152*4+7
152=7*21+5
7=5*1+2
5=2*2+1
2=1*2+0
當被加的數為 0 時，可以得出，1997 和 615 的最大公約數為 1。
以上做法的依據是以下定理：
兩個整數的最大公約數等于其中較小的那個數和兩數相除余數的最大公約數。
用數學表示為：gcd(a,b)=gcd(b,amodb)
并可以證明歐幾里得算法一定能在有限步內結束。
利用圖形可以更直觀地理解歐幾里得算法
程序設計：
算法思想：a,b 始終扮演被除數和除數的角色。
最大公約數(greatest common divisor)縮寫為 gcd
參考代碼如下：
def gcd(a,b):
while b:
r=a%b
a=b #經過一次求余數，進入第二輪相除，即b的值扮演了被除數的角色
b=r #r的值扮演了余數的角色
return a #這里return a的原因是，b作為在最后一輪的除數已經幅值給了a
而對于最小公倍數則有以下思路求解：
a,b 兩個數的最小公倍數乘以他們的最大公約數約等于 a 和 b 本身的乘積
即LCM(a,b)GCD(a,b)=ab
所以最小公倍數的求解代碼如下：
def lcm(a,b):
return a*b//gcd(a,b)
請大家編程，構造一個 three_gcd 和 three_lcm 函數，該函數完成三個數的最大公因數和最小公倍數的求解
例子：
input:2,7,6
output: gcd :1 lcm: 84
思路：
計算三個數的最大公約數時，利用之前寫好的計算 2 個數的最大公約數的方法，先算出 a,b 的公約數，再用 a,b 的公約數與 c 再代入方法，此時返回的值就是三個數的最大公約數了。對于三個數的最小公倍數，繼續嵌套，先求出兩個數的，再求與第三個數的最小公倍數。
參考代碼如下：
def gcd(a,b):
while b:
r=a%b
a=b #經過一次求余數，進入第二輪相除，即b的值扮演了被除數的角色
b=r #r的值扮演了余數的角色
return a #這里return a的原因是，b作為在最后一輪的除數已經幅值給了a
def lcm(a,b):
return a*b//gcd(a,b)
def three_gcd(a,b,c):
return gcd(gcd(a,b),c)
def three_lcm(a,b,c):
return lcm(a,b)*c//gcd(gcd(a,b),c)
def main():
a=2
b=7
c=6
print("a:",a)
print("b:",b)
print("c:",c)
print("gcd(",a,",",b,",",c,"):",three_gcd(a,b,c))
print("lcm(",a,",",b,",",c,"):",three_lcm(a,b,c))
if __name__=='__main__':
main()
算術分析方法
在數學問題中，有很多算術分析方法。包括二分法，牛頓遞歸等等。我們將在接下來的章節里，逐一介紹這兩種種方法。
二分法
二分法：對于區間[a，b]上連續不斷且 f(a)·f(b)<0 的函數 y=f(x)，通過不斷地把函數 f(x)的零點所在的區間一分為二，使區間的兩個端點逐步逼近零點，進而得到零點近似值的方法叫二分法。
注：定義來自百度百科。
給定精確度 flex,用二分法求函數 f(x) 零點近似值的步驟如下：確定區間 [a,b],驗證 f(a)*f(b)<0,給定精確度 flex
求區間 (a,b) 的中點 c
計算 f(c):如果 f(c)=0,則 c 就是函數的零點
如果 f(a)*f(c)<0，則令 b=c
如果 f(c)*f(b)<0, 則令 a=c
判斷是否達到精確度 flex,即若 |a-b|< flex,則得到零點近似值 a(或 b),否則重復 2-3 步驟
例子：請在[1,1000]區間內，找到 x^3-2*x-5 的零點
import math
def bisection(function, a, b): #指定函數function,指定區間[a,b]
start = a
end = b
if function(a) == 0: #a即為零點
return a
elif function(b) == 0: #b即為零點
return b
elif function(a) * function(b) > 0: #二分法無法在該區間找到零點
print("couldn't find root in [a,b]")
return
else: #f(a)*f(b)<0 的情況
mid = (start + end) / 2
while abs(start - mid) > 10**-7: # 精確度設置為10**-7
if function(mid) == 0:
return mid
elif function(mid) * function(start) < 0:
end = mid
else:
start = mid
mid = (start + end) / 2
return mid
?
def f(x):
return math.pow(x, 3) - 2*x - 5
if __name__ == "__main__":
print(bisection(f, 1, 1000))
牛頓法
在數值分析里面, 牛頓法(亦稱牛頓拉弗森法)是一種方法，用于查找更好的根(或零點)的例子尋根算法。牛頓法也被用于求函數的最值。由于函數取最值的點處的導數值為零，故可用牛頓法求導函數的零點，其迭代式為
關于牛頓法和擬牛頓法的區別，請參考牛頓法和擬牛頓法這篇回答
例子：請用牛頓法，求函數 x*3-2x-5 在 3 附近的零點
參考代碼如下：
def newton(function,function1,start):
#function 是 f(x) function1 是 f(x)的導函數，即f'(x)
x_n=start
while True:
x_n1=x_n-function(x_n)/function1(x_n) #遞歸式
if abs(x_n-x_n1) < 10**-5:
return x_n1
x_n=x_n1
def f(x):
return (x**3)-2*x-5
def f1(x):
return 3*(x**2)-2
if __name__=="__main__":
print(newton(f,f1,3))
問題升級：如果題目不提供導函數，只提供本函數表達式，但是提供一個合理區間，如何求解該區間內的零點？
還是采用牛頓法的思路，導函數可以采用斜率不斷遞歸的方式。
參考代碼如下：
def intersection(function,start1,start2):
#function 是 f(x),start1,start2 是區間端點
x_n=start1
x_n1=start2
while True:
x_n2=x_n1-(function(x_n1)/((function(x_n1)-function(x_n))/(x_n1-x_n))) # 遞歸式
if abs(x_n2-x_n1) < 10**-5:
return x_n2
x_n=x_n1
x_n1=x_n2
def f(x):
return (x**3)-2*x-5
if __name__=="__main__":
print(intersection(f,3,3.5))
斐波那契數列問題
斐波那契數列(Fibonacci sequence)，又稱黃金分割數列、因數學家列昂納多·斐波那契(Leonardoda Fibonacci)以兔子繁殖為例子而引入，故又稱為“兔子數列”，指的是這樣一個數列：1、1、2、3、5、8、13、21、34...
在數學上，費波那契數列是以遞歸的方法來定義的：F(0) = 0
F(1) = 1
F(n) = F(n - 1) + F(n - 2) (n >= 2)
注：定義來自百度百科。
從數列上看，我們能看到這是一個典型的遞歸函數，python 遞歸方法實現。
我們在這里將介紹斐波那契數列的 3 種用 python 方法實現。使用 python 遞歸方法實現斐波那契數列
思路：f(n)=f(n-1)+f(n)，我們直接使用 python 遞歸方法實現斐波那契數列
參考代碼如下：
def fibo(num):
if num==1:
return 1
elif num==2:
return 1
elif num>2:
return fibo(num-1)+fibo(num-2)
else:
print("False")
代碼分析：遞歸函數特點，在函數內部調用自身本身；所以函數必須要求調用有底線，不能無窮向下調用，斐波那契數列的底線在 n=1 與 n=2
2. 使用 python 獨特的列表實現斐波那契數列
很多遞歸函數對于 python 來說非常簡單，因為 python 有個獨特的數據類型 list 列表，list 是動態的我們可以在尾部追加數據，這樣一來斐波那契數列就是簡單的加法游戲了。
參考代碼如下
def fibo(num):
if num==1:
return [1]
elif num==2:
return [1,1]
l=[1,1]
for i in range(2,num):
l.append(l[-2]+l[-1]) #將列表最后兩項的值求和，將值添加到列表最后
return l
?
print(fibo(10))
3. 使用 while 循環實現
def fibo(num):
a=1
b=1
i=0
l=[]
while i < num:
l.append(a)
a,b=a+b,a
i=i+1
return l
print(fibo(10))
關于斐波那契數列用矩陣分解的思路，這里就不詳述了，如果大家對矩陣分解的思路感興趣，請自行探索。
總結
以上是生活随笔為你收集整理的in python_数学 in python的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： richtextbox自动滚动到最下面_
- 下一篇： python类型提示包 检查静态类型_P