a005 - Eva 的回家作業
題目描述
本題要求根據給定的數列前四項，判斷該數列是等差數列還是等比數列，然後計算並輸出其第五項。輸入的第一行是一個整數 t，表示總共有 t 個數列。接下來的 t 行，每行包含四個整數，分別是數列的前四項。題目保證數列的前五項均為不大於 $10^5$ 的自然數，且等比數列的比值也是自然數。對於每個數列，輸出它的前五項。
解題思路
本題的核心在於判斷給定數列的類型（等差或等比），然後根據其類型計算第五項。由於題目明確指出數列「只可能是等差或等比數列」，我們可以使用條件判斷來實現。
令數列的前四項為 $A_1, A_2, A_3, A_4$ (在程式碼中對應 b, c, d, e)。
-
判斷是否為等比數列 (Geometric Progression, GP)：
- 如果是一個等比數列，那麼其公比 $r$ 必須是相同的。即 $A_2/A_1 = A_3/A_2 = A_4/A_3$。
- 由於題目約定等比數列的比值是自然數，我們不需要擔心浮點數計算。
- 我們可以檢查 $A_4/A_3$ 是否等於 $A_3/A_2$，並且 $A_4$ 必須能被 $A_3$ 整除。
- 在程式碼中，
e/d == d/c && e%d == 0就是這個判斷邏輯。如果這個條件成立，說明這是一個等比數列，公比為d/c。第五項 $A_5$ 則為 $A_4 \times (A_3/A_2)$，即e * (d/c)。
-
判斷是否為等差數列 (Arithmetic Progression, AP)：
- 如果不是等比數列，那麼根據題意，它必然是等差數列。
- 等差數列的公差 $diff$ 必須是相同的。即 $A_2-A_1 = A_3-A_2 = A_4-A_3$。
- 我們可以檢查 $A_4-A_3$ 是否等於 $A_3-A_2$。
- 在程式碼中，
else if((e-d) == (d-c))就是這個判斷邏輯。如果這個條件成立（或者在前一個等比判斷不成立的情況下，這就是等差數列），公差為d-c。第五項 $A_5$ 則為 $A_4 + (A_3-A_2)$，即e + (d-c)。
由於題目保證數列只可能是等差或等比，並且要求輸出前五項。程式碼的邏輯是先判斷等比數列，如果不滿足條件，則判斷等差數列。這種順序是合理的，因為有些特殊情況（例如 $1, 1, 1, 1$）可能同時滿足兩種條件，但第五項的計算結果是相同的。
複雜度分析
- 時間複雜度:
O(t)對於每個測試案例，程式執行固定次數的算術運算（加減乘除）和比較運算。這些操作的時間複雜度是常數O(1)。總共有t個測試案例，因此整體時間複雜度為O(t)。由於t最大為 20，程式執行非常快速。 - 空間複雜度:
O(1)程式中只使用了少量固定數量的整數變數來儲存輸入值和中間計算結果，這些變數佔用的記憶體空間是常數，不隨輸入規模t變化。
程式碼
#include <iostream>
using namespace std;
int main (){
int a;
int b=0,c=0,d=0,e=0;
cin >> a;
while(cin >> b >> c >> d >> e){
if(e/d==d/c&&e%d==0){
cout << b << " " << c << " " << d << " " << e << " " << e*(d/c) <<endl;
}
else if((e-d)==(d-c)){
cout << b << " " << c << " " << d << " " << e << " " << e+(d-c) <<endl;
}
}
}