a006 - 一元二次方程式

🔗 前往 ZeroJudge 原題

題目描述

本題要求解一元二次方程式 ax^2 + bx + c = 0 的根。輸入會給定三個整數 a, b, c，代表方程式的係數。程式需要根據判別式的值，輸出不同情境的結果：

1. 若有兩個相異實根，輸出 Two different roots x1=?? , x2=??，其中 x1 為較大的根，x2 為較小的根。
2. 若有兩個相同實根，輸出 Two same roots x=??。
3. 若無實根，輸出 No real root。 題目特別說明，所有答案均為整數。

解題思路

解一元二次方程式的核心是使用二次公式：x = (-b ± sqrt(b^2 - 4ac)) / 2a。 其中，判別式 D = b^2 - 4ac (在程式碼中用 k 表示) 的值決定了根的性質：

1. 當 D > 0 時：方程式有兩個相異的實根。

   • x1 = (-b + sqrt(D)) / (2a)
   • x2 = (-b - sqrt(D)) / (2a) 程式碼中會先計算 k = b*b - 4*a*c。如果 k > 0，則計算這兩個根。為了確保 x1 是較大的根，x2 是較小的根，程式碼會比較 (-b + sqrt(k)) / (2a) 和 (-b - sqrt(k)) / (2a) 的大小。由於 sqrt(k) 是正數，通常 (-b + sqrt(k)) / (2a) 會大於 (-b - sqrt(k)) / (2a) (若 a > 0)。根據比較結果，將較大的值指定給 x1，較小的值指定給 x2 並輸出。

2. 當 D = 0 時：方程式有兩個相同的實根。

   • x = -b / (2a) 程式碼中判斷 k == 0 時，直接計算並輸出唯一的實根。

3. 當 D < 0 時：方程式無實根 (有共軛複數根)。 程式碼中判斷 k < 0 時，輸出 No real root。

整個過程會使用 while(cin >> a >> b >> c) 迴圈處理多組輸入，直到輸入結束。

複雜度分析

• 時間複雜度: 對於每組輸入，程式執行固定次數的算術運算（加、減、乘、除）和一個平方根運算 (sqrt)。這些操作通常被視為常數時間操作。因此，處理一個測試案例的時間複雜度是 O(1)。如果總共有 N 組測試案例，則總時間複雜度為 O(N)。
• 空間複雜度: 程式只使用了固定數量的變數來儲存輸入係數和中間計算結果 (a, b, c, k)。這些變數所需的記憶體空間是固定的，不隨輸入規模而變化。因此，空間複雜度是 O(1)。

程式碼

#include <iostream>
#include <math.h>

using namespace std;

int main (){
	
	int a=0,b=0,c=0;
	
	while(cin >> a >> b >> c){
		double k=(b*b-4*a*c);
		if (k>0){
			cout << "Two different roots x1=";
			if((-b+sqrt(k))/2*a>(-b-sqrt(k))/2*a) {
				cout << (-b+sqrt(k))/2*a << " , x2=" << (-b-sqrt(k))/(2*a) <<endl;
			}
			else{
				cout << (-b-sqrt(k))/2*a << " , x2=" << (-b+sqrt(k))/(2*a) <<endl;
			}
		}
		else if (k==0){
			cout << "Two same roots x=" << -b/(2*a) <<endl;
		}
		else if (k<0){
			cout << "No real root" <<endl;
		}
	} 
	
}