斐波那契數(shù)列算法分析(編輯修改稿)
2025-07-13 12:41 本頁面
【文章內(nèi)容簡介】 long d)。 Matrixamp。 operator=(const Matrixamp。)。 friend Matrix operator*(const Matrixamp。 lhs, const Matrixamp。 rhs) { Matrix ret(0,0,0,0)。 [0][0] = [0][0]*[0][0] + [0][1]*[1][0]。 [0][1] = [0][0]*[0][1] + [0][1]*[1][1]。 [1][0] = [1][0]*[0][0] + [1][1]*[1][0]。 [1][1] = [1][0]*[0][1] + [1][1]*[1][1]。 return ret。 }}。Matrix::Matrix(long a, long b, long c, long d){ thismatr[0][0] = a。 thismatr[0][1] = b。 thismatr[1][0] = c。 thismatr[1][1] = d。}Matrix::Matrix(const Matrix amp。rhs){ thismatr[0][0] = [0][0]。 thismatr[0][1] = [0][1]。 thismatr[1][0] = [1][0]。 thismatr[1][1] = [1][1]。}Matrixamp。 Matrix::operator =(const Matrix amp。rhs){ thismatr[0][0] = [0][0]。 thismatr[0][1] = [0][1]。 thismatr[1][0] = [1][0]。 thismatr[1][1] = [1][1]。 return *this。}Matrix power(const Matrixamp。 m, int n){ if (n == 1) return m。 if (n%2 == 0) return power(m*m, n/2)。 else return power(m*m, n/2) * m。}long fib4 (int n){ Matrix matrix0(1, 1, 1, 0)。 matrix0 = power(matrix0, n1)。 return [0][0]。}這時程序的效率為O（log(N)） 。公式解法：在O（1）的時間就能求得到F(n)了： 注意：其中[x]表示取距離x最近的整數(shù)。用C++寫的代碼如下：long fib5(int n){ double z =
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1