2005-北京卷文-14 填-多项式求值运算次数

本题导读

本题考查多项式求值的算法与运算次数的计数。

📌【题干】

Question

（2005年北京卷(文)） 已知 $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. 直接法：先算 $x_0^2,\cdots ,x_0^{10}$ 共 $1+2+\cdots +9=45$ 次乘法。
2. 再算 $a_0{x}_0^{10},\cdots ,a_9{x}_0$ 共 $10$ 次乘法，与 $a_{10}$ 相加共 $10$ 次加法，合计 $45+10+10=65$。
3. 递推法：每步 $1$ 乘 $1$ 加，从 $P_0$ 到 $P_{10}$ 共 $10$ 步，合计 $10+10=20$。

✅【答案】

Success

$65，20$

✍【详细解析】

Abstract

按第一种算法，先计算 $x_0^2,\cdots ,x_0^{10}$，所需乘法次数为 $1+2+\cdots +9=45$．随后计算 $a_0{x}_0^{10},a_1{x}_0^9,\cdots ,a_9{x}_0$，还需 $10$ 次乘法；把这 $10$ 项与 $a_{10}$ 相加，需 $10$ 次加法．因此总运算次数为 $45+10+10=65$． 按递推算法，从 $P_0(x_0)$ 逐步得到 $P_1(x_0),\cdots ,P_{10}(x_0)$，每一步 $P_{k+1}(x_0)=x_0{P}_k(x_0)+a_{k+1}$ 都需 $1$ 次乘法和 $1$ 次加法，共有 $10$ 步，所以总运算次数为 $10+10=20$．

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

Danger

核心考点：多项式求值运算次数

核心方法：按乘加次数逐层累加，递推算法逐步计数

避坑指南：直接法 $45+10+10=65$ 次，秦九韶递推法每步 $1$ 乘 $1$ 加共 $20$ 次；两种算法口径不同别混算

📖【试题探源与推广】

Tip

试题探源：多项式求值的秦九韶算法（人教 A 版必修三，新课标已删）

结论推广：秦九韶算法把 $n$ 次多项式求值从约 $\frac{n(n+1)}{2}+n$ 次乘法降到 $n$ 次乘法 $n$ 次加法

方法推广：递推化是减少运算次数的通用思想（Horner 法则）

🔗【关联脉络】

Multi column

知识锚点 (Nodes)

• 22.01 计数原理、排列与组合
• 25.01 程序框图与基本逻辑结构

类题演练 (Links)

• 2013-大纲卷文-14 填-分组计数
• 2005-全国卷III理-14 填-平面向量的坐标减法运算