Tag Archives: Notes

演算法筆記 — 歸納法(1)

痾 . . . 歸納法是啥?沒關係,這個先別管他,來證明些數學問題吧!

現在有個理論T,而T中有一個參數n ; 我們想證明「n可以是任何自然數」的話該怎麼做呢?

最直接明瞭的方法自然就是窮舉啦 :

證明 T(n=1) 為真
證明 T(n=2) 為真
證明 T(n=3) 為真
...

可能把這串證明寫到宇宙盡頭都寫不完(❍ᴥ❍ʋ)

但是用歸納法的話只要證明兩點就好了 :

1. T(n=1)為真
2. 對所有n>1,若T(n-1)為真,則T(n)為真
Continue reading 演算法筆記 — 歸納法(1)