[C/算法]N硬币问题/称硬币

N枚硬币中，有一枚是假币，并且已知假币与真币重量不同，但不知道假币与真币相比较轻还是较重。可以通过一架天平来任意比较两组硬币，设计一个高效的算法来检测出这枚假币。

#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