✅ PAT 甲级题目讲解1009《Product of Polynomials》摘要本文讲解 PAT 甲级 1009《Product of Polynomials》的完整解法。核心思路是使用数组作为指数映射表通过双层循环模拟两个稀疏多项式的逐项相乘与合并同类项时间复杂度O(k1×k2)O(k_1 \times k_2)O(k1​×k2​)。文中给出了从输入、计算到格式化输出的分步代码并整理了常见错误小数精度、空格控制、忘用累加等与思维拓展方向。 题目简介本题要求实现两个多项式的乘法。即给定两个稀疏多项式A(x)A(x)A(x)和B(x)B(x)B(x)求出它们的乘积多项式C(x)A(x)×B(x)C(x) A(x) \times B(x)C(x)A(x)×B(x)。最后输出非零项指数从大到小排列保留一位小数。 样例分析输入样例2 1 2.4 0 3.2 2 2 1.5 1 0.5两个多项式分别为A(x)2.4x13.2x0A(x) 2.4x^1 3.2x^0A(x)2.4x13.2x0B(x)1.5x20.5x1B(x) 1.5x^2 0.5x^1B(x)1.5x20.5x1手动展开乘积C(x)(2.4x13.2)×(1.5x20.5x1)2.4x1×1.5x22.4x1×0.5x13.2x0×1.5x23.2x0×0.5x13.6x31.2x24.8x21.6x1 \begin{aligned} C(x) (2.4x^1 3.2) \times (1.5x^2 0.5x^1) \\ 2.4x^1 \times 1.5x^2 2.4x^1 \times 0.5x^1 3.2x^0 \times 1.5x^2 3.2x^0 \times 0.5x^1 \\ 3.6x^3 1.2x^2 4.8x^2 1.6x^1 \end{aligned}C(x)​(2.4x13.2)×(1.5x20.5x1)2.4x1×1.5x22.4x1×0.5x13.2x0×1.5x23.2x0×0.5x13.6x31.2x24.8x21.6x1​合并同类项后C(x)3.6x36.0x21.6x1C(x) 3.6x^3 6.0x^2 1.6x^1C(x)3.6x36.0x21.6x1输出为3 3 3.6 2 6.0 1 1.6 解题思路本题的本质是稀疏多项式的乘法展开 合并同类项 格式控制输出。多项式乘法的核心是逐项相乘A(x)∑i1k1aixni,B(x)∑j1k2bjxmj A(x) \sum_{i1}^{k_1} a_i x^{n_i}, \quad B(x) \sum_{j1}^{k_2} b_j x^{m_j}A(x)i1∑k1​​ai​xni​,B(x)j1∑k2​​bj​xmj​则C(x)A(x)×B(x)∑i1k1∑j1k2aibjxnimj C(x) A(x) \times B(x) \sum_{i1}^{k_1} \sum_{j1}^{k_2} a_i b_j x^{n_i m_j}C(x)A(x)×B(x)i1∑k1​​j1∑k2​​ai​bj​xni​mj​ 变量说明表格变量名含义k1,k2多项式 A 和 B 的项数n[i],a[i]多项式 A 的第 i 项指数和系数m[i],b[i]多项式 B 的第 i 项指数和系数c[i]指数为 i 的项的系数乘积结果maxn当前记录的最大指数值s非零项的个数✅ Step 1输入两个稀疏多项式cink1;for(inti1;ik1;i){cinn[i]a[i];// A 的指数和系数}cink2;for(inti1;ik2;i){cinm[i]b[i];// B 的指数和系数}✅ Step 2逐项相乘累加结果模拟C(x)A(x)×B(x)C(x) A(x) \times B(x)C(x)A(x)×B(x)的计算过程数学公式为C(x)A(x)×B(x)∑i1k1∑j1k2aibjxnimj C(x) A(x) \times B(x) \sum_{i1}^{k_1} \sum_{j1}^{k_2} a_i b_j x^{n_i m_j}C(x)A(x)×B(x)i1∑k1​​j1∑k2​​ai​bj​xni​mj​代码实现使用双层循环逐项相乘累加结果for(inti1;ik1;i){// A 有 k1 项for(intj1;jk2;j){// B 有 k2 项inttn[i]m[j];// 新项指数c[t]a[i]*b[j];// 合并同类项maxnmax(maxn,t);// 更新最大指数}}✅ Step 3统计非零项数 按指数从大到小输出for(inti0;imaxn;i){if(c[i])s;// 非零项统计}printf(%d,s);for(intimaxn;i0;i--){if(c[i]){// 该项非 0printf( %d %.1lf,i,c[i]);// 注意先输出空格}}✅ 完整代码#includebits/stdc.husingnamespacestd;intk1,k2,n[15],m[15],maxn,s;doublea[15],b[15],c[2005];intmain(){cink1;for(inti1;ik1;i){cinn[i]a[i];}cink2;for(inti1;ik2;i){cinm[i]b[i];}for(inti1;ik1;i){for(intj1;jk2;j){inttn[i]m[j];c[t]a[i]*b[j];maxnmax(maxn,t);}}for(inti0;imaxn;i){if(c[i])s;}printf(%d,s);for(intimaxn;i0;i--){if(c[i]){printf( %d %.1lf,i,c[i]);}}return0;} 常见错误提醒错误类型错误描述小数精度不对忘记使用%.1lf输出浮点数忘记或多输出空格空格输出要严格控制忘记合并同类项没有用会导致覆盖而非累加✅ 总结归纳本题为稀疏多项式乘法模拟建议使用数组作为指数映射表c[i]空间换时间注意控制合并同类项按指数从大到小输出浮点数格式%.1lf严格空格输出。时间复杂度约为O(k1×k2)O(k_1 \times k_2)O(k1​×k2​)完全可接受。 思维拓展如果改成多项式求和只需将对应c[i]做加法更复杂情形可引入结构体表示项并排序这类题是数据结构课程中“稀疏数组”模型的重要应用。