#include
#include
#include
#include
int?Fake（int?A[]int?lint?rint?×）;
//輸出假幣
int?Weight（int?A[]int?lint?r）;
//累加l到r的和
int?HaveFakeCoin（int?A[]int?lint?rint?×）;
//判斷l到r有沒有假幣
int?JudgeTwo（int?A[]int?lint?rint?×）;
//就剩連個元素時找出假幣
int?JudgeThree（int?A[]int?lint?rint?×）;
//剩余三個元素
int?times=0;
bool?weight=false;//保存檢測出的假幣硬幣是還是重
int?length=0;
void?main（）
{
	int?times=0;
	int?A[500];
	int?n=0;
	int?pos=0;
	srand（（long）time（NULL））;
	do
	{
		printf（“請輸入金幣的個數:\n“）;
		scanf（“%d“&n）;
		length=n;
		for（int?i=0;i		{
			A[i]=0;
		}
		printf（“請輸入假幣的位置:\n“）;
		scanf（“%d“&pos）;
		int?rands=0;
		rands=rand（）%2;
		if（rands==0）
		{
			A[pos-1]=-1;
		}
		else
		{
			A[pos-1]=1;
		}
		for（i=0;i		{
			printf（“%d?“A[i]）;
		}
		printf（“\n“）;
		printf（“假幣的在第%d個位置\n“Fake（A0n-1times）+1）;//尋找假幣的位置
		if（weight）
		{
			printf（“比真幣重:\n“）;
		}
		else
		{
			printf（“比真幣輕:\n“）;
		}
		printf（“總共比較了%d次\n“times）;
		printf（“\n\n\n\n\n\n\n\t\t\t按任意鍵繼續\n“）;
		getch（）;
		times=0;
		system（“cls“）;
	}while（true）;
}
int?Fake（int?A[]int?lint?rint?×）
{
	int?mid=0;
	int?remainder=0;
	do
	{
		mid=（l+r）/2;
		remainder=（l+r）%2;
		if（remainder==1）//偶數s
		{
			int?result=0;
			if（r==（l+1））
			{
				return?JudgeTwo（Alrtimes）;
			}
			result=HaveFakeCoin（Almidtimes）;
			if（result==-1）//如果左邊有假幣
			{
				r=mid;
			}
			else
			{
				if（result==1）//如果假幣在右邊
				{
					l=mid+1;
				}
				else//已經有假幣的位置
				{
					if（A[result]					{
						weight=false;//輕
					}
					else
					{
						weight=true;//重
					}
					return?result;
				}
			}
		}
		else		//奇數
		{
		//	printf（“l=%dmid=%dr=%d\n“lmidr）;
			if（Weight（Almid-1）==Weight（Amid+1r））
				//如果左邊和右邊相同那么假幣就是中間這個
			{
				printf（“到了“）;
				printf（“times=%d“times）;
				times++;
				if（A[mid]>A[l]）
				{
					weight=true;
				}
				else
				{
					weight=false;
				}
				return?mid;
			}
			else
			{
				if（r==（mid+1））
				{
					return?JudgeThree（Alrtimes）;
				}
				int?result=HaveFakeCoin（Almid-1times）;
				if（result==-1）//左邊
				{
					r=mid-1;
				}
				else
				{
					if（result==1）//右邊
					{
						l=mid+1;
					}
					else
					{
						if（A[result]						{
							weight=false;//輕
						}
						else
						{
							weight=true;//重
						}
						return?result;//在這邊已找到假幣
					}
				}
			}
		}
	}while（true）;
	return?0;
}
int?Weight（int?A[]int?lint?r）
{
	int?sum=0;
	for（int?i=l;i<=r;i++）
	{
		sum+=A[i];
	}
	return?sum;
}
int?HaveFakeCoin（int?A[]int?lint?rint?×）
{
	int?mid=（l+r）/2;
	int?remainder=（l+r）%2;
	if（remainder%2==1）//如果為偶數個
	{		
		times++;
		if（Weight（Almid）==Weight（Amid+1r））//如果兩遍相同表示這邊沒有假幣幣，
			//也就是這邊都是真幣
		{
			return?1;
		}
		else
		{
			return?-1;
		}
	}
	else	//如果為奇數個
	{
		times++;
		if（Weight（Almi

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

?????文件???????4400??2008-11-11?21:44??假幣\fakeCoin.cpp

?????文件???????3429??2008-11-11?10:54??假幣\fakeCoin.dsp

?????文件????????524??2008-11-09?16:54??假幣\fakeCoin.dsw

?????目錄??????????0??2008-11-12?20:48??假幣

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

?????????????????8353????????????????????4