<pre name="code" class="cpp">/*
第 19 题:
题目:定义 Fibonacci 数列如下:
f(n)=1 n=0
f(n)= 1 n=1
f(n-1)+f(n-2) n=2
输入n,用最快的方法求该数列的第 n 项。
基本的方法有2种
还有个网上方法:
其数学基础:
方阵{ f(n), f(n-1), f(n-1), f(n-2) } = {1, 1, 1,0 }n-1方
即前者表示一个2X2的方阵,
后者表示一个第一行为1,1、第二行为1,0的方阵的n-1次方。
矩阵{1,1,1,0}的n-1次方的结果的第一行第一列就是f(n),
现在的问题转换为求矩阵{1, 1, 1, 0}的乘方。
但我们可以考虑乘方的如下性质:
/ a......
阅读全文