Swift学习—— 求Fibonacci数列

前端之家收集整理的这篇文章主要介绍了Swift学习—— 求Fibonacci数列前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

参考自:http://www.cnblogs.com/python27/archive/2011/11/25/2261980.html

题目:定义Fibonacci数列如下:

分析1:看到斐波那契数列几乎所有的程序员在第一时间的反应都是递归,没错了,作为和汉诺塔一样的经典递归问题,我们几乎毫不犹豫就可以写出如下的代码

func fibonacci_1(index:Int)->Int{
    if index == 0{
        return 0
    }
    else if index == 1{
        return 1
    }
    else
    {
        return fibonacci_1(index-1)+fibonacci_1(index-2)
    }
}

分析2:既然上面算法的主要缺点是要重复的计算很多不必要的数值,那么我们的想法是不计算那些重复的值,我们考虑对于任意一个N值,我们从第一项开始,不断的累积下去,这样就可以避免重复计算。由于是从第一项逐次求解,所以该算法的时间复杂度为O(n)代码如下:

func fibonacci_2(index:Int)->Int{
    if index == 0{
        return 0
    }
    else if index == 1{
        return 1
    }
    else
    {
        var firstNum:Int = 0
        var secondNum:Int = 1
        var count = 1
        var fib = 0
        while count < index
        {
            fib = firstNum + secondNum
            firstNum = secondNum
            secondNum = fib
            ++count
        }
        return fib
    }
}

分析3:最后介绍一种效率最高的算法O(logn),首先我们有下面的数学公式:

我们可以用数学归纳法证明如下:

Step1: n=2

Step2:设n=k时,公式成立,则有:

等式两边同乘以[1,1;1,0]矩阵可得:

=右,这正是n=k+1时的形式,即当n=k+1时等式成立。

Step1Step2可知,该数学公式成立。

由此可以知道该问题转化为计算右边矩阵的n-1幂问题。

我们利用分治的算法思想可以考虑如下求解一个数A的幂。

实现这种算法需要定义矩阵,以及矩阵的有关运算,具体代码如下:

//定义一个矩阵结构体
struct Matrix2by2 {
    var m00:Int
    var m01:Int
    var m10:Int
    var m11:Int
    init(m_00:Int,m_01:Int,m_10:Int,m_11:Int){
        self.m00 = m_00
        self.m01 = m_01
        self.m10 = m_10
        self.m11 = m_11
    }
    
}

//定义2X2矩阵的乘法运算
func matrixMultiply(matrix1:Matrix2by2,matrix2:Matrix2by2)->Matrix2by2{
    var matrix12:Matrix2by2 = Matrix2by2(m_00: 1,m_01: 1,m_10: 1,m_11: 0)
    matrix12.m00 = matrix1.m00 * matrix2.m00 + matrix1.m01 * matrix2.m10
    matrix12.m01 = matrix1.m00 * matrix2.m01 + matrix1.m01 * matrix2.m11
    matrix12.m10 = matrix1.m10 * matrix2.m00 + matrix1.m11 * matrix2.m10
    matrix12.m11 = matrix1.m10 * matrix2.m01 + matrix1.m11 * matrix2.m11
    return matrix12
}

//定义2X2矩阵的幂运算
func matrixPower(n:Int)->Matrix2by2{
    var matrix:Matrix2by2 = Matrix2by2(m_00: 1,m_11: 0)
    if n == 1{
        matrix = Matrix2by2(m_00: 1,m_11: 0)
    }
    else if n % 2 == 0{
        matrix = matrixPower(n/2)
        matrix = matrixMultiply(matrix,matrix)
    }
    else if n % 2 == 1{
        matrix = matrixPower((n-1) / 2)
        matrix = matrixMultiply(matrix,matrix)
        matrix = matrixMultiply(matrix,Matrix2by2(m_00: 1,m_11: 0))
    }
    return matrix
}

func fibonacci_3(index:Int)->Int{
    if index == 0{
        return 0
    }
    else if index == 1{
        return 1
    }
    else{
        var fibMatrix:Matrix2by2 = matrixPower(index-1)
        return fibMatrix.m00
    }
}

猜你在找的Swift相关文章