遞歸和迴圈:跳臺階和變態跳臺階和矩形覆蓋

題目描述

跳臺階:一隻青蛙一次可以跳上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. 不要動不動就用遞歸