一、概要设计
1、用数组来存储钱币1表示真币0表示比真币轻2表示比假币中。
2、用随机函数rand（）来随机生成假币的在数组中的位置以及假币的值
3、通过简单的比较找出一个真币，将值赋在数组的第一个里面，方便以后的比较。
4、程序用2分法和3分法两种来查找假币的位置，并判断假币的轻重。
5、变量index跟踪存储假币的位置。
//二分法求解
//
#include "Head.h"
#define LEFT_HEAVY 1
#define RIGHT_HEAVY 1
#define HEAVY 2
#define LIGHT 0
int which_heavy = 0 ;//那一边比较重，初始化为0 ，即未确定
int degree = 1 ;//假币轻重标志,初始化为1 ，即未确定
int Sum_Coin(const int A[] ,int from ,int to )
{
int sum = 0 ;
for(int i=from ;i<=to ;i++)
{
sum += A[i] ;
}
return sum ;
}
//
void Check_Degree(int A[] ,int& false_sign ,int from ,int to )
{//在确定真币A[0]的前提下，剩下2个硬币检测假币的所在位置和轻重
if(A[0]==A[from])
{
false_sign = to ;
if( degree==1)
{//判断假币的轻重
if( A[0]<A[to] )
degree = HEAVY ;
else
degree = LIGHT ;
}
}
else
{
false_sign = from ;
if( degree==1)
{//判断假币的轻重
if( A[0]<A[from] )
degree = HEAVY ;
else
degree = LIGHT ;
}
}
}
//
void Check_Coin_3(int A[] ,int& false_sign ,int from ,int to )
{/*假币问题求解：三分法*/
if( (tofrom+1) < 3)
{////确定真币的重量币种
if( from>1 )
A[0] = A[1] ;
else
A[0] = A[to+1] ;
Check_Degree(A ,false_sign ,from ,to ) ;
}
else
{
int i = (tofrom+1)/3 ;
int mid1 = from+i1 ;
int mid2 = mid1+i ;
//cout << "\n" << from << " " <<mid1 << " " <<mid2 <<endl ;
if( Sum_Coin(A ,from ,mid1)==Sum_Coin(A ,mid1+1 ,mid2) )
{
if( degree==1)
{//判断假币的轻重
if(which_heavy==LEFT_HEAVY)
degree = LIGHT ;
if(which_heavy==RIGHT_HEAVY)
degree = HEAVY ;
}
Check_Coin_3(A ,false_sign ,mid2+1 ,to) ;
}
else
{
if( degree==1)
{//判断假币的轻重
if( Sum_Coin(A ,from ,mid1) > Sum_Coin(A ,mid1+1 ,mid2) )
which_heavy = LEFT_HEAVY ;
else
which_heavy = RIGHT_HEAVY ;
}
Check_Coin_3(A ,false_sign ,from ,mid2) ;
}
}
}
//
void Check_Coin_2(int A[] ,int& false_sign ,int from ,int to )
{/*/*假币问题求解：二分法*/*/
if( (tofrom+1) < 4)
{
if( (tofrom+1) ==3)
{//3
if(A[from]==A[to])
{//from+1
false_sign = from+1 ;
if( A[0]<A[from+1] )
degree = HEAVY ;
else
degree = LIGHT ;
}
else
{//from ,to //确定真币的重量币种
A[0] = A[from+1] ;
Check_Degree(A ,false_sign ,from ,to ) ;
}
}
