分治法

一种化繁为简的算法，一般用于计算步骤比较复杂的问题，通过将问题简化而逐步得到结果；

步骤：
1、对于一个规模为n的问题，如若该问题比较容易解决，则直接解决，否则，走下面步骤；
2、将该问题分解为m个规模较小的子问题，这些子问题相互独立，并且与原问题相同；
3、递归的解这些子问题；
4、将各子问题的解合并得到原问题的解；

实例：
8枚金币，其中一枚是假的，外表没什么差别，假币稍微轻一点，找出那个假币；

import java.util.Scanner;

/**
 * @ClassName TestDemo9
 * @Description 分治法
 * @Author lzq
 * @Date 2018/11/29 21:31
 * @Version 1.0
 **/
public class TestDemo9 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        System.out.println("输入金币数量：");
        int n = scan.nextInt();
        int[] array = new int[n];
        for(int i = 0;i < n;i++) {
            array[i] = scan.nextInt();
        }
        System.out.println("第"+divid_and_conquer(array,0,n-1)+"枚金币是假的！");
    }

    public static int divid_and_conquer(int[] array,int low,int high) {
        int i,sum1 = 0,sum2 = 0,sum3 = 0;
        int re = 0;
        if(low+1 == high) {
            if(array[low] < array[high]) {
                re = low+1;
                return re;
            }else {
                re = high+1;
                return re;
            }
        }
        if((high-low+1)%2 == 0) {
            for(i = low; i <= low+(high-low)/2;i++) {
                sum1 = sum1+array[i];
            }
            for(i = low+(high-low)/2+1;i <= high;i++) {
                sum2 = sum2+array[i];
            }
            if(sum1 > sum2) {
                re = divid_and_conquer(array,low+(high-low)/2+1,high);
                return re;
            }else if(sum1 < sum2) {
                re = divid_and_conquer(array,low,low+(high-low)/2);
                return re;
            }
        }else {
            for(i = low; i <= low+(high-low)/2-1;i++) {
                sum1 = sum1+array[i];
            }
            for(i = low+(high-low)/2+1;i <= high;i++) {
                sum2 = sum2+array[i];
            }
            sum3 = array[low+(high-low)/2];
            if(sum1 > sum2) {
                re = divid_and_conquer(array,low+(high-low)/2+1,high);
                return re;
            }else if(sum1 < sum2) {
                re = divid_and_conquer(array,low,low+(high-low)/2-1);
                return re;
            }

            if(sum1+sum3 == sum2+sum3) {
                re = low+(high-low)/2+1;
                return re;
            }
        }
        return re;
    }
}

输入金币数量：
8
2 2 2 2 2 1 2 2
第6枚金币是假的！