检查斐波那契类数列中的第 n 项是奇数还是偶数
我们在这个问题中的任务是检查斐波那契类数列中的第 n 项是奇数还是偶数。斐波那契数列是数学中的一种数列，其中数列中的每个数字都是前两个数字的总和。
斐波那契数列的第 n 项可以表示为 −
$$\mathrm{Fn\:=\:F_{n-1}\:+\:F_{n-2}}$$
斐波那契数列的前几个数字是 0、1、1、2、3、5、8、13、21、34….。
该数列的前两个数字是 0 和 1。正如我们在数列中看到的那样，接下来的数字是前两个数字的总和。
类似地，在这个问题中，我们将得到一个类似斐波那契的数列，其中数列中的每个数字都等于前两个数字的总和。
我们将给定斐波那契数列的前两项，假设和以及一个正数 N 作为输入。我们需要弄清楚在这个问题中是奇数还是偶数。
斐波那契数列的第 N 项可以由给出，这与第 N 个斐波那契数相同，因为它遵循与斐波那契数列相同的模式。
让我们通过几个例子更好地理解这个问题
输入:$\mathrm{x_0}$=2，$\mathrm{x_1}$=4，N=5
输出:偶数
解释 - 由于序列的前两项是给定的，即输入中的 2 和 4。要计算序列的第 N 项，即第 5 项，我们需要计算直到第 5 项的所有项。因此，可以使用第 N 项公式找到该序列的下一项项。
$$\mathrm{x_2\:=\:x_1\:+\:x_0\:=\:2\:+\:4\:=\:6}$$
$$\mathrm{x_3\:=\:x_2\:+\:x_1\:=\:6\:+\:4\:=\:10}$$
$$\mathrm{x_4\:=\:x_3\:+\:x_2\:=\:10\:+\:6\:=\:16}$$
$$\mathrm{x_5\:=\:x_4\:+\:x_3\:=\:16\:+\:10\:=\:26}$$
由于序列的第 5 项为 26，因此是偶数
输入:$\mathrm{x_0}$=3，$\mathrm{x_1}$=7，N=4
输出:奇数
解释 − 使用第 N 个斐波那契数列公式，斐波那契数列的下一个项直到 4 是−
$$\mathrm{x_2\:=\:x_1\:+\:x_0\:=\:7\:+\:3\:=\:10}$$
$$\mathrm{x_3\:=\:x_2\:+\:x_1\:=\:10\:+\:7\:=\:17}$$
$$\mathrm{x_4\:=\:x_3\:+\:x_2\:=\:17\:+\:10\:=\:27}$$
上述数列的前两个数分别为 3 和 7，其第 4 个数为 27，为奇数。
同样，我们需要确定斐波那契数列的第 N 项是偶数还是奇数，其中我们将获得序列的前两个数字和 N 的值作为输入。
以下是解决上述问题的方法。
方法
方法 1(使用数组)
这是解决此问题最基本、最简单的方法。我们将以与示例输入相同的方式找到序列中的每个数字，直到 N 并将它们存储在数组中。然后，我们将检查第 N 个数字是偶数还是奇数，并相应地打印输出。
我们将遵循的方法的分步说明 −
我们将创建一个函数来检查序列的第 N 项。
使用 C++ 中的 MAX 函数创建一个最大长度的数组。
使用 for 循环将序列的每个数字存储在数组中，直到 N。
检查数组中的第 N 项。如果它是偶数，则打印偶数，否则打印奇数。
示例
在 C++ 中实现该方法 −
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
//函数用于确定序列的第 N 项是偶数还是奇数
void evenOrodd(int x, int y, int N){
int arr[N+1]={0}; //创建一个大小为 200 的数组
//将 x 和 y 的值存储在数组的第 0 和第 1 个索引处
arr[0]=x;
arr[1]=y;
for(int i=2;i<=N;i++){ //遍历数组直到 N 并更新相应的
//第 i 个索引处的序列值
arr[i]=arr[i-1]+arr[i-2]; //使用公式
}
cout<<N<<"类似斐波那契的序列的第 1 项是 : ";
//检查它是偶数还是奇数
if(arr[N]%2==0){
cout<<"Even"<<endl;
} else {
cout<<"Odd"<<endl;
}
}
int main(){
int x=3, y=8, N=10;
evenOrodd(x,y,N);
x=7, y=13, N=6;
evenOrodd(x,y,N);
return 0;
}
输出
斐波那契类序列的第 10 项为:偶数 斐波那契类序列的第 6 项为:奇数
时间复杂度:O(N)，因为我们迭代数组直到 N。
空间复杂度:O(N)，因为我们创建了一个大小为 N+1 的数组。
方法 2(观察模式)
在这种方法中，我们将尝试了解斐波那契类序列第 N 项背后的模式。由于序列的每个项都是前两个项的总和，因此第 N 项是偶数还是奇数取决于前两个项。而它们的性质将取决于它们的前两个项。因此，第 N 项的性质(是偶数还是奇数)最终取决于前两项。
这种方法有四种情况 −
1. 前两项都是偶数。
2. 前两项都是奇数。
3. 第一项是偶数，第二项是奇数。
4.第一项为奇数，第二项为偶数。
情况 1 − I第一种情况下，两个项均为偶数，即 $\mathrm{x_0}$ 和 $\mathrm{x_1}$。在这种情况下，序列中的任何数字都将是偶数，因为两个偶数之和始终为偶数。
例如，如果 $\mathrm{x_0}$=2 且 $\mathrm{x_1}$=4，则序列将为 2、4、6、10、16、26、42…。
情况 2 − 对于这种情况，两个初始项都将是奇数。两个奇数之和将始终得出偶数。因此，在这种情况下，$\mathrm{x_2}$ 将始终为偶数。此外，$\mathrm{x_3}$ 将是一个奇数，因为偶数和奇数之和将始终得出奇数。让我们通过一个例子来理解这种模式:$\mathrm{x_0}$=1 和 $\mathrm{x_1}$=3。因此，该序列的下一项将是，$\mathrm{x_2}$=4、$\mathrm{x_3}$=7、$\mathrm{x_4}$=11、$\mathrm{x_5}$=18、$\mathrm{x_6}$=29、$\mathrm{x_7}$=47、$\mathrm{x_8}$=76…..
查看模式，我们可以观察到偶数在 N=2,5,8 处不断重复，对于 a 的任何正值，可以以 3*a-1 的形式表示。因此在这种情况下，$\mathrm{x_N}$ 将为偶数，对于 a 的任何正值，N 可以表示为 (3*a-1)，否则，对于所有其他情况，$\mathrm{x_N}$ 将为奇数。
案例3 − 在这种情况下，第一项为偶数，第二项为奇数。任何偶数和奇数之和总是奇数。下一个项为偶数，因为前两个项为奇数。让我们尝试通过一个例子来理解这种情况的模式，$\mathrm{x_0}$=2 和 $\mathrm{x_1}$=3。该序列的后几项将是，
$\mathrm{x_2}$=5, $\mathrm{x_3}$=8, $\mathrm{x_4}$=13, $\mathrm{x_5}$=21, $\mathrm{x_6}$=34, $\mathrm{x_7}$=55, $\mathrm{x_8}$=89, $\mathrm{x_9}$=144……
我们可以看到偶数项仅在 3 的倍数处重复。因此，只有当 N 是 3 的倍数时，$\mathrm{x_N}$ 才是偶数，否则它将是奇数。
情况 4 − 这个适用于第一项为奇数而第二项为偶数的情况。让我们通过一个例子来研究这种模式，$\mathrm{x_0}$=1 和 $\mathrm{x_1}$=2。序列中的前几个数字将是，
$\mathrm{x_2}$=3, $\mathrm{x_3}$=5, $\mathrm{x_4}$=8, $\mathrm{x_5}$=13, $\mathrm{x_6}$=21, $\mathrm{x_7}$=34, $\mathrm{x_8}$=55, $\mathrm{x_9}$=89, $\mathrm{x_10}$=144……
观察模式，我们可以得出结论，偶数在 N=4,7,10… 处不断重复。对于任何正值 a 或 0，这些都可以表示为 3*a+1 的形式。我们可以说，如果 N 的形式为 (3*a+1)，𝑥𝑁 将是序列的偶数，否则对于所有其他 N 值，该数字将是奇数。
示例
该方法在 C++ 中的实现 −
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
//函数用于检查斐波那契类序列的第 N 项是偶数还是奇数
void evenOrodd(int x,int y,int N){
if(N==0){
if(x%2==0) //to check if it is even
cout<<"第 N 项为 : 偶数"<<endl;
else
cout<<"第 N 项为 : 奇数"<<endl;
return;
}
if(N==1){
if(y%2==0)
cout<<"第 N 项为 : 偶数"<<endl;
else
cout<<"第 N 项为 : 奇数"<<endl;
return;
}
if(x%2==0){ //if x is even
if(y%2==0){ //if y is even
cout<<"第 N 项为 : 偶数"<<endl;
}
else{
if(N%3==0) //if one term is even and other is odd
cout<<"第 N 项为 : 偶数"<<endl;
else
cout<<"第 N 项为 : 奇数"<<endl;
}
return;
} else { //if x is odd
if(y%2!=0){ //if y is odd too
if((N+1)%3==0)
cout<<"第 N 项为 : 偶数"<<endl;
else
cout<<"第 N 项为 : 奇数"<<endl;
}
else{ //if y is an even number
if((N-1)%3==0)
cout<<"第 N 项为 : 偶数"<<endl;
else
cout<<"第 N 项为 : 奇数"<<endl;
}
return;
}
}
int main(){
int x=6,y=10,N=7;
evenOrodd(x,y,N);
x=13, y=16, N=5;
evenOrodd(x,y,N);
return 0;
}
输出
第 N 项为 : 偶数 第 N 项为 : 奇数
时间复杂度:O(1)，因为检查需要花费恒定的时间。
空间复杂度:O(1)，不占用额外空间。
结论
在本文中，我们学习了如何检查斐波那契数列的第 N 项是偶数还是奇数。我们尝试使用两种不同的方法解决这个问题，其中在第一种方法中，我们使用数组来查找直到 N 的序列并检查第 N 项，而在第二种方法中，我们尝试学习序列中遵循的模式。第二种方法是两种方法中最有效的方法，因为它需要恒定的时间。我希望本文能帮助您学习解决这个问题的概念，并发现本文很有帮助。
