PAT Basic 1106. 2019数列

1. 题目描述：

把 2019 各个数位上的数字 2、0、1、9 作为一个数列的前 4 项，用它们去构造一个无穷数列，其中第 \(n\)（\(>4\)）项是它前 4 项之和的个位数字。例如第 5 项为 2，因为 \(2+0+1+9=12\)，个位数是 2。

本题就请你编写程序，列出这个序列的前 \(n\) 项。

2. 输入格式：

输入给出正整数 \(n\)（\(≤1000\)）。

3. 输出格式：

在一行中输出数列的前 \(n\) 项，数字间不要有空格。

4. 输入样例：

5. 输出样例：

2019224758

题外话：这个数列中永远不会出现 2018，你能证明吗？

6. 性能要求：

Code Size Limit
16 KB
Time Limit
400 ms
Memory Limit
64 MB

思路：

根据题意求出数列前 \(n\) 项元素进行输出即可，一开始定义了子函数getSeqNum()递归求解数列元素，但是第一次提交时testpoint2报time limit exceeded，无奈改为循环迭代求解数列元素，修改后AC。参考了别人的题解，应该是我递归函数的编写存在问题，会造成递归次数过多。。。

My Code:

// #include <stdio.h>

// int getSeqNum(int n);

// // first submit testpoint2 time limit exceeded
// int main(void)
// {
//     int n=0;
    
//     scanf("%d", &n);
//     for(int i=1; i<=n; ++i)
//     {
//         printf("%d", getSeqNum(i));
//     }
//     printf("\n"); // end a line
    
    
//     return 0;
// }

// int getSeqNum(int n)
// {
//     if(n==1) return 2;
//     else if(n==2) return 0;
//     else if(n==3) return 1;
//     else if(n==4) return 9;
//     else return((getSeqNum(n-4)+getSeqNum(n-3)+getSeqNum(n-2)+getSeqNum(n-1)) % 10);
// }


#include <stdio.h>

int getSeqNum(int n);

// first submit testpoint2 time limit exceeded
int main(void)
{
    int n=0;
    int seq[1000] = {0};
    
    seq[0] = 2;
    seq[1] = 0;
    seq[2] = 1;
    seq[3] = 9;
    
    scanf("%d", &n);
    
    for(int i=4; i<n; ++i)
    {
        seq[i] = (seq[i-4] + seq[i-3] + seq[i-2] + seq[i-1]) % 10;
    }
    
    for(int i=0; i<n; ++i)
    {
        printf("%d", seq[i]);
    }
    printf("\n"); // end a line
    
    
    return 0;
}