算法分析之假币问题源代码

//        假币算法求解（三分算法和二分算法）
//             xwlee 2006/12/20
//**********************************************
#include<iostream>
#include<cmath>
#include <ctime>
#include <iomanip>
using namespace std;

int find2(int coin[], int low, int high);//二分算法
int find3(int coin[], int low, int high);//三分算法

int  main(void)
{
    int i, *coin,n,temp;
  
    cout<<"请输入硬币的个数(n最大为机器整数值)：";
    cin>>n;
    srand( (unsigned)time( NULL ) );//srand()函数产生一个以当前时间开始的随机种子 
    cout<<"正在随机产生数据（用0和1分别代表假币和真币）...\n\n";
    coin=new int[n+1];//多产生一个位置，用coin[0]来记录本次调用称重的次数
    temp=1+rand()%n;//随机产生1~n之间的一个数
    coin[0]=0;//计数器
    for(i=1; i<n+1; ++i) 
        i!=temp ? coin[i]=1 : coin[i]=0;
            
    for(i=1; i<n+1; ++i)
        if(i!=temp)
            cout<<"第"<<setw(3)<<i<<" 枚硬币是真币(1)"<<endl;
        else

            cout<<"第"<<setw(3)<<i<<" 枚硬币是假币(0)"<<endl;
        
        cout<<endl<<endl<<"假币二分算法结果："<<endl;
        cout<<"假币在第"<<setw(3)<<find2(coin,1,n)<<"个位置!"<<endl;
        cout<<"总共称的次数为"<<setw(3)<<coin[0]<<"次!"<<endl;
       
        cout<<endl<<endl<<"假币三分算法结果："<<endl;
        cout<<"假币在第"<<setw(3)<<find3(coin,1,n)<<"个位置!"<<endl;
        cout<<"总共称的次数为"<<setw(3)<<coin[0]<<"次!"<<endl<<endl<<endl;
    
    return 0;
}

int find2(int coin[], int low, int high)
{ 
    int i,mid,sum1,sum2,sign;
    
    coin[0]=0;
    do //下界和上界所指示的初始位置
    {
             mid=(low+high)/2; 
             sign= (low+high)%2;//标记奇数和偶数
             //cout<<sign<<endl;
             sum1=sum2=0;

             if(sign==0)//处理奇数的情况
             {    
                 for(i=low; i<mid; i++)
                    sum1 += coin[i];
                  for(i=mid+1; i<=high; i++)