菲薄那切问题

sheet

斐波那契	解决思路
递归解法	首先判断终结的方式，就是等于 1 或者等于2 的时候就返回一，否则返回 f(1) +ｆ(2)
非递归解法	同上，首先判断终结条件，然后构建三个变量，首先 result = v1 + v2, 然后 v1 = v2 ， v2 = relust 就是一路推，首先 v1 推到 v2 的位置，也就是更新了
上台阶	上台阶问题，就是菲薄那切的变种，12台阶可以直接用，别的就是递归多次而已

话不多说，直接上代码：

package com.xpj.algo

/*
* 上台阶问题，每次都可以上一个或者两个台阶，这个就是斐波那契 数列，如果是每次一到 3 那么就
* 是 f(4) = f(3) +　ｆ(2) + f(1)
* */

// 使用递归解决菲薄那切数列
fun feb1(value: Int) : Int{
    if (value <= 0 || value == 1 || value == 2) {
        return 1
    }
    return feb1(value - 1) + feb1(value - 2)
}

fun feb2(value:Int) :Int {
    if (value <= 0 || value == 1 || value == 2) {
        return 1
    }

    var v1 = 1
    var v2 = 1
    var result = 0
    // 注意这里需要用 .. 去完成前后都是 闭区间的效果
    for (i in 3 .. value) {
        result = v1 + v2
        v1 = v2
        v2 = result
    }
    return result
}