package com.xj.www.algo;
import java.util.Scanner;
/**
* 分治算法
*
* @author xiongjing
*
*/
public class DivideTest {
static int FalseCoin(int coin[], int low, int high) {
int i, sum1, sum2, sum3;
int re = 0;
sum1 = sum2 = sum3 = 0;
// 算法具体实现
// 判断high == 1的情况
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 += coin[i];
}
for (i = low + (high - low) / 2 + 1; i <= high; i++) {
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 += coin[i];
}
for (i = low + (high - low) / 2 + 1; i <= high; i++) {
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);
} else {
}
if (sum1 + sum3 == sum2 + sum3) {
re = low + (high - low) / 2 + 1;
return re;
}
}
return re;
}
// 方法主入口
public static void main(String[] args) {
int i, n;
int weizhi;
System.out.println("分治算法求解假币问题!");
System.out.print("请输入硬币总的个数:");
@SuppressWarnings("resource")
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
System.out.print("请输入硬币的真假:");
int[] coin = new int[n];
for (i = 0; i < n; i++) {
coin[i] = sc.nextInt();
}
weizhi = FalseCoin(coin, 0, n - 1);
System.out.println("在上述" + n + "个硬币中,第" + weizhi + "个硬币是假的!");
}
}
网友评论