爬梯子问题

有个梯子,有N个台阶,你每一次只能跨1个或者2个,问有多少种走法可以走到第N个呢?

首先想到像是排列组合,列出表格,看是否存在规律。

n=1 1 1
n=2 11,2 2
n=3 111,12, 21 3
n=4 1111, 112, 121, 211,22 5
n=5 11111,1112,1121,1211,2111,221, 212, 122 8

 

看第二列有规律,再看第三列,规律更大,“1  2  3  5  8 ……”不就是斐波那契数列吗?于是爬楼梯问题转化为斐波那契数列问题,再进行编码。
可以用数学归纳法来证明此问题就是斐波那契数列问题

也可以这么想,爬到第N个台阶后,有K个方法,那么前一步呢?可能是在第N-1个台阶,也可能是在N-2个台阶上(因为只能走1步或者2步),所以
f(N) = f(N-1) + f(N -2)
那么这个就是斐波那契数列了。

/**
 * Created by chris on 2014/11/24.
 *
 * You are climbing a stair case. It takes n steps to reach to the top.
 * Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
 *
 */

public class ClimbingStairs {
	//非递归实现
    public int climbStairs(int n) {
        int a,b,result;
        a = 1;
        b = 2;
        result = 0;
        if (1 == n){
            return a;
        }
        if (2 == n) {
            return b;
        }
        if (n >= 3) {
            for (int i = 3; i <= n; i++) {
                result = a + b;
                a = b;
                b = result;
            }
        }
      return result;
    }

    // 斐波那契数列递归实现 
    public int fibonacci(int n) {
        if (1 == n) return 1;
        if (2 == n) return 2;
        if (n >= 3) return fibonacci(n-1) + fibonacci(n-2);

        throw new IllegalArgumentException("invalid number n");
    }

	//也可以计算通项,直接计算,见下图


}

 

 

 

斐波那契数列通项

可以用通项直接求值。

 

 

 

Tagged on: , ,

发表评论

电子邮件地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.