蓝桥杯数列求值(2019试题C)
【问题描述】
给定数列1,1,1,3,5,7,17……从第4项开始，每项都是前3项的和。求第20190324项的最后4位数字。
【答案提交】
这是一道结果填空题，考生只需要计算出结果并提交即可。本题的结果为一个4位整数（提示:答案的千位不为0），在提交答案时只填写这个整数，填写多余内容将无法得分。
【参考答案】
4659
【题目解析】
该数列公式很容易让人想起斐波那契数列的递推法进行计算，递推公式为:
a[i] = a[i-1] + a[i-2] +a[i-3]
但要注意一个问题，那就是由于a[i]到后面会变得过大，从而超过long long所表示的范围，所以数组中只保留计算结果的后4位，这就需要在每次存放数据之前就对数据进行取余运算，只保留数据的后4位。
【参考程序如下】
#include <iostream>
using namespace std;
int dp[20190324];
int main(int argc, char** argv) {
int i;
dp[0] = dp[1] = dp[2] = 1;
for(i = 3; i < 20190324;i++)
dp[i] = (dp[i - 1] + dp[i - 2] + dp[i - 3]) % 10000;
cout << dp[i - 1];
return 0;
}【运行结果如下】
