学步园

想法源于题目：一个人一次可以上一个台阶，也可以上两个台阶，问上到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;
        }