亚洲在线久爱草,狠狠天天香蕉网,天天搞日日干久草,伊人亚洲日本欧美

為了賬號安全,請及時綁定郵箱和手機立即綁定

分治算法

標簽:
Android
/**
 * 问题描述:一个袋子有一堆硬币其中一枚是假币,并且假币和真币一模一样,肉眼很难分辨,目前只知道假币比真币重量轻一点,请问如何区分出假币呢?
 */
static int FastCoin(int[] coin, int low , int high){
int num1,num2;//num1求出前半部分的总和,num2求出后半部分的总和
int re = 0;//记录最小值得位置
num1 = num2 = 0;
//*******************************下面的判断是递归的终止条件
if(low + 1 == high){//当索引low和high相邻,就是两者中的一个
if(coin[low] > coin[high]){
re = high + 1;//这里coin数组是从0开始所以要+1,下面同理
return re;
}else if(coin[low] < coin[high]){
re = low + 1;
return re;
}else{}//当相等的时候就说明此数组中的元素都一样
}
//*******************************coin数量为偶数
if((high - low + 1)%2 == 0){//coin的数量为偶数
for(int i = low; i<=low+(high - low)/2; i++){//前半部分
num1 = num1 + coin[i];
}
for(int i = low + (high - low)/2 + 1; i<=high ; i++){//后半部分
num2 = num2 + coin[i];
}
//进行判断
if(num1 > num2){//可知最小值在后半部分
re = FastCoin(coin, low+(high - low)/2+1,high);
return re;
}else if(num1 < num2){//可知最小值在前半部分
re = FastCoin(coin, low, low+(high - low)/2);
return re;
}else{}//如果相等则说明没有小值
//*******************************coin的数量为奇数
}else{//coin的数量为奇数
for(int i = low; i<=low+(high-low)/2-1; i++){//前半部分
num1 = num1 + coin[i];
}
for(int i = low+(high-low)/2+1; i<=high; i++){//后半部分
num2 = num2 + coin[i];
}
if(num1 > num2){//可知最小值在后半部分
re = FastCoin(coin, low+(high-low)/2+1, high);
return re;
}else if(num1 < num2){//可知在前半部分
re = FastCoin(coin, low, low+(high-low)/2-1);
return re;
}else{
re = low+(high-low)/2+1;
return re;
}
}
return re;
}
public static void main(String[] args) {
int[] coin = new int[]{3,3,3,3,3,2,3,3,3,3};
System.out.println(FastCoin(coin, 0, 9));
}

原文链接:http://www.apkbus.com/blog-523232-59351.html

點擊查看更多內容
1人點贊

若覺得本文不錯,就分享一下吧!

評論

作者其他優質文章

正在加載中
感謝您的支持,我會繼續努力的~
掃碼打賞,你說多少就多少
贊賞金額會直接到老師賬戶
支付方式
打開微信掃一掃,即可進行掃碼打賞哦
今天注冊有機會得

100積分直接送

付費專欄免費學

大額優惠券免費領

立即參與 放棄機會
微信客服

購課補貼
聯系客服咨詢優惠詳情

幫助反饋 APP下載

慕課網APP
您的移動學習伙伴

公眾號

掃描二維碼
關注慕課網微信公眾號

舉報

0/150
提交
取消