#include?
#define?HEAVY?1???????//用來表示A比B重
#define?LIGHT?-1??????//用來表示A比B輕
#define?BALANCE?0?????//用來表示AB一樣重
//??硬幣重量的數組|硬幣標準重量|儲存求到的硬幣位置|?times表示稱量次數
int?coins[2000]standerWeight=0locate=-1times=0;

int?GroupWeight（int?start?int?size）;
int?CompareGroups（int?weight_A?int?weight_B）;
int?Group_Know（int?start?int?size?int?compare）;
int?Two_Group（int?start_A?int?compare?int?start_B?int?size）;
int?DealThree（int?head?int?length?int?fadeCoin）;
int?Group_Unknow（int?start?int?size）;

//統計coins[start]到coins[start+size]的size個硬幣的重量??用以稱量
int?GroupWeight（int?start?int?size）
{
	int?weight=0;
	for（int?i=0;?i		weight+=coins[start+i];
	return?weight;
}

//稱量重量weight_A和wight_B?并返回稱量結果
int?CompareGroups（int?weight_A?int?weight_B）
{????
	times++;
	if（weight_A>weight_B）return?HEAVY;??//A比B重
	if（weight_A	return?BALANCE;?//AB一樣重
}

//當前硬幣只有一組?且??不知道假硬幣偏輕或偏重
//該組硬幣?以start為下標??有size個
int?Group_Unknow（int?start?int?size）
{
	int?r=0nhead=startlength=size;
	while（1）{
		n=（length+1）/3;//將硬幣分為A、B、C三組
		r=CompareGroups（GroupWeight（headn）?GroupWeight（head+nn））;
		if（r==0）{//A、B一樣重，繼續分?（問題規模減為1/3）
			head=head+2*n;
			length=length-2*n;
			if（length<=3）{
				return?DealThree（head?length?0）;
			}
		}
		else//A、B不一樣重，?調用函數該函數也能將問題規模縮小為1/3
			return?Two_Group（head?r?head+n?n）;
	}
}

//當前硬幣只有一組??且?知道假硬幣偏輕?或?偏重
//即已知一組硬幣???偏輕??或?偏重????（已知假硬幣偏輕或偏重）
//該組硬幣?以start為下標??有size個?與標準硬幣對比值compare
int?Group_Know（int?start?int?size?int?compare）
{
	if（size<=3）return?DealThree（start?size?compare）;
	int?n=（size+1）/3;???????????????????//減治法，分三組稱量，縮小規模，縮小為原來的1/3
	int?tempCompare=CompareGroups（GroupWeight（startn）GroupWeight（start+nn））;
	if（tempCompare==BALANCE）return?Group_Know（start+2*nsize-2*ncompare）;
	if（tempCompare==compare）return?Group_Know（startncompare）;
	else?return?Group_Know（start+n?ncompare）;
}

//當前硬幣有兩組，一組比另一組輕（或重），且確定有一組包含假硬幣，但不知道是哪一組
//即已知一組硬幣比另一組?輕??或?重???（不知道假硬幣偏輕還是偏重）
//以start_A開始和以start_B開始的??size個硬幣??稱量值為compare
int?Two_Group（int?start_A?int?compare?int?start_B?int?size）
{
	int?itempComparelayer=0groupOut;
	locate=start_A;
	if（size==1）{//兩組硬幣個數都為1
		tempCompare=CompareGroups（GroupWeight（start_B1）?standerWeight）;
		if（tempCompare==BALANCE）return?compare;
		locate=start_B;
		return?tempCompare;
	}
	for（i=1;?size>（i+i/2）;?i=i*3）;?//以下過程將組A分為A1A2B分為B1B2
	groupOut=i<（size-1）?i:size-1;??//使得A1數量約為A2兩倍B情況相同???將?A2+B1?與?B2+（B1個標準硬幣）	?稱量
	int?group_A=GroupWeight（start_A+groupOutsize-groupOut）+GroupWeight（start_BgroupOut）;??//?A2+B1?質量
????int?group_B=GroupWeight（start_B+groupOutsize-groupOut）+standerWeight*groupOut;?????????//B2+（B1個標準硬幣）	質量
	tempCompare=CompareGroups（group_A?group_B）;????????????????????????????????????????????//稱量
	if（tempCompare==compare）return?Two_Group（start_A+groupOut?compare?start_B+groupOut?size-groupOut）;?//稱量值與compare一樣，則假硬幣在A2B2?
	else?if（tempCompare==BALANCE）retur

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----

?????文件???????5178??2009-04-23?14:07??N_coins.cpp

?????文件????????511??2010-08-27?18:07??read.txt

?????文件?????108470??2009-04-23?14:08??QQ截圖未命名1.bmp

?????文件?????135774??2009-04-23?14:08??QQ截圖未命名2.bmp

?????文件?????154294??2009-04-23?14:09??QQ截圖未命名4.bmp

?????文件?????153654??2009-04-23?14:09??QQ截圖未命名5.bmp

?????文件?????107154??2009-04-23?14:07??QQ截圖未命名.bmp

?????文件?????114938??2009-04-23?14:08??3.bmp

-----------?---------??----------?-----??----

???????????????779973????????????????????8