Question

某计算器只有两个键 [ $+1$ ] 和 [ $\times 2$ ]。按下其中一个键时，计算器会自动显示结果。例如，如果计算器原来显示“ $9$ ”，按 [ $+1$ ] 后会显示“ $10$ ”。如果接着按 [ $\times 2$ ]，会显示“ $20$ ”。从显示“ $1$ ”开始，要达到“ $200$ ”最少需要按多少次键？

A certain calculator has only two keys [ $+1$ ] and [ $\times 2$ ]. When you press one of the keys, the calculator automatically displays the result. For instance, if the calculator originally displayed " $9$ " and you pressed [ $+1$ ], it would display " $10.$ " If you then pressed [ $\times 2$ ], it would display " $20.$ " Starting with the display " $1,$ " what is the fewest number of keystrokes you would need to reach " $200$ "?

$8$

$9$

$10$

$11$

$12$

答案：B

知识点：逆推法最优化

难度评级：1610

解答：

从 $200$ 反向操作。数为偶数时，用除以 $2$ 撤销 $\times2$ ；数为奇数时，用减去 $1$ 撤销 $+1$ 。

使用 $9$ 个反向步骤，所以 $9$ 次按键足够。 $200,100,50,25,24,12,6,3,2,1$

对于目标 $200$ ， $8$ 次按键不够：小于目标的最大可达值由先 $\times2,+1$ ，再六次加倍得到，即 $3\cdot2^6=192$ 。更大的可能会至少达到 $256$ ，所以 $200$ 不能在 $8$ 次按键内到达。

所以正确答案是 B。

Work backward from $200$ . When the number is even, undo $\times2$ by dividing by $2$ ; when it is odd, undo $+1$ by subtracting $1$ .

$200,100,50,25,24,12,6,3,2,1$ uses $9$ reverse steps, so $9$ keystrokes are enough.

Eight keystrokes are not enough: the largest value below $200$ reachable in $8$ keystrokes is obtained by $\times2,+1$ followed by six doublings, giving $3\cdot2^6=192$ . The next larger possibilities overshoot to at least $256$ , so $200$ cannot be reached in $8$ keystrokes.

Thus, B is the correct answer.

2005 AMC 8 第 24 题

答案：B

难度评级：1610

解答：

其他年份的第 24 题