找假币

本文主要是介绍找假币，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一个国王要赏赐一个大臣30枚金币，但其中有一枚是假币。国王提出要求：只能用一个天平作为测量工具，并用尽量少的比较次数找出这枚假币，那么余下的29枚金币就赏赐给这个大臣；否则这个大臣将得不到赏赐。已知假币要比真币的分量略轻一些。

样例输入：

样例输出：

11

典型的分冶问题；

	static Scanner sc=new Scanner(System.in);static int a=sc.nextInt();static int[] i=new int[a];public static void main(String[] args){for(int b=0;b<a;b++){i[b]=sc.nextInt();}System.out.println(FalseCoin(i,0,a-1));}public static int FalseCoin(int[] coin,int low,int high){int sum1=0,sum2=0,sum3=0;if(low==high-1){//递归出口之一，当只剩两个银币时候的情况if(coin[low]>coin[high]){return high+1;}if(coin[low]<coin[high]){return low+1;}}if((high-low+1)%2==0){//如果n是偶数for(int i=low;i<=low+(high-low)/2;i++){//前半段和sum1=sum1+coin[i];}for(int i=low+(high-low)/2+1;i<=high;i++){//后半段和sum2=sum2+coin[i];}if(sum1>sum2){return FalseCoin(coin,(high-low)/2+1,high);}else{return FalseCoin(coin,low,low+(high-low)/2);}}else{//n为奇数for(int i=low;i<=low+(high-low)/2-1;i++){sum1=sum1+coin[i];}for(int i=low+(high-low)/2+1;i<=high;i++){sum2=sum2+coin[i];}sum3=coin[low+(high-low)/2];//中间数if(sum1>sum2){return FalseCoin(coin,low+(high-low)/2+1,high);}else if(sum1<sum2){return FalseCoin(coin,low,low+(high-low)/2-1);}if(sum1+sum3==sum2+sum3){//此时，sum1==sum2，再比较他们和sum3的关系return low+(high-low)/2+1;//另一个递归出口}}return 0;}

这篇关于找假币的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---