欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

递归和循环:跳台阶和变态跳台阶和矩形覆盖

程序员文章站 2023-11-03 18:10:10
题目描述 跳台阶:一只青蛙一次可以跳上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. 不要动不动就用递归