递归与变态跳台阶

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

剑指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%