一、递归法
最容易想到的就是办法，但是这个算法是不够好的。时间复杂度比较高，主要是因为有很多数是重复计算的。
二、直接法
递归是从后面往前推，而直接法是从前面往后面推，每次算得一个结果后，把结果暂存起来，得到了两个新的基值，然后使用新的基值，进一步推出后面的值。
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;
}
}
}
}
结果输出正确
