首页 > 试题广场 >

数列

[编程题]数列

热度指数：10838 时间限制：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

算法知识视频讲解

Tendō·Pein

//建表不一定非要建立整张表
//建立输入的最大值以内的表即可
//需要注意建表的过程直接用余数就可以，否则溢出
//余数的计算满足线性约束即可
#include<iostream>
#include<vector>
#include<map>
using namespace std;
int main()
{
    long long num, m;
    cin >> num;
    map<long long, long long> table;//表的第一个数代表次序，第二个数代表余数
    table[1] = 1;
    table[2] = 2;
    table[3] = 5;
    while (num--)
    {
        cin >> m;
        if (table[m] == 0)
        {
            for (long long i = 3; i <= m; i++)
            {
                if (table[i] == 0)//检查建表的时候是否建立过，如果建过直接跳
                    table[i] = (table[i - 1] * 2 + table[i - 2]) % 32767;
            }
            cout << table[m] << endl;
        }
        else
            cout << table[m] << endl;
    }
    return 0;
}

编辑于 2019-03-18 16:47:02 回复(0)

Python

华科平凡

python解法

res = [1, 2]

for i in range(int(input())):
    k = int(input())  # 数列的第k项
    while len(res) < k:
        res.append(2 * res[-1] + res[-2])
    print(res[k - 1] % 32767)

运行时间：910ms

可以将模运算放在循环体中：

res = [1, 2]

for i in range(int(input())):
    k = int(input())  # 数列的第k项
    while len(res) < k:
        res.append((2 * res[-1] + res[-2])% 32767)
    print(res[k - 1] )

运行时间：367ms

发表于 2019-02-24 14:15:21 回复(0)

向宇回桌

好多题解说的玄乎其玄，打个表不就行了。

import java.util.*;

public class Main {
    private static final int MAX = 1000000 + 10;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] nums = new int[MAX]; nums[1] = 1; nums[2] = 2;
        for (int i=3; i<=MAX-5; i++) {
            nums[i] = (nums[i-1] * 2 + nums[i-2]) % 32767;
        }
        int T = sc.nextInt();
        while (T-- != 0) {
            System.out.println(nums[sc.nextInt()]);
        }
        return;
    }
}

发表于 2019-01-26 02:53:38 回复(2)

C/C++

一个好听的名字

//不得不提的是，看到这个求模递归类型的题，就想到可能会有个循环所以在此取巧
//事先编程处理(或者在程序内进行也可)
//进行取模的大量输出，然后寻找到循环的部分（通过判断再次连续出现的1,2来看循环）
//然后，复制粘贴，声明大数组。
//至于大数组的数量可以另外编一个很小的程序进行末端两位判断获取长度值。
//注意：这里把最末尾的循环数提到了数组零的位置，这样k直接取模就可以得到值
//另外，非取巧方法也有类似动态规划的思想，每一次都进行一个动态的存储（等等诸多细节）
#include <iostream>
using namespace std;
int main()
{
    int a[150] = {0, 1, 2, 5, 12, 29, 70, 169, 408, 985, 2378, 5741, 13860, 694, 15248, 31190, 12094, 22611, 24549, 6175, 4132, 14439, 243, 14925, 30093, 9577, 16480, 9770, 3253, 16276, 3038, 22352, 14975, 19535, 21278, 29324, 14392, 25341, 32307, 24421, 15615, 22884, 28616, 14582, 25013, 31841, 23161, 12629, 15652, 11166, 5217, 21600, 15650, 20133, 23149, 897, 24943, 18016, 28208, 8898, 13237, 2605, 18447, 6732, 31911, 5020, 9184, 23388, 23193, 4240, 31673, 2052, 3010, 8072, 19154, 13613, 13613, 8072, 29757, 2052, 1094, 4240, 9574, 23388, 23583, 5020, 856, 6732, 14320, 2605, 19530, 8898, 4559, 18016, 7824, 897, 9618, 20133, 17117, 21600, 27550, 11166, 17115, 12629, 9606, 31841, 7754, 14582, 4151, 22884, 17152, 24421, 460, 25341, 18375, 29324, 11489, 19535, 17792, 22352, 29729, 16276, 29514, 9770, 16287, 9577, 2674, 14925, 32524, 14439, 28635, 6175, 8218, 22611, 20673, 31190, 17519, 694, 18907, 5741, 30389, 985, 32359, 169, 32697, 29, 32755, 5, 32765, 1};
    int n = 0;
    cin >> n;
    long int k = 0;
    for (int i = 0; i < n; i++)
    {
        cin >> k;
        cout << a[k % 150] << endl;
    }
    return 0;
}

编辑于 2019-01-23 20:59:21 回复(0)

C/C++

项延皓

#include<bits/stdc++.h>
using namespace std;
int a[1000001];
int main(){
    int n;
    scanf("%d",&n);
    for(int i = 1;i <= 1000000;i++){
        if(i <= 2) a[i] = i;
        else a[i] = (2*a[i-1]+a[i-2])%32767; //在中间就应取模，防止溢出
    }
    while(n--){
        int k;
        scanf("%d",&k);
        printf("%d\n",a[k]);
    }
    return 0;
}
//由于数据范围明显，可以直接将每次计算的时间复杂度降为O(1)

编辑于 2020-07-25 20:21:08 回复(0)

平头哥，冲呀~

这个题有问题吧？我看打表的答案清一色的在建立数列的时候取余，但是在建立数列的时候取余就不是原来的数列了啊，比如说Ai为32767，Ai+1为32766，那Ai+2的值就应该是2*Ai+Ai+1,而不应该取余，若对结果取余后使其等于A1+2，则会影响Ai+3及以后的值，所以只能在输出的时候取余。望各位大佬解解惑.............................

发表于 2019-04-08 15:09:18 回复(1)

要暴富的肱二头肌很贪吃

注意可能有两个地方比较坑：1.不要用递归，否则会栈溢出； 2.value这个数组不要放在另一个for循环中，否则还是会超时（当时为了赶时间，就放在另一个for循环中了！！！）

发表于 2019-01-14 21:50:09 回复(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)

小陈也只是想要一个实习罢了

emmmm，考研复试好像有相似的题？反正就是读清楚题意，直接把得出的每一项都对32767取模，就不会超限了

#include<iostream>
using namespace std;
int main(){
    int n;
    int a[100000];
    a[1]=1;
    a[2]=2;
    for(int i=3;i<100000;i++)
        a[i]=(2*a[i-1]+a[i-2])%32767;
    while(cin>>n){
        int k;
        for(int i=0;i<n;i++){
            cin>>k;
            cout<<a[k]<<endl;
        }
    }
}

发表于 2019-02-11 20:18:31 回复(5)

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)

C++

小熊猫的黑眼圈

int main()

{

int n=0;

int k=0;

int a1=1;

int a2=2;

int a3=0;

cin>>n;

vector<int> v;

v.push_back(1);

v.push_back(2);

while(n--)

{

cin>>k;

int s=v.size();

if(k > s)

{

v.reserve(k);

int i=k-s;

a1=v[s-2];

a2=v[s-1];

while(i--)

{

a3=(2*a2+a1)%32767;

a1=a2;

a2=a3;

v.push_back(a3);

}

cout<<v[k-1]<<endl;

}

return 0;

}

发表于 2024-02-15 21:07:49 回复(0)

C++

神码_

#include <iostream>
using namespace std;
int a[1000000];
int main() {
    int n;
    cin>>n;
    for(int i=1;i<1000000;i++)
    {
        if(i<=2)
        {
            a[i]=i;
        }
        else {
        a[i]=(2*a[i-1]+a[i-2])%32767;
        }
    }
    while(n--)
    {
        int k;
        cin>>k;
        cout<<a[k]<<endl;
    }
}

好坑这个题目，不要用递归，然后测试用例变态，提前在算的时候%23767，就不会溢出

发表于 2023-08-30 15:12:27 回复(0)

秃驴应该痛

#include <stdio.h>

int main() {
    int arr[1000000]={1,2};
    for(int i=2;i<1000000;i++) {
        arr[i]=(2*arr[i-1]+arr[i-2])%32767;
    }
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++) {
        int k;
        scanf("%d",&k);
        printf("%d\n",arr[k-1]);
    }
    return 0;
}

发表于 2023-07-15 12:02:49 回复(0)

C++

demo·Dream

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    int num;
    vector<long> arr(1000000);
    arr[0] = 1;
    arr[1] = 2;
    for (int i = 2; i < 1000000; ++i) {
        arr[i] = (2 * arr[i - 1] + arr[i - 2]) % 32767; //存进去后面再取出来
    }
    cin >> n;
    while (n--) {
        cin >> num;
        cout << arr[num - 1] << endl;
    }
    return 0;
}

发表于 2023-01-07 12:24:52 回复(0)

C++

东条希尔薇233

每一项，我是真没想到

发表于 2022-02-04 17:33:25 回复(0)

JavaScript

牛客171145081号

var n = readline()
var numArr = new Array(2)
for(var j=0;j<n;j++){
    var k = readline()
    numArr[0] = 1
    numArr[1] = 2
    for(var i=2;i<k;i++){
       numArr[i] = (2*numArr[i-1] + numArr[i-2])%32767
    }
    print(numArr[k-1])
}

javascript一直超时，怎么解决啊"您的程序未能在规定时间内运行结束，请检查是否循环有错或算法复杂度过大。"

发表于 2020-07-22 10:26:40 回复(0)

Noir666

import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int n= in.nextInt();
        int [] arr = new int [n];
        int max = 0;
        for(int i= 0;i< n;i++){
            arr[i]= in.nextInt();
            if(arr[i]>max){
                max = arr[i];
            }
        }
        int [] s= new int [max+1];
        s[1]= 1;s[2]= 2;
        for(int i=3;i<max+1;i++){
            //之前在输出的时候取模，case：0.0%
            //计算的时候取模，就提交成功了
            //有没有大佬解释一下？？？？？？
            s[i]= (s[i-1]*2 + s[i-2])%32767;
        }
        for(int i=0;i<n;i++){
            System.out.println(s[arr[i]]);
        }
    }
}

发表于 2020-06-19 17:40:34 回复(0)

冬雪香莹

常规思路计算即可，中间的诀窍是循环次数不要直接套用输入，而是提前预置

#include<iostream>
using namespace std;
int main(){
    int n;
    int a[100000];
    a[1]=1;
    a[2]=2;
    for(int i=3;i<100000;i++)
        a[i]=(2*a[i-1]+a[i-2])%32767;
    while(cin>>n){
        int k;
        for(int i=0;i<n;i++){
            cin>>k;
            cout<<a[k]<<endl;
        }
    }
}

稳妥的方法还是建表，用多少建多少。

发表于 2019-05-31 11:12:53 回复(0)

Young~e

#include<iostream>
using namespace std;
int arr[1000005] = {0};
int main(){
   arr[0]=0;arr[1]=1;arr[2]=2;
    for(int i=3;i<=1000000;i++){
        arr[i] = (2*arr[i-1]+arr[i-2])%32767;
    }
    int n;scanf("%d\n",&n);
    while(n>0){
        int t; scanf("%d",&t);
        cout<<arr[t]<<endl;
        n--;
    }
}

发表于 2019-04-19 18:47:29 回复(0)

黄宗文

def kItem(k):
    maxk = max(k)            # 直接计算最大的k，避免了重复计算
    if maxk < 3:
        return [1, 2]
    dp = [0]*maxk
    dp[0], dp[1] = 1, 2
    for i in range(2, maxk):
        dp[i] = 2*dp[i-1] + dp[i-2]            # 最简单直接的动态规划
    return dp

if __name__ == "__main__":
    n = int(input())
    k = []
    for i in range(n):
        k.append(int(input()))
    dpk = kItem(k)
    for j in k:
        print(dpk[j-1]%32767)

发表于 2019-04-08 11:13:49 回复(0)