🔗 UVA-392 Polynomial Showdown

tags: `模擬(Simulation)`

範例程式碼已於UVA、瘋狂程設(CPE)、ZeroJudge 上皆測試通過。

題意

給定一個長度為 $9$ 的整數陣列，代表一個多項式的係數，輸出多項式的字串表示。

思路：模擬(Simulation)

直接模擬多項式的輸出過程即可，注意輸出格式即可：
- 係數為 $0$ 的項不用輸出。
- 第一項前面不用加運算符，只有第一項的係數為負數時才需要輸出負號。
- 係數為 $1$ 的項不用輸出係數部分。
- 次方為 $1$ 的項不用輸出次方部分。
- 次方為 $0$ 的項只需要輸出係數部分即可。
- 全部係數為 $0$ 的話代表多項式為 $0$ ，直接輸出 $0$ 即可。
時間複雜度： $O(N)$ ， $N$ 為多項式的最高次方數，本題 $N = 8$ 。
空間複雜度： $O(N)$

N = 8
while True:
	try:
		coef = list(map(int, input().split()))
	except EOFError:
		break
	if all(c == 0 for c in coef): # 特判
		print(0)
		continue
	flag = False # 前面是否有其他項
	for i, x in enumerate(coef):
		if not x:
			continue
		if flag:
			print(" + " if x > 0 else " - ", end = "") 
		else:
			if x < 0:
				print("-", end = "") 
			flag = True
		x = abs(x) # 係數部分
		m = N - i # 次方
		if x != 1 or m == 0:
			print(x, end = "") 
		if m > 1:
			print(f"x^{m}", end = "") 
		elif m == 1:
			print("x", end = "") 
	print()

#include <bits/stdc++.h>
using namespace std;
const int N = 9;
#define endl '\n'

int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	int x, coef[N];
	while (cin >> x) {
		coef[0] = x;
		for (int i = 1; i < N; i++) cin >> coef[i];
		// 先特判是不是全為 0 ，如果是的話直接輸出 0
		bool all_zero = true;
		for (int i = 0; i < N; i++) {
			if (coef[i]) {
				all_zero = false;
				break;
			}
		}
		if (all_zero) {
			cout << 0 << endl;
			continue;
		}
		// 輸出多項式
		bool flag = false; // 第一項前面不用加 + 或 - ，所以 flag = false
		for (int i = 0; i < N; i++) {
			if (!coef[i]) {
				continue;
			}
			if (flag) { // 不是第一項
				cout << (coef[i] > 0 ? " + " : " - ");
			} else { // 是第一項
				if (coef[i] < 0) {
					cout << "-";
				}
				flag = true;
			}
			int x = abs(coef[i]); // 係數部分
			int m = N - 1 - i; // 次方
			if (x != 1 || m == 0) { // 係數部分不是 1 或是次方是 0 的話才輸出係數部分
				cout << x;
			}
			if (m > 1) { // 次方大於 1 才輸出次方
				cout << "x^" << m;
			} else if (m == 1) {
				cout << "x";
			}
		}
		cout << endl;
		
	}
	return 0;
}