1.分冶算法思想是将一个计算复杂的问题分为规模较小，计算简单的问题，，然后综合各个小问题得到最终问题的答案。
2.分冶算法的执行过程
- 对于一个对魔为N的问题，若该问题可以容易的解决，则直接解决，否则执行下面的步骤。
- 将该分解为M个规模较小的子问题，子问题相互独立，并且与原问题形式相同。
- 递归的解这些问题，
- 然后，将各子问题的姐合并得到原问题的解。
3.分冶算法例子
java实现：
package com.sjx.test1;
import java.util.Scanner;
public class FenYeA {
static final int MAXNUM = 30;
//这个函数的功能是，将真假币数组从中间分开，比较前一半和后一半的重量，看看哪个重。
static int FalseCoin(int coin[], int low, int high)
{
int i, sum1, sum2, sum3;
int re = 0;
sum1 = sum2 = sum3 = 0;
if(low+1==high)
{
if(coin[low]<coin[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+coin[i];
for(i=low+(high-low)/2+1; i<=high; i++)
sum2 = sum2+coin[i];
if(sum1>sum2)
{
re = FalseCoin(coin, low+(high-low)/2+1, high);
return re;
}
else if(sum1<sum2)
{
re = FalseCoin(coin, low, low+(high-low)/2);
return re;
}
else
{
}
}
else
{
for(i=low; i<=low+(high-low)/2-1; i++)
sum1=sum1+coin[i];
for(i=low+(high-low)/2+1; i<=high; i++)
sum2 = sum2 +coin[i];
sum3 = coin[low+(high-low)/2];
if(sum1>sum2)
{
re = FalseCoin(coin, low+(high-low)/2+1, high);
return re;
}
else if(sum1<sum2)
{
re = FalseCoin(coin, low, low+(high-low)/2-1);
return re;
}
else
{
}
if(sum1+sum3==sum2+sum3)
{
re = low + (high-low)/2;
return re;
}
}
return re;
}
public static void main(String[] args)
{
int[] coin = new int[MAXNUM];
int i, n;
int weizhi;
System.out.println("分冶算法求解假银币问题！");
System.out.print("请输入假币的个数:");
Scanner input = new Scanner(System.in);
n = input.nextInt();
System.out.print("请输入银币的真假:"); //真币的重量都是相同且重量是比较重的，而假币是比较轻的
for(i=0; i<n; i++)
{
coin[i] = input.nextInt();
}
weizhi = FalseCoin(coin, 0, n-1);
System.out.println("在上述"+MAXNUM+"个银币中，第"+weizhi+"个银币是假的！");
input.close();
}
}