iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 12
0

利用function寫一個計算正方形面積和正三角形面積,並且計算當邊長為5和10的正方形面積相差多少?又邊長為5的正方形面積和邊長為10的正三角形面積相差多少?

def sq_area(length):
    return length*length

def tri_area(length):
    return 0.25*(3**0.5)*length**2

print(sq_area(10)-sq_area(5)) #outout:75
print(tri_area(10)-sq_area(5)) #outout:18.30127018922193

費氏數列

費波那契數列(Fibonacci sequence),是一個很常見的關係數列關係,我們來觀察一下他的數列:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55,.....


所以我們將他的關係寫成方程式的樣子如下:

當序列中的每一項和前面幾項有關係,這個關係我們又稱為「遞迴關係(recurrence relation)」!

那在程式中我們該如何進行呢?

例如我們要求n=6時的費氏數字f(6)時,就必須切成f(5)和f(4),這時若要計算f(5),就必須計算f(4)和f(3),依此類推,最後達到f(0)時這時候就不需再往下切。

讓我們來Programming

def fib(n):
    if n<1:
        return 0
    elif n==1:
        return 1
    else:
        return fib(n-1)+fib(n-2)
print(fib(30))

Divide And Conquer

其實我們剛剛在做的就是演算法(Algorithm)我們必須要將大問題,一步一步切成小問題,再將小問題切成更小的問題,直到問題不能再往下切,即達到base case,這個就是所謂的「分而治之(Divide And Conquer)」。
原則上對於Divide And Conquer大致上可以分成:分解、解題、合併
分解:將大問題分解成小問題,而這些小問題的形式與大問題一樣,直到小問題不能再往下分解的base case
解題:當小問題較小且容易解決時,則直接解;否則,利用遞歸關係來解決問題。
合併:將解決後的小問題,在合併成原本的大問題。

好啦~今天我們到這
今天我們來寫一個問題:
Q. 利用Divide And Conquer Algorithm 來完成計算組合數C(m,n),其必須滿足以下關係:


上一篇
[Day15]你知道函數嗎?
下一篇
[Day 17] name? main? if __name__ == '__main__' ? 兩眼一抹黑啊...
系列文
從0開始學習程式-Python32

尚未有邦友留言

立即登入留言