Try   HackMD
tags: ADA 2.2 Recurrence

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才知道切到什麼時候停下來

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 →