C++實(shí)例:假幣問(wèn)題（C++解決方案）

一、概要設(shè)計(jì)
    1、用數(shù)組來(lái)存儲(chǔ)錢(qián)幣1表示真幣0表示比真幣輕2表示比假幣中。
    2、用隨機(jī)函數(shù)rand（）來(lái)隨機(jī)生成假幣的在數(shù)組中的位置以及假幣的值
    3、通過(guò)簡(jiǎn)單的比較找出一個(gè)真幣，將值賦在數(shù)組的第一個(gè)里面，方便以后的比較。
    4、程序用2分法和3分法兩種來(lái)查找假幣的位置，并判斷假幣的輕重。
    5、變量index跟蹤存儲(chǔ)假幣的位置。
    //二分法求解
    //
    #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 ;//假幣輕重標(biāo)志,初始化為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個(gè)硬幣檢測(cè)假幣的所在位置和輕重
    if(A[0]==A[from])
    {
    false_sign = to ;
    if( degree==1)
    {//判斷假幣的輕重
    if( A[0]　　degree = HEAVY ;
    else
    degree = LIGHT ;
    }
    }
    else
    {
    false_sign = from ;
    if( degree==1)
    {//判斷假幣的輕重
    if( A[0]　　degree = HEAVY ;
    else
    degree = LIGHT ;
    }
    }
    }
    //
    void Check_Coin_3(int A[] ,int& false_sign ,int from ,int to )
    {/*假幣問(wèn)題求解：三分法*/
    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 << " " <    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 )
    {/*/*假幣問(wèn)題求解：二分法*/*/
    if( (tofrom+1) < 4)
    {
    if( (tofrom+1) ==3)
    {//3
    if(A[from]==A[to])
    {//from+1
    false_sign = from+1 ;
    if( A[0]　　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 = (tofrom+1)/4 ;
    int mid1 = from+i1 ;
    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 請(qǐng)輸入貨幣總數(shù)： " ;
    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 ;
    if(false_coin==0)
    coin[false_position] = 0 ;
    else
    coin[false_position] = 2 ;
    Print_Coin(coin ,coin_num) ;
    int false_sign = 1 ; //假幣位置
    degree = 1 ;//輕重標(biāo)志,初始化為1 ，即未確定
    which_heavy = 0 ;//那一邊比較重，初始化為0 ，即未確定
    Check_Coin_2(coin ,false_sign ,1,coin_num ) ;
    cout << "\n 二分法求解 ,假幣位置：" << false_sign ;
    if( degree==LIGHT )
    cout << " 假幣較輕！\n" ;
    else
    cout << " 假幣較重！\n" ;
    /************************************************/
    false_sign = 1 ; //假幣位置
    degree = 1 ;//輕重標(biāo)志,初始化為1 ，即未確定
    which_heavy = 0 ;//那一邊比較重，初始化為0 ，即未確定
    Check_Coin_3(coin ,false_sign ,1,coin_num ) ;
    cout << "\n 三分法求解 ,假幣位置：" << false_sign ;
    if( degree==LIGHT )
    cout << " 假幣較輕！\n" ;
    else
    cout << " 假幣較重！\n" ;
    /************************************************/
    cout << "\n\n !!!按任意鍵繼續(xù)，Esc退出程序!!!" << endl ;
    }while( (c=getch())!=27 ) ;
    return ;
    }
    /***********************************************