假币判断伪代码

假币判断伪代码

初始化:List< int> C,表示硬币数组;

• flag = 0: 表示没有假币
• flag = 1: 表示假币重
• flag = -1:表示假币轻

返回:假币在硬币组中的位置(数组起始位置为:0)

1. flag = 0;

2. 判断 集合C 的大小是否大于3,是,继续下一步,否,返回错误;

3. 初始化查找区间 arrNow = [0,C.size()];

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

5.  将arrNow.size()模3,判断是否为0;
        =0:
        arrRemain[-1,-1];
        >0:
        1. 求出余数组:arrRemain=[arrNow.low,arrNow.low + arrNow.size() % 3];
        2. 设置当前查找区间的下界 arrNow.low += arrNow.size() % 3;
    将arrNow按硬币的数目平均划分为三组,每组大小为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){
                假币可能在余数组中,将余数组设置为下一次的运算区间: arrNow = arrRemain;
            }
        2.  if(arrA != arrB && arrA != arrC && arrB = arrC){
                假币在arrA中,设置arrA为下一次的运算区间: arrNow = arrA;
            }
        3.  if(arrB != arrA && arrB != arrC && arrA = arrC){
                假币在arrB中,设置arrB为下一次的运算区间: arrNow = arrB;
            }
        4.  if(arrC != arrB && arrC != arrA && arrA = arrB){
                假币在arrC中,设置arrC为下一次的运算区间: arrNow = arrC;
            }
   

   end while;//此时的arrNow的区间大小为0-2;

7.  if(arrNow.low == -1){
        1.从上次的分出的三组中不存在假币,而上次又没有分出余数组,所以没有假币;
        2.return 0;
    }else{
        1.从arrNow范围外随便找出一枚硬币 = rightOne (一定为真,因为此时假币在arrNow范围中);
        2.for(i = arrNow.low;arrNow < arrNow.size();i++){
            使用天平判断 i 与rightOne的重量,并用flag记录判断结果;
             if (0 != flag)
                retrun i+1;//返回从1开始的具体位置
          }
    return 0 ; //全部重量相等,不存在假币;