[第十届蓝桥杯省赛C++B组]数列求值_第十届蓝桥杯c语言b组

阿里云国内75折回扣微信号：monov8

阿里云国际，腾讯云国际，低至75折。AWS 93折免费开户实名账号代冲值优惠多多微信号：monov8 飞机：@monov6

题目来源：第十届蓝桥杯省赛C++B组

算法标签：递推

问题描述：

给定数列 1, 1, 1, 3, 5, 9, 17, …，从第 4 项开始，每项都是前 3 项的和。
求第 20190324 项的最后 4 位数字。

思路：

看题肯定就是递推没跑。

for (int i = 4; i <= 20190324; i++)a[i] = (a[i-1] + a[i-2] + a[i-3]) ;

1.这道题不%10000就会数据过大，且后四位也只受到后四位的变化影响,所以我们每个数都mod10000;

for (int i = 4; i <= 20190324; i++)a[i] = (a[i-1] + a[i-2] + a[i-3]) % 10000;

2.OJ上数组开到20190324这种程度会出MLE问题,所以我们不开太大的数组而只固定4个位子，把整个数列每次移动一格取四格来看，则每次移动后，第四个是前三之和，前三个每次移动都分别变成了后一个的大小。

部分变动过程 1 1 1 3 1 1 3 5 1 3 5 9 3 5 9 17

int a[4] = { 0,1,1,1 };
a[4] = (a[3] + a[2] + a[1]) % 10000;
for (int j = 1; j <= 3; j++)a[j] = a[j + 1];

题目代码

#include <iostream>
using namespace std;

int a[4] = { 0,1,1,1 };

int main()
{
  for (int i = 4; i <= 20190324; i++)
  {
    a[4] = (a[3] + a[2] + a[1]) % 10000;//后四位之和只与后四位有关
    for (int j = 1; j <= 3; j++)a[j] = a[j + 1];//模拟后四位的前三位每次滚动增加
  }
  cout << a[4];

  return 0;
}

方法二：

#include<iostream>

using namespace std;

int a,b,c;
const int tlen = 10000;

int main(){
        a=b=c=1;

        for(int i=4;i<20190324;i+=3){
                a=(a+b+c)%tlen;
                b=(a+b+c)%tlen;
                c=(a+b+c)%tlen;
        }

        cout<<c<<endl;

        return 0;
}