CSP-S 提高级 · CSP 2021 提高级第一轮 第 19 题

三、完善程序（单选题，每小题 3 分，共计 30 分）

(1) （魔法数字） 小 H 的魔法数字是 $4$。给定 $n$， 他希望用若干个 $4$ 进行若干次加法、减法和整除运算得到 $n$。但由于小 H 计算能力有限，计算过程中只能出现不超过 $M = 10000$ 的正整数。求至少可能用到多少个 $4$。

例如，当 $n=2$ 时，有 $2=\dfrac{4 + 4}{4}$，用到了 $3$ 个 $4$，是最优方案。

试补全程序。  

34. ①处应填（ ） A. F[4] = 0 B. F[1] = 4 C. F[1] = 2 D. F[4] = 1

35. ②处应填（ ） A. !Vis[n] B. r < n C. F[M] == INT_MAX D. F[n] == INT_MAX

36. ③处应填（ ） A. F[i] == r B. !Vis[i] && F[i] == r C. F[i] < F[x] D. !Vis[i] && F[i] < F[x]

37. ④处应填（ ） A. F[i] < F[x] B. F[i]<=r C. Vis[i] D. i <= x

这题本质是求最少步数，用BFS逐层扩展。队列里存的是当前能达到的数值，每次挑F值最小且没访问过的数，做+4、-4、/4三种操作，只要结果在1到M之间就入队。

很多学生一看到求最少次数就想到DFS，结果陷入深搜；或者把F数组初始值搞错，以为F[4]=0；还有人忽略C++整数除法的向零特性，认为3/4=0合法，其实题目要求中间结果是正整数，所以x/4必须≥1即x≥4才合法。

考点与概念

这题考查BFS广度优先搜索在“最少操作步数”场景下的应用。BFS的核心是层序遍历：从起点开始，一层一层往外扩展，第一次遇到终点时，走的层数就是最短距离。本题里，起点是数值4，终点是n，每走一层代表多用了若干个4。我们用数组F[x]记录达到数值x最少需要多少个4，用Vis[x]标记x是否已经被访问过。

命题视角

命题人喜欢在“数字变换”类题目里挖坑：一是初始状态设错，二是运算规则理解偏差（特别是整除），三是忘记中间结果必须为正整数且不超过M=10000。本题把这三个坑都埋进去了，但通过BFS的“层序”特性，只要选对扩展顺序，就能避开这些陷阱。