试题详情
简答题分治法与减治法的思路有什么相同之处？又有什么不同？
  • 分治法和减治法的共同之处是，它们都是在“分而治之” 思想的指导下发展起来的， 基本思路就是把一个规模较大的问题划分为若干个规模较小的子问题，通过对子问题的求解，得到原问题的解。
    但分治法和减治法又各自适用于不同的情况，因此它们的求解过程有所不同。用分治法求解的问题，所划分的子问题是互相独立的，且原问题的解需要由各子问题的解合并而成。因此，需要对各子问题分别求解，并合并子问题的解，才能得到原问题的解。可以用减治法求解的问题，虽然也要对原问题进行划分，但因为原问题的或者解只在其中一个子问题中，或者是只与其中的一个子问题的解之间有着某种对应关系，因此只要对相关的一个子问题进行求解，就可以得到原问题的解。当然它也就不存在合并解的过程。可以说，减治法是一种退化了的分治法。

  • 关注下方微信公众号，在线模考后查看

热门试题