「PAT乙级真题解析」Basic Level 1106 2019数列 (问题分析+完整步骤+伪代码描述+提交通过代码)

乙级的题目训练主要用来熟悉编程语言的语法和形成良好的编码习惯和编码规范。从小白开始逐步掌握用编程解决问题。

PAT (Basic Level) Practice 1106 2019数列

问题分析

题设要求很明确, 给定一个递推数列, 并第n项是第n-4到第n-1项的和的个位数字。
要求给定正整数n之后, 输出前n项.
于是我们的重点在于如何实现递推式得到数列的新一项, 然后一直生成到指定项即可。

如何生成新一项

因为我们需要用到前4项, 所以需要记录前4项。
用前4项之和生成新项后, 需要将第1项去掉, 然后将当前新项加到前4项中的末尾, 相当于一个滑动窗口。
如果编程语言自带"队列"这种数据结构, 十分好实现。
但是C语言中没有队列, 如果每次都自行移动记录的前4项, 可能会造成超时。
于是我们重新审视为什么我们要移动记录的4项值, 原因在于我们希望每一次都减去第1项, 把新项加在末尾。
但C语言难以实现我们这个直觉上想到的第一方案, 我们需要换一个方案。
其实我们需要的是知道接下来要减去哪一项（第一方案就是通过队列让我们确定每一次都减去第一项）
所以我们可以记录当前的迭代次数, 然后通过模运算, 在记录的4项值中循环进行数值更新。

样例

当前记录的前4项: 2 0 1 9
当前和: 12

生成第5项(记当前迭代次数为0)

• 当前和取个位数字, 得到新项"2"
• 当前和减去"前4项中索引为