算法-->分治

一时失言乱红尘 2022-06-12 02:06 177阅读 0赞

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\]<coin\[hight\]) \{  
  re=low+1;  
  return re;  
 \}else \{  
  re=hight+1;  
  return re;  
 \}  
 \}  
  //如果是偶数  
 if((hight-low+1)%2==0) \{  
 for(i=low;i<=low+(hight-low)/2;i++) \{  
  num1=num1+coin\[i\];//前面一半的和  
 \}  
 for(i=low+(hight-low)/2+1;i<=hight;i++) \{  
  num2=num2+coin\[i\];//后面一半的和  
 \}  
 if(num1<num2) \{  
  re=falsecoin(coin,low,low+(hight-low)/2);  
  return re;  
 \}else if(num1>num2)\{  
  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+"个硬币是假币");  
  \}  
\} ![Center][]

[Center]: /images/20220612/31844a8454c846a4849276a59cb89a64.png