題目描述 跳臺階:一隻青蛙一次可以跳上1級臺階，也可以跳上2級。求該青蛙跳上一個n級的臺階總共有多少種跳法（先後次序不同算不同的結果）。變態跳臺階:一隻青蛙一次可以跳上1級臺階，也可以跳上2級……它也可以跳上n級。求該青蛙跳上一個n級的臺階總共有多少種跳法。矩形覆蓋:我們可以用21的小矩形橫著或者豎 ...
題目描述
跳臺階:一隻青蛙一次可以跳上1級臺階，也可以跳上2級。求該青蛙跳上一個n級的臺階總共有多少種跳法（先後次序不同算不同的結果）。
變態跳臺階:一隻青蛙一次可以跳上1級臺階，也可以跳上2級……它也可以跳上n級。求該青蛙跳上一個n級的臺階總共有多少種跳法。
矩形覆蓋:我們可以用21的小矩形橫著或者豎著去覆蓋更大的矩形。請問用n個21的小矩形無重疊地覆蓋一個2*n的大矩形，總共有多少種方法？
解題思路
看到這樣的題，基本上都是一臉矇蔽，但是其實這樣的題，一般都是有規律的，沒有規律，那還怎麼計算，這個時候學的數學就有用了，找規律。
跳臺階：
1級臺階：1，共1種，
2級臺階：2,11 共2種
3級臺階：12,21,111 共3種
4級臺階：22,211,121,112,1111 共5種
5級臺階：221,212,122,2111,1211,1121,1112,11111共8種
.....看出來規律了fn=f(n-1)+f(n-2)
變態跳臺階：
1級臺階：1，共1種，
2級臺階：2,11 共2種
3級臺階：3,21,12,1111 共4種
4級臺階：4,31,13,22,211,121,112,1111 共8種
5級臺階：5,41,14,32,23,311,131,113,221,212,122,2111,1211,1121,1112,11111共16種
.....看出來規律了fn=2f(n-1)
矩形覆蓋：
1的矩陣：1，共1種
2的矩陣4平：2*2,1111，共2種
3的矩陣9平：2*2 + 2*2 + 1, 2*2 + 1*5, 1*9共3種
4的矩陣16平：2*2*4, 2*2*3+1*2, 2*2*1+1*4(2種，2挨著和不挨著), 1*16共5種
.......規律了fn=f(n-1)+f(n-2),可以看出和跳臺階一樣
代碼實現
/// <summary> /// 迴圈跳臺階 /// </summary> /// <param name="n"></param> /// <returns></returns> public static int Jump(int n) { if (n <= 2) { return n; } int first = 1; int second = 2; int result = 0; for (int i = 3; i <= n; i++) { result = first + second; first = second; second = result; } return result; } /// <summary> /// 變態跳臺階 /// </summary> /// <param name="n"></param> /// <returns></returns> public static int Jump(int n) { if (n <= 1) { return n; } int first = 1; int result = 0; for (int i = 2; i <= n; i++) { result = 2 * first; first = result; } return result; }
想入非非：擴展思維，發揮想象
1. 數學不要忘，學會找規律
2. 不要動不動就用遞歸
