資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究檢查斐波那契類數列中第 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}$$
上面數列的第 4 個數字，其前兩個數字是 3 和 7，是 27，這是一個奇數。
接下來，我們需要找出斐波那契類數列的第 N 項是偶數還是奇數，其中我們將得到數列的前兩個數字和 N 的值作為輸入。
以下是我們可以遵循解決上述問題的方法。
方法
方法 1（使用陣列）
這是解決此問題的最基本和最簡單的方法。我們將像在示例輸入中所做的那樣找到數列的每個數字，直到 N，並將它們儲存在陣列中。然後，我們將檢查第 N 個數字是偶數還是奇數，並相應地列印輸出。
我們將遵循的方法的逐步說明 -
我們將建立一個函式來檢查數列的第 N 項。
使用 C++ 中的 MAX 函式建立一個最大長度的陣列。
使用 for 迴圈將數列的每個數字儲存在陣列中，直到 N。
檢查陣列中的第 N 項。如果它是偶數，則列印偶數，否則列印奇數。
示例
C++ 中方法的實現 -
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
//function to find out if the N-th term of the sequence is an even or odd number
void evenOrodd(int x, int y, int N){
int arr[N+1]={0}; //create an array of size 200
//store value of x and y at 0th and 1st index of array
arr[0]=x;
arr[1]=y;
for(int i=2;i<=N;i++){ //iterate through array until N and update corresponding
//value of the sequence at ith index
arr[i]=arr[i-1]+arr[i-2]; //using the formula
}
cout<<N<<"th term of the fibonacci-like sequence is : ";
//to check if it is an even or odd
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;
}
輸出
10th term of the fibonacci-like sequence is : Even 6th term of the fibonacci-like sequence is : Odd
時間複雜度：O(N)，因為我們迭代陣列直到 N。
空間複雜度：O(N)，因為我們建立了一個大小為 N+1 的陣列。
方法 2（觀察模式）
在這種方法中，我們將嘗試瞭解斐波那契類數列的第 N 項背後的模式。由於數列的每一項都是前兩項的和，因此第 N 項是偶數還是奇數取決於前兩項。它們的性質將取決於它們的前兩項。因此，第 N 項是偶數還是奇數的性質最終將取決於前兩項。
在這種方法中將有四種情況 -
1. 前兩項都是偶數。
2. 前兩項都是奇數。
3. 第一項是偶數，第二項是奇數。
4. 第一項是奇數，第二項是偶數。
情況 1 - 在第一種情況下，兩項都是偶數，即 $\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 處連續重複，可以用 3*a-1 表示，對於 a 的任何正值。因此，在這種情況下，$\mathrm{x_N}$ 將為偶數 N 可以表示為 (3*a-1)，對於 a 的任何正值，否則對於所有其他情況，$\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 的倍數處重複。因此，$\mathrm{x_N}$ 僅在 N 為 3 的倍數時為偶數，否則為奇數。
情況 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…. 處連續重複。這些可以用 3*a+1 表示，對於 a 的任何正值或 0。我們可以說，如果 N 的形式為 (3*a+1)，則數列的 𝑥𝑁 將為偶數，否則對於 N 的所有其他值，該數字將為奇數。
示例
C++ 中方法的實現 -
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
//function to check if N-th term of fibonacci-like sequence is even or odd
void evenOrodd(int x,int y,int N){
if(N==0){
if(x%2==0) //to check if it is even
cout<<"N-th term is : Even"<<endl;
else
cout<<"N-th term is : Odd"<<endl;
return;
}
if(N==1){
if(y%2==0)
cout<<"N-th term is : Even"<<endl;
else
cout<<"N-th term is : Odd"<<endl;
return;
}
if(x%2==0){ //if x is even
if(y%2==0){ //if y is even
cout<<"N-th term is : Even"<<endl;
}
else{
if(N%3==0) //if one term is even and other is odd
cout<<"N-th term is : Even"<<endl;
else
cout<<"N-th term is : Odd"<<endl;
}
return;
} else { //if x is odd
if(y%2!=0){ //if y is odd too
if((N+1)%3==0)
cout<<"N-th term is : Even"<<endl;
else
cout<<"N-th term is : Odd"<<endl;
}
else{ //if y is an even number
if((N-1)%3==0)
cout<<"N-th term is : Even"<<endl;
else
cout<<"N-th term is : Odd"<<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-th term is : Even N-th term is : Odd
時間複雜度：O(1)，因為檢查需要常數時間。
空間複雜度：O(1)，沒有佔用額外的空間。
結論
在本文中，我們學習瞭如何檢查斐波那契類數列的第 N 項是偶數還是奇數。我們嘗試使用兩種不同的方法來解決此問題，在第一種方法中，我們使用陣列找到直到 N 的數列並檢查第 N 項，而在第二種方法中，我們嘗試學習數列中遵循的模式。第二種方法是兩種方法中最有效的方法，因為它需要常數時間。我希望本文能幫助您學習解決此問題的概念，並發現本文對您有所幫助。
298 次瀏覽
