时间限制：3000 ms  |  内存限制：65535 KB

难度：

1

描述

无穷数列1，1，2，3，5，8，13，21，34，55...称为Fibonacci数列，它可以递归地定义为

F(n)=1 ...........(n=1或n=2)

F(n)=F(n-1)+F(n-2).....(n>2)

现要你来求第n个斐波纳奇数。（第1个、第二个都为1)

输入

第一行是一个整数m(m<5)表示共有m组测试数据

每次测试数据只有一行，且只有一个整形数n(n<20)

输出

对每组输入n，输出第n个Fibonacci数

样例输入

3135

样例输出

125

来源

上传者

 //迭代 C 时间复杂度是0(n),时间复杂度是0(1)。

#include<stdio.h>

int f(int n);

int main()

{

  int n;

  int i;

  int m;

  scanf("%d",&m);

  getchar();

  for(i=0;i<m;i++){

      scanf("%d",&n);

      getchar();

      f(n);

    }

}

int f(int n)

{

  int i,f1=1,f2=1,f3;

  if(n<=0)

    {

      printf("输入错误.\n");

    }

  else if(n==1||n==2)

    {

      printf("1\n");

    }

  else

    {

      for(i=0;i<n-2;i++)

        {

          f3=f1+f2;           //f1表示当前的值

          f2=f1;

          f1=f3;

        }

      printf("%d\n",f1);

    }

}

 

// 队列 C++

#include <stdio.h>

#include <iostream>

#include <queue>

#include <vector>

#include <string.h>

using namespace std;

int fib(int index){

  if (index < 1) {

      return -1;

    }

  queue<int> a;

  a.push(1);

  a.push(1);

  for (int var = 2; var < index; ++var) {

      a.push(a.front() + a.back());

      a.pop();

    }

  return a.back();

}

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

{

  cout << fib(3) << endl;

  return 0;

}

//vector C++

#include <stdio.h>

#include <iostream>

#include <queue>

#include <vector>

#include <string.h>

using namespace std;

int fib(int index){

  if (index < 1) {

      return -1;

    }

  vector<int> a(2,1);

  a.reserve(3);//reserve是容器预留空间，但并不真正创建元素对象，在创建对象之前，不能引用容器内的元素，因此当加入新的元素//时，需要用push_back()/insert()函数。

　　//resize是改变容器的大小，并且创建对象，因此，调用这个函数之后，就可以引用容器内的对象了，因此当加入新的元素时，用//operator[]操作符，或者用迭代器来引用元素对象

  //cout << "a2:" << a.at(2) << endl;

  cout << a.size() << endl;

  cout << a.capacity() << endl;

  for (int var = 2; var < index; ++var) {

      a.insert(a.begin(),a.at(0)+a.at(1));

      cout << "a0:"<< a.at(0)<< " a1:"<<a.at(1) << " a2:" << a.at(2) << endl;

      a.pop_back();

      cout <<"a.size:"<< a.size() << endl;

      cout << "a.cpt:"<<a.capacity() << endl;

    }

  return a.at(0);

}

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

{

  cout << fib(5) << endl;

  return 0;

}

output：

2

3

a0:2 a1:1 a2:1

a.size:2

a.cpt:3

a0:3 a1:2 a2:1

a.size:2

a.cpt:3

a0:5 a1:3 a2:2

a.size:2

a.cpt:3

5