返回列表 發帖

資料結構 105 多項式的鏈結串列表示與相加

資料結構 105 多項式的鏈結串列表示與相加
1. 題目說明:
請依下列題意進行作答,使輸出值符合題意要求。


2. 設計說明:
(1) 一個二元多項式是由多個項組成的,每個項包含三個整數:係數、x 的指數和 y 的指數。需要使用鏈結串列(Linked list)來實作這個多項式的儲存和操作,並完成以下功能:

多項式的鏈結表示:每個節點(或稱為「項」)應包含係數 a、x 的指數 b 和 y 的指數 c,以及指向下一個節點的指針。每一項定義如下:ax^by^c

多項式是由多個「項」組合而成,當使用者輸入一列整數資料代表一個多項式,其中每三個整數代表「一項」。如果新項的 x 和 y 指數已經存在於多項式中,則應將它們的係數相加。

例如:輸入「4 4 0 -5 2 1 2 2 1」,代表為多項式:4x^4y^0-3x^2y^1

多項式相加:實作一個方法來相加兩個多項式,並返回一個新的多項式作為結果。

格式化輸出:輸出結果先依照 x 的指數降冪排序,再依照 y 的指數降冪排序。如果係數是負數,則其前面不應顯示加號。

提示:請利用鏈結串列(Linked list)來實作,有指標的程式語言可利用指標方式實作,有物件導向的程式語言可利用類別來實作。

3. 輸入輸出:
輸入說明
第 1 列:輸入一個正整數 N(2 ≤ N ≤ 10),代表有 N 個二元多項式相加。
第 2~N+1 列:每一列代表一個多項式,每一項有三個整數 a、b、c,所有整數間以一個半形空白間隔。若有 M 組 a、b、c 代表多項式有 M 項。

輸出說明
逐列呈現 N 個二元多項式,並計算所有多項式相加的結果。

註:

多項式的呈現順序,先以 x 的指數降冪排序,再以 y 的指數降冪排序。
次方請以「^」符號表示。例如: 則顯示「10x^5y^4+3x^5y^1-6x^4y^4+1x^3y^0」。
若係數為負數,則其前面不應顯示加號;若係數為 0,則不顯示該項;若係數非 0,則一律顯示係數值。
範例輸入1
2
3 2 1 -4 1 3 8 0 0
7 2 1 -2 1 4 5 1 3
範例輸出1
3x^2y^1-4x^1y^3+8x^0y^0
7x^2y^1-2x^1y^4+5x^1y^3
Sum:10x^2y^1-2x^1y^4+1x^1y^3+8x^0y^0
範例輸入2
3
1 1 0 5 4 3 2 1 0
3 3 3 2 2 2 -1 1 0
3 2 1 -1 1 0 1 0 0 3 0 0
範例輸出2
5x^4y^3+3x^1y^0
3x^3y^3+2x^2y^2-1x^1y^0
3x^2y^1-1x^1y^0+4x^0y^0
Sum:5x^4y^3+3x^3y^3+2x^2y^2+3x^2y^1+1x^1y^0+4x^0y^0
附件: 您需要登錄才可以下載或查看附件。沒有帳號?註冊
May

回復 1# may
  1. //#include <iostream>
  2. //#include <vector>
  3. //#include <map>
  4. //#include <sstream>
  5. //#include <algorithm>
  6. #include <bits/stdc++.h>
  7. using namespace std;

  8. // 定義每一項結構
  9. struct Term {
  10.     int coef; // 係數
  11.     int xExp; // x 的指數
  12.     int yExp; // y 的指數
  13. };

  14. // 比較函式:先比 x 降冪,再比 y 降冪
  15. bool compare(const Term &a, const Term &b) {
  16.     if (a.xExp != b.xExp)
  17.         return a.xExp > b.xExp;
  18.     return a.yExp > b.yExp;
  19. }

  20. // 印出一個多項式
  21. void printPolynomial(const map<pair<int, int>, int> &poly) {
  22.     vector<Term> terms;

  23.     for (auto it : poly) {
  24.         if (it.second != 0) {
  25.             terms.push_back({it.second, it.first.first, it.first.second});
  26.         }
  27.     }

  28.     // 排序:先比 x 再比 y(都為降冪)
  29.     sort(terms.begin(), terms.end(), compare);

  30.     bool first = true;
  31.     for (auto &t : terms) {
  32.         if (!first && t.coef > 0)
  33.             cout << "+";
  34.         cout << t.coef << "x^" << t.xExp << "y^" << t.yExp;
  35.         first = false;
  36.     }

  37.     if (terms.empty()) cout << "0"; // 若全部為 0,顯示 0
  38.     cout << endl;
  39. }

  40. int main() {
  41.     int N;
  42.     cin >> N;
  43.     cin.ignore(); // 清除換行字元

  44.     vector<map<pair<int, int>, int>> polys(N); // 每個多項式都用一個 map 存

  45.     // 逐列讀取每一個多項式
  46.     for (int i = 0; i < N; i++) {
  47.         string line;
  48.         getline(cin, line);
  49.         istringstream iss(line);

  50.         int a, b, c;
  51.         while (iss >> a >> b >> c) {
  52.             polys[i][{b, c}] += a;
  53.         }
  54.     }

  55.     // 輸出每個多項式
  56.     for (int i = 0; i < N; i++) {
  57.         printPolynomial(polys[i]);
  58.     }

  59.     // 計算總和
  60.     map<pair<int, int>, int> total;
  61.     for (int i = 0; i < N; i++) {
  62.         for (auto it : polys[i]) {
  63.             total[it.first] += it.second;
  64.         }
  65.     }

  66.     cout << "Sum:";
  67.     printPolynomial(total);

  68.     return 0;
  69. }
複製代碼
May

TOP

回復 2# may
解說(搭配上面的程式碼):
資料結構設計
使用 map<pair<int,int>, int>:

pair<int,int> 存的是 (x 指數, y 指數)

int 是這一項的係數

多項式相加
相同 (x, y) 指數的項目會自動相加(因為是用 map 儲存)

如果有重複的 (x, y),就會直接相加進 map 裡

排序輸出
把 map 裡面的內容丟進 vector

排序規則是:先比 x 降冪,再比 y 降冪

輸出格式
第一項前面不加 +

後面項目若是正的就加 +,負的自動顯示 -

次方使用 x^、y^ 格式呈現

範例輸入:

2
3 2 1 -4 1 3 8 0 0
7 2 1 -2 1 4 5 1 3
對應輸出:

3x^2y^1-4x^1y^3+8x^0y^0
7x^2y^1-2x^1y^4+5x^1y^3
Sum:10x^2y^1-2x^1y^4+1x^1y^3+8x^0y^0
May

TOP

問題一:關鍵程式碼解說

回復 3# may
  1. for (auto it : poly) {
  2.         if (it.second != 0) {
  3.             terms.push_back({it.second, it.first.first, it.first.second});
  4.         }
  5.     }
複製代碼
-------------------------------------
背景說明:
poly 是一個 map<pair<int, int>, int>:

每一項的 key 是 pair<int, int>(代表 x 的指數 和 y 的指數)

每一項的 value 是 int(代表這一項的 係數)
例如:
poly[{2, 1}] = 3; // 表示 3x^2y^1
poly[{1, 3}] = -4; // 表示 -4x^1y^3
--------------------------------------
for 迴圈解釋:
for (auto it : poly)
這行是 C++ 的範圍式 for 迴圈(range-based for loop),會把 poly map 中的每一筆資料逐一取出:

it 的型別其實是 pair<pair<int, int>, int>
因為:

key 是 pair<int, int>(代表指數:x, y)

value 是 int(代表係數)
-----------------------------
條件篩選:if (it.second != 0)
it.second 是這一項的「係數」

若係數是 0,就不處理它(因為 0 不需要顯示在多項式中)

若不是 0,就加入 terms 向量中
-------------------------
重點:加入 terms 向量
terms.push_back({it.second, it.first.first, it.first.second});
這句的意思是把這項轉成 Term 結構並加入 terms 向量中。

it.second // 係數 coef

it.first.first // x 的指數 xExp

it.first.second // y 的指數 yExp

也就是:
Term t;
t.coef = it.second;
t.xExp = it.first.first;
t.yExp = it.first.second;
terms.push_back(t);
整段功能總結:
這段程式碼的功能是:
把多項式中「係數不為 0」的項目轉換成 Term 結構,並儲存到 terms 向量中,準備後續排序與輸出。
---------------------------
舉個例子(假設 poly 裡面資料是這樣):
poly = {
    {{2, 1}, 3},
    {{1, 3}, -4},
    {{0, 0}, 0}  // 這項會被略過
};
則這段程式執行完後:
terms = {
    {3, 2, 1},   // 3x^2y^1
    {-4, 1, 3}   // -4x^1y^3
};
May

TOP

測資

回復 4# may
測資:
測資 00:
2
3 2 1 -4 1 3 8 0 0
7 2 1 -2 1 4 5 1 3
預期輸出:
3x^2y^1-4x^1y^3+8x^0y^0
7x^2y^1-2x^1y^4+5x^1y^3
Sum:10x^2y^1-2x^1y^4+1x^1y^3+8x^0y^0
測資 01:
3
1 1 0 5 4 3 2 1 0
3 3 3 2 2 2 -1 1 0
3 2 1 -1 1 0 1 0 0 3 0 0
預期輸出:
5x^4y^3+3x^1y^0
3x^3y^3+2x^2y^2-1x^1y^0
3x^2y^1-1x^1y^0+4x^0y^0
Sum:5x^4y^3+3x^3y^3+2x^2y^2+3x^2y^1+1x^1y^0+4x^0y^0
測資 02:
2
2 1 1 4 2 2 1 0 0
-2 1 1 -1 0 0
預期輸出:
4x^2y^2+2x^1y^1+1x^0y^0
-2x^1y^1-1x^0y^0
Sum:4x^2y^2
測資 03:
4
1 3 2 2 2 2
-1 3 2 3 1 1
5 0 0
-3 1 1 -2 2 2
預期輸出:
1x^3y^2+2x^2y^2
-1x^3y^2+3x^1y^1
5x^0y^0
-2x^2y^2-3x^1y^1
Sum:0x^3y^2+0x^2y^2+0x^1y^1+5x^0y^0
Sum:5x^0y^0
測資 04:
3
5 5 5 -3 2 2
1 5 5 -1 2 2
2 1 1 3 0 0
預期輸出:
5x^5y^5-3x^2y^2
1x^5y^5-1x^2y^2
2x^1y^1+3x^0y^0
Sum:6x^5y^5-4x^2y^2+2x^1y^1+3x^0y^0
May

TOP

返回列表