二、算法——07、斐波那契序列

一、递归法

最容易想到的就是办法，但是这个算法是不够好的。时间复杂度比较高，主要是因为有很多数是重复计算的。

二、直接法

递归是从后面往前推，而直接法是从前面往后面推，每次算得一个结果后，把结果暂存起来，得到了两个新的基值，然后使用新的基值，进一步推出后面的值。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ShuLie
{
    class Program
    {
        static void Main(string[] args)
        {
            //注意这里要从1开始，表示的是第一位
            for (int i = 1; i < 2000; i++)
            {
                if(DiGui(i) != ZhiJieFa(i))
                    Console.WriteLine("结果不不正确");
                else
                    Console.WriteLine("结果正确");

                Console.ReadLine();
            }
        }

        //算法复杂度2的n次方。Number代表的是第几位。
        static int DiGui(int number)
        {
            if (number == 1 || number == 2)
            {
                return 1;
            }
            else
            {
                return DiGui(number - 1) + DiGui(number - 2);
            }
        }

        //从头开始到尾，直接法。算法复杂度O（n）
        static int ZhiJieFa(int number)
        {
            int a = 1, b = 1;
            if (number == 1 || number == 2)
            {
                return 1;
            }
            else
            {
                for (int i = 3; i < number; i++)
                {
                    //1、算出前面两个相加的值
                    int temp = a + b;
                    //2、b本来是temp后两位的值。这时候需要往前移1位。
                    b = a;
                    //3、a本来是temp后一位的值。这时需要往前移1位。
                    a = temp;
                }
                return a;
            }
        }
    }
}

结果输出正确