d437 - 10326 - The Polynomial Equation
題目描述
題目要求根據給定的根，生成對應的多項式並輸出。多項式的形式為 x^n + ... + c0 = 0，其中 n 是根的個數。輸出時需要注意以下幾點：
- 係數為 0 的項不輸出。
- 係數為 1 的項不輸出係數。
- 常數項為 0 時，輸出
+0。 - 使用
x^i表示x的i次方。
解題思路
這題的核心思想是利用多項式的根與係數之間的關係。給定 n 個根 r1, r2, ..., rn，則多項式可以表示為 (x - r1)(x - r2)...(x - rn)。程式碼通過迭代的方式，逐步將每個根納入多項式中。
- 初始化一個係數陣列
ans，表示多項式x^0 = 1。 - 遍歷每個根
a[i]。 - 對於每個根，將當前多項式
ans與(x - a[i])相乘。這相當於將ans中的每一項乘以x，然後加上ans中的每一項乘以-a[i]。 - 將新的多項式儲存在
nxt陣列中，然後更新ans陣列。 - 最後，遍歷
ans陣列，按照要求輸出多項式。
複雜度分析
- 時間複雜度: O(n^2)，其中 n 是根的個數。因為有兩層迴圈，分別用於遍歷根和多項式的係數。
- 空間複雜度: O(n)，因為需要一個大小為 n+1 的陣列
ans和nxt來儲存多項式的係數。
程式碼
#include <iostream>
using namespace std;
long long n,a[51];
int main(){
while(cin >> n){
long long ans[51]={1};
for(int i=0;i<n;++i)
cin >> a[i];
for(int i=0;i<n;++i){
long long nxt[51]={0};
for(int j=0;j<n;++j){
nxt[j+1]=ans[j];
nxt[j]+=ans[j]*a[i];
}
for(int j=0;j<=n;++j)
ans[j]=nxt[j];
}
for(int i=n,j=0;i>=0;--i,++j){
if(ans[i]==0&&i)continue;
if(i!=n){
bool j1=0;
if(ans[i]<0){
j1=1;
ans[i]*=-1;
}
if((j+j1)%2){
if(ans[i]==0)cout << "+ ";
else cout << "- ";
}
else
cout << "+ ";
}
if((ans[i]!=1&&ans[i])||i==0)cout << ans[i];
if(i>1)
cout << "x^" << i << " ";
else if(i==1)
cout << "x ";
else
cout << " ";
}
cout << "= 0\n";
}
}