假币判断伪代码
初始化:List< int> C,表示硬币数组;
- flag = 0: 表示没有假币
- flag = 1: 表示假币重
- flag = -1:表示假币轻
返回:假币在硬币组中的位置(数组起始位置为:0)
flag = 0;
判断 集合C 的大小是否大于3,是,继续下一步,否,返回错误;
初始化查找区间 arrNow = [0,C.size()];
while (arrNow.size() >= 3)
-
将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;
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 ; //全部重量相等,不存在假币;
