想法源于题目：一个人一次可以上一个台阶，也可以上两个台阶，问上到20级台阶有多少种走法？
这就是一个斐波那契数列：登上第一级台阶有一种登法；登上两级台阶，有两种登法；登上三级台阶，有三种登法；登上四级台阶，有五种方法……所以，1，2，3，5，8，13……
我们也会发现：
f(3) = f(2) + f(1);
f(4) = 2*(f2)+1*f(1);
f(5) = 3*(f2) + 2*f(1);
f(6) = 5*f(2) + 3*f(1);
..........
f(n) = a*f(x) + b * f(y);
a,b同样是斐波那契数列中的数；同时发现当：
a+x == n && b+y ==n-1 && x == y+1时等式成立；
可以得到如下O(log(n))的算法：
/// <summary> /// 基本原理为: /// n为偶数时f(n)=f(n/2)*f(n/2)+f(n-1)*f(n-1); /// n为基数时f(n)=f(n/2+1)*f(n/2)+f(n/2)*f(n/2-1); /// </summary> /// <param name="n"></param> /// <returns></returns> public static long Fn2( int n) { if ( 1 < n) { var steps = new Stack< int>(); while (n > 2) { steps.Push(n); n /= 2; } long r1 = 2, r2 = 3; while (steps.Count > 0) { int tmp = steps.Pop(); if ( 3 < tmp) { long tr1; long tr2; if ( 0 == tmp% 2) { tr1 = 2*r1*r1 + r2*r2 - 2*r1*r2; tr2 = 2*r1*r2 - r1*r1; r1 = tr1; r2 = tr2; } else { tr1 = 2*r1*r2 - r1*r1; tr2 = r1*r1 + r2*r2; r1 = tr1; r2 = tr2; } } else { r1 = 3; r2 = 5; } } return r1; } if ( 1 == n) return 1; return - 1; }