递归与变态跳台阶

发表于 | 分类于 | | 阅读次数

数学是算法的皇后，不懂数学，难学算法啊。

剑指offer第11题Java实现

题目：
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

/**
 * @author 李文浩
 * @version 2017/8/13.
 *          <p>
 *          <p>
 *          一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。
            求该青蛙跳上一个n级的台阶总共有多少种跳法。
 *          <p>
 *          思路:
 *          因为n级台阶，第一步有n种跳法：跳1级、跳2级、到跳n级
 *          跳1级，剩下n-1级，则剩下跳法是f(n-1)
 *          跳2级，剩下n-2级，则剩下跳法是f(n-2)
 *          所以f(n)=f(n-1)+f(n-2)+...+f(1)
 *          因为f(n-1)=f(n-2)+f(n-3)+...+f(1)
 *          所以f(n)=f(n-1)+f(n-1)=2*f(n-1)
 */
public class Test11 {
    public static void main(String[] args) {
        Test11 test11 = new Test11();
        System.out.println(test11.JumpFloorII(10));
        System.out.println(test11.JumpFloorII2(10));
        System.out.println(test11.JumpFloorII3(10));
    }

    /**
     * 递归
     *
     * @param target
     * @return
     */
    public int JumpFloorII2(int target) {
        if (target <= 0) {
            return -1;
        } else if (target == 1) {
            return 1;
        } else {
            return 2 * JumpFloorII2(target - 1);
        }
    }

    /**
     * 迭代
     *
     * @param target
     * @return
     */
    public int JumpFloorII3(int target) {
        int f = 1;
        for (int i = 1; i < target; i++) {
            f *= 2;
        }
        return f;
    }

    /**
     * 此种思路充分说明了数学是算法的皇后
     * <p>
     * 每个台阶都有跳与不跳两种情况(第n阶台阶必须跳),所以总共有 2 ^ (n - 1)种跳法，
     *
     * @param target
     * @return
     */
    public int JumpFloorII(int target) {
        //使用Math类的方法
//        return (int) Math.pow(2, target - 1);
        //2^(n-1)可以用位移操作进行，更快
        return 1 << --target;
    }
}

移位运算符

左移运算是将一个二进制位的操作数按指定移动的位数向左移位，移出位被丢弃，右边的空位一律补0。右移运算是将一个二进制位的操作数按指定移动的位数向右移动，移出位被丢弃，左边移出的空位或者一律补0，或者补符号位，这由不同的机器而定。在使用补码作为机器数的机器中，正数的符号位为0，负数的符号位为1。

<< 左移

需要移位的数字 << 移位的次数
例如：
3 << 2，则是将数字3左移2位

  1. 计算过程：
    　　首先把3转换为二进制数字0000 0000 0000 0000 0000 0000 0000 0011，然后把该数字高位(左侧)的两个零移出，其他的数字都朝左平移2位，最后在低位(右侧)的两个空位补零。则得到的最终结果是0000 0000 0000 0000 0000 0000 0000 1100，则转换为十进制是12。
  2. 数学意义：
    　　在数字没有溢出的前提下，对于正数和负数，左移一位都相当于乘以2的1次方，左移n位就相当于乘以2的n次方。

>> 右移
运算规则：
按二进制形式把所有的数字向右移动对应位移位数，低位移出(舍弃)，高位的空位补符号位，即正数补零，负数补1。
语法格式：
需要移位的数字 >> 移位的次数

例如11 >> 2，则是将数字11右移2位

  1. 计算过程：
    11的二进制形式为：0000 0000 0000 0000 0000 0000 0000 1011，然后把低位的最后两个数字移出，因为该数字是正数，所以在高位补零。则得到的最终结果是0000 0000 0000 0000 0000 0000 0000 0010。转换为十进制是2。
  2. 数学意义：
    右移一位相当于除2，右移n位相当于除以2的n次方。

>>> 无符号右移

  1. 运算规则：
    按二进制形式把所有的数字向右移动对应位数，低位移出(舍弃)，高位的空位补零。对于正数来说和带符号右移相同，对于负数来说不同。

  2. 其他结构和>>相似。
    有的时候，你希望将一个数的二进制值向右或向左移位。执行左移时，在一个数的二进制形式中，所有位都向左移动由移位运算符右侧的操作数指定的位数。 移位后在右边留下的空位将由零来填充。右移位运算符的原理相似，只是朝相反的方向移位。然而，如果数是负数，那么在左侧填充的值就是1而不是0。两个移位 运算符是>>和<<，它们分别是右移位和左移位运算符。除此之外，还有复合移位和赋值运算符<<=和>>=。

参考文档

  1. 移位运算符-百度百科
0%