第六周-001:Pell數列

001:Pell數列

總時間限制: 

3000ms

記憶體限制: 

65536kB

描述

Pell數列a1, a2, a3, ...的定義是這樣的，a1 = 1, a2 = 2, ... , an = 2 * an − 1 + an - 2 (n > 2)。

給出一個正整數k，要求Pell數列的第k項模上32767是多少。

輸入

第1行是測試資料的組數n，後面跟着n行輸入。每組測試資料占1行，包括一個正整數k (1 ≤ k < 1000000)。

輸出

n行，每行輸出對應一個輸入。輸出應是一個非負整數。

樣例輸入

2
1
8
      

樣例輸出

1
408      

# define _CRT_SECURE_NO_DEPRECATE
#include <iostream>
using namespace std;

int main()
{
	int n;
	int m;
	long res[10000];
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
	{
		scanf("%ld", &m);
		long a[1000000];
		for (int j = 1; j <= m; j++)
		{
			if (j < 3)
			{
				a[j] = j;
			}
			else
			{
				a[j] = 2 * a[j - 1] + a[j - 2];
			}
		}
		res[i] = a[m] % 32767;
	}
	for (int i = 1; i <= n; i++)
	{
		printf("%ld\n", res[i]);
	}
	system("pause");
	return 0;
}
           

VS運作代碼，總是一閃而過，編譯運作都沒有彈出錯誤視窗，可能是因為設定了1000000個long型的數組，開辟的空間太大了，是以崩了。

度娘參考了一下：https://blog.csdn.net/qq_40486952/article/details/83154453

# define _CRT_SECURE_NO_DEPRECATE
#include <iostream>
using namespace std;

int main()
{
	int n;
	int m;
	int res[10000];
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
	{
		scanf("%ld", &m);
		long long a[3];
		if (m == 1)
		{
			res[i] = 1 % 32767;
		}
		else if (m == 2)
		{
			res[i] = 2 % 32767;
		}
		else
		{
			a[1] = 1;
			a[2] = 2;
			for (int j = 3; j <= m; j++)
			{
				a[3] = (2 * a[2] + a[1]) % 32767;
				a[1] = a[2];
				a[2] = a[3];
			}
			res[i] = a[3];
		}

	}
	for (int i = 1; i <= n; i++)
	{
		printf("%ld\n", res[i]);
	}
	system("pause");
	return 0;
}
           

結果運作成功。

總結一下：我感覺個人對于題目Pell數列的第k項模上32767是多少了解有歧義，我之前了解為Pell數列的最後1項第k項才需要模上32767，代碼運算的時候按照案例輸入8輸出結果為408符合要求，在測試過程中卻不對了，按題意要求對每一項都需要模上32767，這導緻了程式開始失敗