假幣判斷偽代碼

初始化:List< int> C,表示硬幣數(shù)組;

• flag = 0: 表示沒有假幣
• flag = 1: 表示假幣重
• flag = -1:表示假幣輕

返回:假幣在硬幣組中的位置(數(shù)組起始位置為:0)

1. flag = 0;

2. 判斷 集合C 的大小是否大于3,是,繼續(xù)下一步,否,返回錯(cuò)誤;

3. 初始化查找區(qū)間 arrNow = [0,C.size()];

4. while (arrNow.size() >= 3)

5.  將arrNow.size()模3,判斷是否為0;
        =0:
        arrRemain[-1,-1];
        >0:
        1. 求出余數(shù)組:arrRemain=[arrNow.low,arrNow.low + arrNow.size() % 3];
        2. 設(shè)置當(dāng)前查找區(qū)間的下界 arrNow.low += arrNow.size() % 3;
    將arrNow按硬幣的數(shù)目平均劃分為三組,每組大小為groupSize = arrNow.siez() / 3;
        1. arrA = [arrNow.low,arrNow.low + groupSize];
        2. arrB = [arrA.size(),arrA.size() + groupSize];
        3. arrC = [arrB.size(),arrB.size() + groupSize];
    用天平比較arrA,arrB,arrC的重量,判斷它們的重量是否相同;
        1.  if(arrA = arrB = arrC){
                假幣可能在余數(shù)組中,將余數(shù)組設(shè)置為下一次的運(yùn)算區(qū)間: arrNow = arrRemain;
            }
        2.  if(arrA != arrB && arrA != arrC && arrB = arrC){
                假幣在arrA中,設(shè)置arrA為下一次的運(yùn)算區(qū)間: arrNow = arrA;
            }
        3.  if(arrB != arrA && arrB != arrC && arrA = arrC){
                假幣在arrB中,設(shè)置arrB為下一次的運(yùn)算區(qū)間: arrNow = arrB;
            }
        4.  if(arrC != arrB && arrC != arrA && arrA = arrB){
                假幣在arrC中,設(shè)置arrC為下一次的運(yùn)算區(qū)間: arrNow = arrC;
            }
   

   end while;//此時(shí)的arrNow的區(qū)間大小為0-2;

7.  if(arrNow.low == -1){
        1.從上次的分出的三組中不存在假幣,而上次又沒有分出余數(shù)組,所以沒有假幣;
        2.return 0;
    }else{
        1.從arrNow范圍外隨便找出一枚硬幣 = rightOne (一定為真,因?yàn)榇藭r(shí)假幣在arrNow范圍中);
        2.for(i = arrNow.low;arrNow < arrNow.size();i++){
            使用天平判斷 i 與rightOne的重量,并用flag記錄判斷結(jié)果;
             if (0 != flag)
                retrun i+1;//返回從1開始的具體位置
          }
    return 0 ; //全部重量相等,不存在假幣;