算法-->分治
package 分治算法;
import java.util.Scanner;
public class fenzhi {
static final int MAXNUM=4;
static int falsecoin(int coin[],int low,int hight) {
int i,num1,num2,num3;
int re=0;
num1=num2=num3=0;
if(low+1==hight) {
if(coin[low]
re=falsecoin(coin,low+(hight-low)/2,hight);
return re;
}else {
}
}else {//是奇数
for(i=low;i<=low+(hight-low)/2-1;i++) {
num1=num1+coin[i];
}
for(i=low+(hight-low)/2+1;i<=hight;i++) {
num2=num2+coin[i];
}
num3=coin[low+(hight-low)/2];
if(num1>num2) {
re=falsecoin(coin,low+(hight-low)/2+1,hight);
return re;
}else if(num1<num2) {
re=falsecoin(coin,low,low+(hight-low)/2);
return re;
}else {
}
if(num1+num3==num2+num3) {
re=low+(hight-low)/2+1;
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.println(“请输入硬币的总个数”);
Scanner sc=new Scanner(System.in);
n=sc.nextInt();
System.out.println(“请输入硬币的真假”);
for(i=0;i<n;i++) {
coin[i]=sc.nextInt();//输入硬币的真假
}
weizhi=falsecoin(coin,0,n-1);
System.out.println(“在上述”+MAXNUM+”个硬币中，第”+weizhi+”个硬币是假币”);
}
} 
妖狐艹你老母
港控/mmm°
还没有评论，来说两句吧...