僞币識别問題

 僞币識别問題。一個袋子中裝有256枚金币，其中有一枚是僞币，且已知僞币比真的金币要輕。現在給你一架天平，如何快速找出那枚僞币？使用分治政策來對該問題進行求解，設計并實作相應的分治算法。

思路：采用二分法，将一個金币分為A、B兩部分，分别計算A、B部分的品質和，因為金币為偶數個且僞币比金币要輕，是以，其中一部分的品質和總比另一部分的品質和小，此時再将品質和小的部分進行二分，遞歸繼續下去。當隻剩下兩個金币時，記錄下品質較小的金币的位置進行輸出即可。（但是金币為奇數個時，此辦法行不通，因為并沒有具體告訴僞币比真币輕的具體數量，如果少一個機關品質，無法進行判斷）

package cn.aaa;

public class CSearch {

static int num=0;

public static void BinarySearch(int a[],int left,int right){

int sum1=0,sum2=0;

if(left+1<right){

int mid=(left+right)/2;

for (int i = 0; i < mid; i++) 

sum1 = sum1+a[i];

for (int i = mid; i < right; i++) 

sum2 = sum2+a[i];

if(sum1<sum2)

BinarySearch(a,left,mid);

else

BinarySearch(a,mid+1,right);

}

else if(left+1==right){

if(a[left]<a[right])

num = left;

if(a[left]>a[right])

num = right;

}

else 

num = -1;

}

public static void main(String[] args) {

int a[] = {1,1,1,1,1,1,-1,1};

BinarySearch(a,0,a.length-1);

System.out.println("僞币的位置為："+(num+1));

}

}