减治法介绍 减治法思想 ​ 分治法是将一个大问题划分为若干个子问题，分别求各个子问题，然后把子问题的解进行合并得到原问题的解。 ​ 减治法同样是把一个大问题划分为若干个子问题，但是并不是求解所有的子问题，因为原问题的解就在其中一个子问题当中，所以只求解其中一个子问题。 ​ 与分治法不同的就在于这个“减”字上，会不断的将原问题的规模减小，直到找到最终的解。 减治法求解过程： ​ 减治法将

分治法需要对分解的子问题分别求解，再对子问题进行合并，减治法只对一个子问题求解，并且不需要进行解的合并。减治法的效率更好。 *时间复杂性为log2n *思路：如果n=1,返回a的值；n是偶数且n>1，把该问题的规模减半，计算a^n/2的值；n是奇数且n>1，先利用偶指数的规则计算a^(n-1)，再把结果乘以a             a   n=1 a^n=    (a^n/2)^2

题目： 国王赏赐大臣30枚金币，但是有一枚是假的，并且假的金币较轻，国王让大臣仅用一个天平，比较最少的次数得到答案。也就是，在n枚外观相同的硬币中，有一枚是假币，并且已知假币较轻，可以通过一架天平来任意比较两组硬币，从而得知两组硬币的重量是否相同，或者哪一组更轻一些。 解法： 我们可以把假币一分为二，也就是把n枚硬币分为两组，每组有n/2个硬币，如果n为奇数，就留下一枚硬币，然后把两组硬