斐波拉契数

leetcode地址：https://leetcode-cn.com/problems/fibonacci-number/

//斐波那契数，通常用 F(n) 表示，形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：F(0) = 0,  F(1) = 1  F(N) = F(N - 1) + F(N - 2), 其中 N > 1.

//0  1  2  3  4  5  6  7

//0  1  1  2  3  5  8  13

1.第一种实现方式：

int  fib (int n)//递归

{

    if(n<=1) return n;

    return fib(n-1)+fib(n-2);

}

2.第二种实现方式

int fib2(int n)

{

    if(n<=1) return n;

    int first = 0;

    int second = 1;

    int sum = 0;

    for(int i=0;i<n-1;i++)

    {

        sum = first+second;

        first =  second;

        second = sum;

    }

    return sum;

}

3.第三种实现方式

int fib3 (int n)

{

    if(n<=1) return n;

  int  first = 0;

  int second = 1;

   for(int i=0;i<n-1;i++)

   { 

      second = first + second;

      first  =  second - first;

    }

}

int main(int argc,const char* argv[]) {

    @autoreleasepool {

        // insert code here...

        NSLog(@"%d",fib(10));

        NSLog(@"------分割线-------");

        NSLog(@"%d",fib2(10));

    }

    return 0;

}