算法设计与分析 课件 4.3-分治法 - 基本思想

算法设计与分析分治法-基本思想信息工程大学国家级实验教学示范中心计算机学科组规划教材算法设计与分析Python案例详解微课视频版寻找假币和金块问题的共同点把问题分解为规模更小的问题求解小规模问题得到原问题的解

算法策略：分而治之总体思想适用条件代码框架一二三T(n)将要求解的较大规模的问题分割成k个更小规模的子问题。对k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。T(n/m)T(n/m)T(n/m)T(n/m)………………………………边界和递归式T(n)将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。T(n/m)T(n/m)T(n/m)T(n/m)………………………………分治法的思想：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。分治就是“分而治之”，实质是将原问题分成n个规模较小而结构与原问题相似的子问题，然后递归地解这些子问题，最后合并其结果就得到原问题的解。子问题求解(conquer)问题S问题S1……问题S2问题Sn问题SiS1的解……S2的解Sn的解Si的解S的解问题的分解(divide)子问题解的合并(combine)选择题分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问题，分别解决子问题，最后将子问题的解组合起来形成原问题的解，要求原问题和子问题的问题规模

，问题性质

。A：相同，相同B：相同，不同C：不同，相同D：不同，不同测试分治法所能解决的问题一般具有以下几个特征：该问题的规模缩小到一定的程度就可以容易地解决；该问题可以分解为若干个规模较小的相同问题；利用该问题分解出的子问题的解可以合并为该问题的解；该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。divide-and-conquer(P){if(|P|<=n0)adhoc(P);//解决小规模的问题

//分解

dividePintosmallersubinstancesP1,P2,...,Pk；

//递归求解各子问题

for(i=1;i<=k;i++)yi=divide-and-conquer(Pi);

//将子问题的解合并为原问题的解

returnmerge(y1,...,yk);}分治法设计的平衡原则：使子问题的规模大致相同测试：博彩诈骗为什么可以成功背景设定你是一位足球迷，当前正在进行某个足球赛事，你在看球的同时想娱乐一下，参与一下博彩事业，当前正在进行16进8的比赛，你想买张彩票，正在你准备下注时，收到了一个信息。选择题：1信息中说：A队肯定会在这场比赛中获胜，此时你会相信吗？A：不信 B：信 C：半信半疑无论你信不信，你买了A队胜，此后，当A和C比赛时，你又收到了信息2信息中说：C队肯定会在这场比赛中获胜，此时你会相信吗？A：不信 B：信 C：半信半疑无论你信不信，你买了C队胜，此后，当C和E比赛时，你又收到了信息3信息中说：C队肯定会在这场比赛中获胜，此时你会相信吗？A：不信 B：信 C：半信半疑你买了C队胜，决赛时，你又收到了信息4要想知道比赛结果，需要付费查看，此时你会付