2244 - a1003

已知一个数列的前几个数是: 1, 1, 2, 3, 5, 8, 13, 21,….. 编程实现输入一个整数N,输出第N项是多少．例如输入4 输出3.。

N小于等于20；

Input

输入t 随后输入t个要查找的数

Output

Examples

Input

Output

Solution C

#include<stdio.h>
int main()
{
    int i,a[30],n,b;
    a[0]=1;
    a[1]=1;
    for(i=2;i<20;i++)
        a[i]=a[i-1]+a[i-2];
    scanf("%d",&n);
    while(n--)
    {
        scanf("%d",&b);
        printf("%d\n",a[b-1]);
    } return 0;
}

Solution C++

#include<iostream>
#include<cstdio>
#include<iostream>

using namespace std;

int a[50];

int dg(int n){
    if(n==1||n==2)
        a[n]=1;
    else if(a[n] == -1)
        a[n] = dg(n-1) + dg(n-2);
    return a[n];
}

int main(){
    fill(a,a+50,-1);
    int n;
    while(cin>>n){
        while(n--){
            int m;
            cin>>m;
            cout<<dg(m)<<endl;
        }
    }
    return 0;
}

Time Limit	1 second
Memory Limit	128 MB

Discuss Stats

上一题下一题