glr7nu.rar

glr7nu.rar

#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