GESP 五级 · GESP 五级样题（C++ 组）第 14 题

选择题 · 答案 B · 考点：分治算法

← 整套速查表 GESP 五级全部真题

题目

下列哪个算法并没有体现分治思想？

答案：B

考点

分治算法

解题思维

这题考分治思想与筛法的本质区别。拿到题先想‘分治三要素：划分、递归、合并’，再看算法流程是否包含‘把大问题拆成小问题解决后合并’。埃氏筛只是反复标记倍数，没有拆分与合并，直接排除。

常见错误

很多考生只记‘筛法效率高’或‘从i*i开始标记’，误以为这就是分治的‘优化技巧’。其实分治核心是‘问题规模递归缩小+子问题结果合并’，筛法全程是迭代标记，从未把原问题拆成子问题去求解再拼回去。还有个坑是看到‘二分’就下意识觉得是分治，但二分查找没有‘合并’步骤，不过它确实体现了‘划分’思想，而埃氏筛连划分都没有。

详细解析（节选）

【考点】分治思想辨析｜筛法原理｜算法流程控制

1. 分治的三要素（人话版）

分治不是随便‘分’一下，它必须同时满足三步：①划分——把大问题拆成若干小问题；②解决——递归或迭代地处理这些小问题；③合并——把小问题的答案拼起来得到原问题的解。经典案例：归并排序（二分→分别排序→合并）、快速排序（分区→递归→合并）。二分查找虽然只有‘划分’和‘解决’，没有显式合并，但教材里仍把它归为分治思想，因为它本质是不断把问题规模减半。

同考点真题

第 28 题· NOIP 2007 普及组初赛试题 · 答案 return(dr<tr+s)&&(dc<tc+s)dr<tr+s&&dc<tc+schessboard(tr,tc,tr+s-1,tc+s-1,s)chessboard(tr,tc+s,tr+s-1,tc+s,s)chessboard(tr+s,tc,tr+s,tc+s-1,s)chessboard(tr+s,tc+s,tr+s,tc+s,s)看解析 →
第 27 题· NOIP 2008 提高组初赛试题 · 答案 a[left];a[j]<valuea[j]<=valuea[i]>valuea[i]>=valuea[i] = value; i + 1,right,n FindKth(left, i – 1, n);看解析 →
第 26 题· NOIP 2009 普及组初赛试题 · 答案 NPOI看解析 →
第 28 题· NOIP 2011 提高组初赛试题 · 答案 num++num = num + 1j = isolve(left, j - 1, deep + 1)solve(j + 1, right, deep + 1)看解析 →
第 15 题· NOIP 2012 普及组初赛试题 · 答案 C看解析 →

在 OI伴学里做这道题

登录后可计时作答、查看完整六段式解析，并按你的错题自动生成同类练习。

去刷题先做一次 AI 学情诊断

GESP 五级 · GESP 五级样题（C++ 组） 第 14 题

题目

考点