2005-北京卷理-14 填-数列与算法设计

本题导读

本题考查秦九韶算法中乘法与加法次数的定性分析，以及等差数列通项在算法复杂度中的度量。

📌【题干】

Question

（2005年北京卷(理)） 14. 已知 $n$ 次多项式 $P_n(x)=a_0{x}^n+a_1{x}^{n-1}+\cdots +a_{n-1}x+a_n$. 如果在一项算法中，计算 $x_0^k$ ($k=2,3,4,\cdots ,n$) 的值需要 $k-1$ 次乘法，计算 $P_3(x_0)$ 的值共需要 9 次运算 (6 次乘法， 3 次加法)，那么计算 $P_{10}(x_0)$ 的值共需要$\underline{}$次运算. 下面给出一种减少运算次数的算法： $P_0(x)=a_0$, $P_{k+1}(x)=x{P}_k(x)+a_{k+1}$ ($k=0,1,2,\cdots ,n-1$). 利用该算法，计算 $P_3(x_0)$ 的值共需要 6 次运算，计算 $P_{10}(x_0)$ 的值共需要$\underline{}$次运算.

🔍【思路分析】

破题导航

1. 分析第一空（传统朴素算法）：

• 加法次数：一个 $n$ 次多项式总共有 $n+1$ 项，两两相加需要 $n$ 次加法。因此 $P_{10}(x_0)$ 确定需要 10 次加法。
• 乘法次数：计算 $a_k{x}_0^{n-k}$ 时，需要先算 $x_0^{n-k}$（由题意需 $n-k-1$ 次乘法），再乘以系数 $a_k$（需 1 次乘法）。求和列出关于 $n$ 的等差数列，利用求和公式算出 $n=10$ 时的总乘法次数。

2. 分析第二空（秦九韶算法）：

• 观察递推式 $P_{k+1}(x)=x{P}_k(x)+a_{k+1}$，每向后递推一次（即多项式次数增加 1 次），提取出公因式后，都只需要进行 1 次乘法和 1 次加法，总计 2 次运算。
• 计算 $n$ 次多项式一共需要进行 $n$ 次这样的递推步。因此总运算次数可以直接建模为 $2n$。

✅【答案】

Success

$65，20$

✍【详细解析】

Abstract

解：

(1) 第一空：计算第一种传统算法下的 $P_{10}(x_0)$ 运算总数

对于 $n$ 次多项式 $P_n(x_0)=a_0{x}_0^n+a_1{x}_0^{n-1}+\cdots +a_{n-1}{x}_0+a_n$：

• 加法次数分析： 多项式共有 $n+1$ 个项，将这 $n+1$ 个单项式相加，一共需要 $n$ 次加法。 当 $n=10$ 时，加法次数为 10 次。

• 乘法次数分析： 根据题意，计算 $x_0^k$ 的值需要 $k-1$ 次乘法，则计算带有系数的单项式 $a_{n-k}{x}_0^k$ 需要 $(k-1)+1=k$ 次乘法（其中 1 次为乘以系数 $a_{n-k}$）。 各单项式的乘法消耗情况具体为：

• $a_n$ 项：0 次乘法；

• $a_{n-1}{x}_0^1$ 项：1 次乘法（即乘以系数 $a_{n-1}$）；

• $a_{n-2}{x}_0^2$ 项：2 次乘法；

• $\cdots$

• $a_0{x}_0^n$ 项： $n$ 次乘法。

所以，计算整个 $n$ 次多项式所需的总乘法次数为等差数列求和： $M_n=1+2+3+\cdots +n=\frac{n(n+1)}{2}$

当 $n=10$ 时，乘法次数为： $M_{10}=\frac{10\times 11}{2}=55\text{ 次}$

• 总运算次数： $\text{总次数}=\text{加法次数}+\text{乘法次数}=10+55=65\text{ 次}$

(2) 第二空：计算新改进算法（秦九韶算法）下的 $P_{10}(x_0)$ 运算总数

新算法的递推关系式为： $P_0(x)=a_0,P_{k+1}(x)=x{P}_k(x)+a_{k+1}(k=0,1,2,\cdots ,n-1)$

• 单步递推开销分析： 从 $P_k(x)$ 计算到 $P_{k+1}(x)$，解析式右侧只有两步运算：

1. $x\cdot P_k(x)$ （1 次乘法）

2. $\cdots +a_{k+1}$ （1 次加法） 也就是说，每增加 1 次次数，固定增加 1 次乘法和 1 次加法，即共需要 2 次运算。

• 总运算次数分析： 要计算出 $n$ 次多项式 $P_n(x_0)$ 的值，需要从 $k=0$ 一直递推到 $k=n-1$，总共执行了 $n$ 步这样的操作。 所以计算 $n$ 次多项式所需的总运算次数为： $W_n=2\times n=2n\text{ 次}$

题干中“计算 $P_3(x_0)$ 的值共需要 6 次运算”符合 $2\times 3=6$ 的规律。 当 $n=10$ 时，计算 $P_{10}(x_0)$ 的值所需的总运算次数为： $W_{10}=2\times 10=20\text{ 次}$

💡【考点归纳与避坑指南】

Danger

核心考点：秦九韶算法中乘法与加法次数的定性分析、等差数列通项在算法复杂度中的度量。 核心方法：递推步开销分析法、分组求和法。

避坑指南：

• 切勿在第一空中漏掉“乘以系数 $a_i$”的那一次乘法。部分同学容易直接将乘法次数算成 $1+2+\cdots +(n-1)$，从而导致总数偏小。牢记：不仅幂次自乘需要消耗乘法，系数与幂次变量之间相乘同样属于必不可少的乘法运算。

📖【试题探源与推广】

Tip

变式练习：改变递推式的首项或系数，用待定系数法构造等比数列，或改用裂项、错位相减求和。

🔗【关联脉络】

Multi column

知识锚点 (Nodes)

• 19.01 等差数列全总结
• 25.01 程序框图与基本逻辑结构

类题演练 (Links)