PTA L2-018 多項式A除以B

• 題目網址：https://pintia.cn/problem-sets/994805046380707840/exam/problems/994805060372905984

• 題目概述：

  這一道題首先得知道多項式除法，怎麼弄得，這個高中其實都學過，在分解多項式那一個環節。這道題每次都拿除多項式的最高次幂（階數）項去消掉被除多項式，而後剩下的項則與被除多項式進行相加減。

• 存儲結構：
  1. 采用下标記錄階數，裡面的值記錄系數。
  2. 開一個差不多1000000的數組夠用了，針對本題。
• 注意事項：
  1. 我們可以直接用浮點數來進行計算，沒必要用分數，c++浮點數能存儲5位（好像是），足夠我們判斷是否需要舍去。對于輸出無論用

     cout

     還是

     printf

     都可以，保留一位小數即可，注意這裡隻對那些大于等于

     0.05

     的數進行保留。
  2. 注意隻有當被除多項式的最高階數大于等于除多項式的階數時才可以進行除法，否則商直接就是0多項式，而餘數直接就是原來的被除多項式。（這種情況不需要進行舍入，因為系數都是整數）
  3. 可以除的情況下，每次都需要知道目前所做除法的被除數最高階數是多少，其實就直接從被除數最高階開始遞減，隻要階數對應下标所存儲的值不為0，說明被除數這邊有值進而進行除法（題目所給的資料是階數是遞減的，不存在一個階數出現兩次的情況，是以在運算過程中被除數一直在變化，階數一直在遞減）
  4. 可以除的情況下：設定循環

     while(max1>=max2)

     目前情況的被除數階數大于等于除數，從最高階開始，對存儲被除數的數組開始進行操作，max1為目前情況被除數的最高階，max2始終就是除數的最高階，求出max1-max2的值（max1!=0），就更改被除數數組，存儲商 = 目前情況被除數最高階系數 / 除數最高階系數。
  5. 注意對于除法過程中不需要先進行判斷是否舍去，從除法結束後開始。
  6. 除法結束後，必須要知道商和餘數符合輸出條件的個數，不然為0的話需要直接輸出0多項式。記住，這裡的商和餘數都需要進行判斷。得到個數後再進行一遍循環判斷并輸出。
• 關于測試點：
  1. 沒有被除數為0多項式的測試案例，除數也沒有為0多項式。（不然輸入的形式都得再加一層判斷）
  2. 測試點4：必須要判斷商的系數的是否大于等于0.05。
• 代碼（上面語言有點粗糙，大家看代碼應該能看懂）

  #include <iostream>
  #include <iomanip>
  using namespace std;
  double xishu1[10000000], xishu2[10000000];
  double outxishu1[10000000];
  
  int main()
  {
      double x = 0.05;
      cout << setiosflags(ios::fixed) << setprecision(1);
      
      int N1 = -1, N2 = -1;
      int max1, max2;
      int countRemainNum = 0, countDivNum = 0;
      int temp;
      int maxE; //記錄被除數的最大次數，不會變這個值。
      int dis = 0;
      cin >> N1;
  
      for (int i = 1; i <= N1; i++)
      {
          cin >> temp;
          cin >> xishu1[temp];
          if (i == 1)
          {
              max1 = temp; // 底下出發循環再變
              maxE = max1; // 不變的
          }
      }
  
      cin >> N2;
      for (int i = 1; i <= N2; i++)
      {
          cin >> temp;
          cin >> xishu2[temp];
          if (i == 1)
          {
              max2 = temp;
          }
      }
  
      // 直接被除數小于除數的情況
      if (max1 < max2)
      {
          int y = 0;
          cout << y << " " << y << " " << 0.0 << endl;
          countDivNum = N1;
          cout << N1 << " ";
          for (int i = max1; i >= 0; i--)
          {
              if (abs(xishu1[i]) > 0)
              {
                  cout << i << " " << xishu1[i];
                  countDivNum--;
                  if (countDivNum > 0)
                  {
                      cout << " ";
                  }
              }
          }
  
          return 0;
      }
  
      // 正常情況，被除數大于除數的情況
      double xishu;
      // 一旦被除數的最大系數小于除數的最大系數時，除法結束。
      while (max1 >= max2)
      {
  
          if (xishu1[max1] == 0)
          {
              max1--;
              continue;
          }
  
          // dis就是此次運算階數的內插補點，作為outxishu1數組的下标。
          dis = max1 - max2;
          xishu = xishu1[max1] / xishu2[max2];
  		
          // 得到商中能夠輸出的個數（也可以除法結束後再周遊存儲商的數組outxishu1進行判斷計數）
          if (abs(xishu) >= x)
          {
              outxishu1[dis] = xishu;
              countDivNum++;
          }
  
          // 開始更新被除數的值以及max1 , 直接抵消的此時的被除數最高項可不做處理。但是保險一點還是處理一下為0。
          // 而且xishu2中可能存在着0，但是沒關系，乘0相減還是0。
          for (int j = 0; j <= max2; j++)
          {
              xishu1[j + dis] -= (xishu2[j] * xishu);
          }
          xishu1[max2 + dis] = 0;
          max1--;
      }
  
      cout << countDivNum << " ";
      int timeR = countDivNum;
  
      // **************************【就是這一步驟！！！】********************************
      // 就算被除數次數大于除數，也有可能出現商為0的情況，因為商的各項數值可能都小于0.05
      if (countDivNum == 0)
      {
          int y = 0;
          cout << y << " " << 0.0 << endl;
      }
      else
      {
          for (int i = maxE - max2; i >= 0; i--)
          {
              if (abs(outxishu1[i]) >= x)
              {
                  cout << i << " " << outxishu1[i];
                  timeR--;
                  if (timeR > 0)
                  {
                      cout << " ";
                  }
              }
          }
          cout << endl;
      }
  	
      // 被除數小于除數時，此時這代碼不執行
      // 餘數中能夠輸出的個數
      for (int j = max2 - 1; j >= 0; j--)
      {
          if (abs(xishu1[j]) >= x)
          {
              countRemainNum++;
          }
      }
      cout << countRemainNum << " ";
      
      int time = countRemainNum;
      if (countRemainNum == 0)
      {
          int y = 0;
          cout << y << " " << 0.0 << endl;
      }
      else
      {
          for (int j = max2 - 1; j >= 0; j--)
          {
              if (abs(xishu1[j]) >= x)
              {
                  cout << j << " " << xishu1[j];
                  time--;
                  if (time > 0)
                  {
                      cout << " ";
                  }
              }
          }
          cout << endl;
      }
      return 0;
  }
  
  /*
  測試資料
  0 0 0.0
  3 2 3 1 -2 0 1
  
  2 1 3 0 -1
  3 2 3 1 -2 0 1
  
  2 2 4 1 2
  2 1 2 0 1
  */