数列

[编程题]数列

热度指数：10895 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

某种特殊的数列a1, a2, a3, ...的定义如下：a1 = 1, a2 = 2, ... , a_n = 2 * a_{n − 1} + a_{n - 2} (n > 2)。

给出任意一个正整数k，求该数列的第k项模以32767的结果是多少？

输入描述:

第1行是测试数据的组数n，后面跟着n行输入。每组测试数据占1行，包括一个正整数k (1 ≤ k < 1000000)。

输出描述:

n行，每行输出对应一个输入。输出应是一个非负整数。

示例1

输入

2
1
8

输出

1
408

算法知识视频讲解

202308764547周军

当测试用例有多个的情况下，每次重新计算第k个数据，效率就要差很多了，毕竟每个数都要从头重新计算一遍。因此程序进入后首先可以先生成一个较大的数列，后边测试用例中需要第几个直接取出即可

#include <stdio.h>
int main()
{
long n;
long arr[100000] = {1, 2};
//先生成数列，注意这里存入的是取模后的结果，否则数据会越界
for (int i = 2; i < 100000; i++) 
{
arr[i] = (arr[i-1] * 2 + arr[i-2]) % 32767;
} 
scanf("%d", &n);//获取测试用例个数
for (int i = 0; i < n; i++) 
{
int num;
scanf("%d", &num);
printf("%ld\n", arr[num-1]);//循环打印每个测试用例的对应结果就行
} 
return 0;
}

发表于 2024-11-07 21:43:17 回复(0)

一个达布刘

#include <stdio.h>
int main()
{
    int n;
    int a[100000];
    for(int i=0;i<100000;i++)
    {
        if(i<=2)
            a[i]=i;
        else
            a[i]=(2*a[i-1]+a[i-2])%32767;
    }
    while(scanf("%d",&n)!=EOF)
    {
        int k;
        for(int i=0;i<n;i++)
        {
            scanf("%d",&k);
            printf("%d\n",a[k]);
        }
    }
    return 0;
}

与其最后要模32767，不如给该数列提前模好

发表于 2022-07-21 10:31:31 回复(0)