|
//二分法求解、、、、
//
#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( (to-from+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 = (to-from+1)/3 ;
int mid1 = from+i-1 ;
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( (to-from+1) < 4)
{
if( (to-from+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 ) ;
}
}
else
{//2//确定真币的重量--币种
if( from>1 )
A[0] = A[1] ;
else
A[0] = A[to+1] ;
Check_Degree(A ,false_sign ,from ,to ) ;
}
}
else
{
int i = (to-from+1)/4 ;
int mid1 = from+i-1 ;
int mid2 = mid1+i ;
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(which_heavy==LEFT_HEAVY)
degree = HEAVY ;
else
{
if(which_heavy==RIGHT_HEAVY)
degree = LIGHT ;
else
{
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 Print_Coin(const int coin[] ,int coin_num)
{
for(int i=1 ;i<=coin_num ;++i)
cout << coin[i] << " " ;
}
void main()
{
int* coin ;
int coin_num ;
int false_coin ; //1 ，假币较重； 0 ，假币较轻
time_t t;
srand((unsigned) time(&t));
char c ;
do
{
system("cls") ;
cout << "\n\n 请输入货币总数： " ;
cin >> coin_num ;
coin = new int[coin_num+1] ;
for(int i=1 ;i<=coin_num ;++i)
{
coin[i] = 1 ;
}
false_coin = rand()%2 ;
int false_position = (rand()%coin_num)+1 ;
|
