ADA 2.2 Recurrence
解決問題一定要用Recurrence方式做,遞迴
Recurrence Relation
- Definition
A recurrence is an equation or inequality that describes a function in
terms of its value on smaller inputs.
等式或是不等式,這個式子不管是等式或不等式,它描述一個function,是根據他比較小的input數值,會寫在func裡面
- Example
Fibonaccisequence(費波那契數列)
**Base case: F(0) = F(1)= 1
**Recursive case: F(n) = F(n-1) +F(n-2)
左邊跟右邊是一樣的func,只是裡面的數值比較小(右邊比左邊小)
需注意數列上要定義base case,什麼時候要足夠小,將來在Recursive case才知道切到什麼時候停下來
n |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
… |
F(n) |
1 |
1 |
2 |
3 |
5 |
8 |
13 |
21 |
34 |
… |
*螺,黃金比例
Recurrent Neural Network (RNN)
Image Not Showing
Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →
AI 類神經網路一個公式
也是一個遞迴相關的公式
St藉由St-1 ,t前一個時間的資訊拿來用,後面的時間會拿來沿用前面的時間資訊
Recurrent Benefits
Image Not Showing
Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →
有效率,較容易思考
比較容易思緒清楚跟簡單
因為只需要定義base case跟recursive case,就等同於定義了一連串的數字
Image Not Showing
Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →
把程式寫進去
**注意:base case一定要定義,否則程式會一直跑
Recurrence v.s. Non-Recurrence
Image Not Showing
Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →
分析:
結構清楚,但是效能不好,會有同一個func被不同的情況call一次
Image Not Showing
Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →
先準備一個表單,a0跟a1先填上,之後迴圈將數值填入,達到一樣的效果
分析:
因為從前面往後填,不會有上述重複扣的情況,雖然結構可能沒有上面的明確,但效能比較好
Image Not Showing
Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →
原則上能定義base case跟recursive case就可以去解決剛剛的問題
但不是所有問題都容易被解決,需要思考什麼是何用Recurrence去解決
舉例:河內塔
當盤子數量很多時,會很難去思考
但當盤子數量很少的時候,比較簡單,就容易定義出base case
就可以把大問題切成小問題,慢慢的去解決
如果n很小還是找不到,就不適合
Image Not Showing
Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →