分治法

简介

分治法顾名思义，分而治之，分治法是符合人类思维的一种朴素算法，在面对大规模问题的时候，把问题进行拆解，分成规模较小的问题，然后逐个解决，最终实现对整个问题的求解。

流程

分治法的流程一般分为三个环节，分，治和合并。

• 分(Divide)：通用采用递归的方式将问题分解为较小的规模，直到子问题的规模达到可以解决的时候中止拆分。
• 治(Conquer)：递归求解。
• 合并(Combine)：合并子问题的解构建父类问题的解。

示例

假币问题

有n枚硬币，其中一枚假币比其他硬币相比，重量较轻，如何用一个天平找出这枚假币。

把假币按照数据等分为两份，放在天平两边，因为假币的数量较轻，所以假币位于天平较轻的一侧。这样，只需要在较轻的天平一侧继续这个过程即可。

直到最后剩下两枚硬币，就可以发现这个假币了。

代码（C++）

#include <iostream>
#include <cstdlib>

using namespace std;

const int MAXNUM = 30;

int falseCoin(int weight[], int lhs, int rhs)
{
    if (lhs == rhs)
        return lhs + 1;
    //如果只剩下两个银币，则较轻的那个便是假币
    else if (lhs == (rhs - 1))
    {
        return weight[lhs] < weight[rhs] ? lhs + 1 : rhs + 1;
    }

    int lsum = 0, rsum = 0;

    //如果偶数个银币，则比较两等份
    if ((rhs - lhs + 1) % 2 == 0)
    {
        for (int i = lhs; i < (lhs + (rhs - lhs + 1) / 2); i++)
        {
            lsum += weight[i];
        }

        for (int j = lhs + (rhs - lhs + 1) / 2; j <= rhs; j++)
        {
            rsum += weight[j];
        }

        //左右两份等重，则无假币
        if (lsum == rsum)
            return -1;
        else
            return (lsum < rsum) ? falseCoin(weight, lhs, lhs + (rhs - lhs) / 2) : falseCoin(weight, lhs + (rhs - lhs) / 2 + 1, rhs);
    }

    //如果奇数个银币，则比较除中间银币外的两等份
    else if ((rhs - lhs + 1) % 2 != 0)
    {
        for (int i = lhs; i < (lhs + (rhs - lhs) / 2); i++)
        {
            lsum += weight[i];
        }

        for (int j = (lhs + (rhs - lhs) / 2 + 1); j <= rhs; j++)
        {
            rsum += weight[j];
        }

        //左右两份等重，则无假币
        if (lsum == rsum && weight[lhs] == weight[lhs + (rhs - lhs) / 2])
            return -1;

        //如果两份等重，中间银币较轻，则中间银币为假币
        else if (lsum == rsum && weight[lhs] > weight[lhs + (rhs - lhs) / 2])
            return lhs + (rhs - lhs) / 2 + 1;

        //否则，返回较轻那份中的假币
        else
            return (lsum < rsum) ? falseCoin(weight, lhs, lhs + (rhs - lhs) / 2 - 1) : falseCoin(weight, lhs + (rhs - lhs) / 2 + 1, rhs);
    }
}

int main()
{
    int weight[MAXNUM];

    int n;
    while (cin >> n)
    {
        for (int i = 0; i < n; i++)
            cin >> weight[i];

        int falsePos = falseCoin(weight, 0, n - 1);

        if (falsePos != -1)
            cout << "第" << falsePos << "个银币为假币！" << endl;
        else
            cout << "无假币!" << endl;

    }//while

    system("pause");
    return 0;
}