題目：一只青蛙一次可以跳上1級(jí)臺(tái)階绒障，也可以跳上2級(jí)臺(tái)階。求該青蛙跳上一個(gè)n級(jí)的臺(tái)階總共有多少種跳法？
答題思路
- 如果只有1級(jí)臺(tái)階形葬，那顯然只有一種跳法
- 如果有2級(jí)臺(tái)階，那么就有2種跳法暮的，一種是分2次跳。每次跳1級(jí)淌实，另一種就是一次跳2級(jí)
- 如果臺(tái)階級(jí)數(shù)大于2冻辩，設(shè)為n的話猖腕，這時(shí)我們把n級(jí)臺(tái)階時(shí)的跳法看成n的函數(shù)，記為
,第一次跳的時(shí)候有2種不同的選擇：一是第一次跳一級(jí)恨闪，此時(shí)跳法的數(shù)目等于后面剩下的n-1級(jí)臺(tái)階的跳法數(shù)目倘感，即為
,二是第一次跳二級(jí)，此時(shí)跳法的數(shù)目等于后面剩下的n-2級(jí)臺(tái)階的跳法數(shù)目咙咽，即為
,因此n級(jí)臺(tái)階的不同跳法的總數(shù)為
老玛，不難看出就是斐波那契數(shù)列
數(shù)學(xué)函數(shù)表示如下
code
這里需要注意一下溢出的問(wèn)題，因?yàn)樵趕wift里若相加溢出钧敞，則會(huì)直接crash蜡豹，所以這里相加使用了 &+，溢出后返回nil
func fibonacci(number: UInt64) -> UInt64? {
if number == 1 {
return 1
}else if number == 2 {
return 1
}
var fibNMinusOne:UInt64 = 1
var fibNMinusTwo:UInt64 = 1
var fibN:UInt64 = 0
for _ in 3...number {
fibN = fibNMinusOne &+ fibNMinusTwo
if(fibN < fibNMinusOne) {
return nil
}
fibNMinusTwo = fibNMinusOne
fibNMinusOne = fibN
}
return fibN
}
若把條件修改成一次可以跳一級(jí)溉苛，也可以跳2級(jí)...也可以跳上n級(jí)呢镜廉？
思路
- 如果臺(tái)階級(jí)數(shù)為n的話，這時(shí)我們把n級(jí)臺(tái)階時(shí)的跳法看成n的函數(shù)愚战，記為
,若是第一次跳n級(jí)，此時(shí)跳法的數(shù)目等于1.所以
- 因此
- 兩式相減得到
- 因此可以得到下面的結(jié)果
答案
若把條件修改成一次可以跳一級(jí)拓哟，也可以跳2級(jí)...也可以跳上n級(jí)呢想许，則
