第一種
一共有5個臺階，每一次可以跳一個或兩個臺階，
思路：設完成跳臺階的函式是jump(5)
完成這個動作最后可能有
- 最后跳了一下就跳完了；
- 最后跳了兩下就跳完了；
1——它的位置在第四個臺階，跳到這里要jump(4);
2——它的位置在第三個臺階，跳到這里要jump(3);
所以在這種情況下jump(5)=jump(4)+jump(3).
我們再將總共的臺階數看成n個
最后可能情況為
- 最后跳了一下就跳完了；
- 最后跳了兩下就跳完了；
與上一種情況相同；
jump(n)=jump(n-1)+jump(n-2)
（注意當n=1時有一種方法，n=2時有兩種方法作為結束遞回的出口）
//這里討論1或2的原因
eg：n=3時=jump(2)+jump(1);如果不考慮n=2有兩種情況
jump（2）=jump(1)+jump(0)=1但實際上n=2時有兩種情況，會出現錯誤，
對應代碼實作為
觀察輸出結果
發現是斐波那契數，
第二種
一共n個臺階，每次可以跳1，2，3到n個臺階，
根據上面的分析
最后可能的情況為：
剩一個，剩兩個…剩n個；
//剩n個到此位置的方法為0；jump(0)=0
jump(n)=jump(n-1)+jump(n-2)…+jump(0);——1
———————一共n個———————
對應jump(n-1):
jump(n-1)=jump(n-2)+…jump(0);——2
1式與2式聯立求解
jump(n)=jump(n-1)+jump(n-1)=2*jump(n-1);
對應代碼：
輸出結果
第三種
有n個臺階，每次可以跳1，2，3…m個臺階
因為m與n的大小未知所以要討論
當m>=n時
跳到最后的可能情況：
剩n個，剩n-1個，…剩1個；
所以這種情況和第二種相同，
jump(n)=2*jump(n-1)
當m<n
跳到最后可能的情況
剩m個跳完——在此位置可能情況jump(n-m)
剩m-1個跳完——位置可能情況jump(n-(m-1))
…
剩一個跳完——可能情況jump(n-1)
此時
jump(n)=jump(n-1)+jump(n-2)…+jump(n-m);
jump(n-1)=jump(n-2)…jump(n-m)+jump(n-m-1);
聯立求解
jump(n)=jump(n-1)+jump(n-1)-jump(n-m-1)；
jump(n)=2*jump(n-1)-jump(n-m-1);
對應代碼
輸出結果
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/252176.html
標籤：其他
上一篇：CTFshow——DJBCTF MISC（2021年大吉杯）
下一篇：冬令營第二天（1.19）