使用分治算法必须满足的条件是 有哪些算法是利用分治策略实现的

分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。递归地解这些子问题，然后将各个子问题的解合并得到原问题的解。它的一般的算法设计模式如下：divide-and-conquer(P){if(|P|)adhoc(P)；divide P into smaller subinstances P1，P2，.，Pk；for(i=1；i；i+)yi=divide-and-conquer(Pi)；return merge(y1，.，yk)；}其中，P|表示问题P的规模。n0为一阀值，表示当问题P的规模不超过n0时，问题已容易解出，不必再继续分解。adhoc(P)是该分治法中的基本子算法，用于直接解小规模的问题P。当P的规模不超过n0时，直接算法adhoc(P)求解。算法merge(y1，y2，.，yk)是该分治法中的合并子算法，用于将P的子问题P1，P2，.，Pk的解y1，y2，.，yk合并为P的解。根据分治法的分割原则，应把原问题分为多少个子问题才比较适宜？每个子问题是否规模相同或怎样才为适当？这些问题很难给予肯定的回答。但人们从大量实践中发现，在用分治法设计算法时，最好使子问题的规模大致相同。即将一个问题分成大小相等的k个子问题的处理方法是行之有效的。许多问题可以取k=2。这种使子问题规模大致相等的做法是出自一种平衡(banlancing)子问题的思想，它几乎。分治法的适用条件？ 分治法所能解决的问题一般具有以下几个特征：1)该问题的规模缩小到一定的程度就可以容易地解决2)该问题可以分解为若干个规模较小的相同问题，即该zhidao问题具有最优子结构性质。3)利用该问题分解出的子问题的解可以合并为该问题的解；4)该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。上述的第一条特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加而增加；第二条特征是应用分治法的前提它也是大多数问题可以满足的，此特回征反映了递归思想的应用；第三条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑用贪心法或动态规划法。第四条特征涉及到分治法的效率，如果各子问题是不独立的则分治法要做许多不必要的工作，重复地解公共的子问题，答此时虽然可用分治法，但一般用动态规划法较好。分治法的算法说明？ 1、分治法的基本思想 任何一个可以用计算机求解的问题所需的计算时间都与其规模N有关。问题的规模越小，越容易直接求解，解题所需的计算时间也越少。例如，对于n个元素的。利用分治算法求解、 对于这种已知不合格硬币比正常银币偏重（或偏轻）的问题，可以用分治法。以下算法可以用数学归纳法证明：假设有3枚硬币，则称一次，如果a边重则是a，…，平衡则是c。同理如果有N块硬币，我们可以把它分成三堆，称一次后，这样问题规模缩小至n/3。重复以上操作，直至称出。需要次数为log3 n。这是典型的分治法，如果想了解更多，可参考《算法导论》谢谢采纳我的答案利用分治算法求解、 这不是智力题么。每次对半分放在天平两端。1.奇数的话：多出一个，天平两端平衡说明多出的那个不合格，否则不合格的在较重的那堆里。2.偶数的话，天平肯定不平衡，不合格的在较重的那堆里。把教重的那堆继续对半分重复以上的做法，直到找到不合格的硬币。这算是分治，也算二分吧。

#分治算法