面试题9：斐波那契数列

方法一：很容易想到的解法是直接使用递归。

C++代码：

#include "stdafx.h"   
#include <iostream>   
using namespace std;  
  
long long Fibonacci(unsigned int n)  
{  
    if (n == 0)  
    {  
        return 0;  
    }  
  
    if (n == 1)  
    {  
        return 1;  
    }  
  
    return Fibonacci(n-1) + Fibonacci(n-2);  
}  
  
int _tmain(int argc, _TCHAR* argv[])  
{  
    unsigned int n = 10;  
    cout << Fibonacci(n) << endl;  
    system("pause");  
    return 0;  
}  
#include "stdafx.h"
#include <iostream>
using namespace std;

long long Fibonacci(unsigned int n)
{
    if (n == 0)
    {
		return 0;
    }

	if (n == 1)
	{
		return 1;
	}

	return Fibonacci(n-1) + Fibonacci(n-2);
}

int _tmain(int argc, _TCHAR* argv[])
{
	unsigned int n = 10;
	cout << Fibonacci(n) << endl;
	system("pause");
	return 0;
}

缺点：很显然效率很低，因为存在重复计算的问题。

方法二：改进方法是将已经得到的数列中间项保存起来，下次使用时直接查找即可，避免重复计算。

C++代码：

#include "stdafx.h"   
#include <iostream>   
using namespace std;  
  
long long Fibonacci(unsigned int n)  
{  
    if (n == 0)  
    {  
        return 0;  
    }  
  
    if (n == 1)  
    {  
        return 1;  
    }  
  
    long long one = 0;  
    long long two = 1;  
    long long result = 0;  
  
    for (unsigned int i=2; i<=n; i++)  
    {  
        result = one + two;  
        one = two;  
        two = result;  
    }  
  
    return result;  
}  
  
int _tmain(int argc, _TCHAR* argv[])  
{  
    unsigned int n = 100;  
    cout << Fibonacci(n) << endl;  
    system("pause");  
    return 0;  
}  
#include "stdafx.h"
#include <iostream>
using namespace std;

long long Fibonacci(unsigned int n)
{
    if (n == 0)
    {
		return 0;
    }

	if (n == 1)
	{
		return 1;
	}

	long long one = 0;
	long long two = 1;
	long long result = 0;

	for (unsigned int i=2; i<=n; i++)
	{
		result = one + two;
        one = two;
		two = result;
	}

	return result;
}

int _tmain(int argc, _TCHAR* argv[])
{
	unsigned int n = 100;
	cout << Fibonacci(n) << endl;
	system("pause");
	return 0;
}