高级天平称小球问题——枯燥级

[笑言]

天平称小球问题

本文最早发表于vckbase 竞赛版(后该版面取消)，后藏于CSDN blog（偶早已不维护）。这个经典算法，丢弃了实为可惜，所以还是捡回来放于此处吧。

天平称小球问题

乾坤一笑[smileonce] 2004-7-11

天平称小球问题有很多经典的范式解法，在这里我们谈论着只是其中最为广泛应用的一种——三进制编码解法。
为什么想起了使用三进制？其实很好理解。让我们考虑一下小球的状态，有：没放在天平上、在天平左盘、在天平右盘三种。我们不妨用一些数码来表示这三种状态:
0——没放在天平上
1——放在天平左盘
2——放在天平右盘
这样，我们就可以用一个数码串来表示某个小球被称量的过程，比如某个小球的编码是210120，就表明这个小球，第一次称量在右盘，第二次在左盘，第三次不在天平上，第四次在左盘，第五次在右盘，第六次不在天平上。很简单吧，仅仅用一个数码串就把小球复杂的称量过程表示出来了。
为了方便说明，下面都以“12小球称3次”来描述这个问题，不过，你很容易就能够推广到“M个小球称N次的情形”。好，闲言少叙，书归正传。
假设我们已经把12个小球编上不重复的3进制编码，称量的时候我们完全按照编码操作，第0步，我们把12个小球上的编码第0位为1的放在天平左边，编码第0位为2的放在天平的右边，编码第0位为0的则不放在天平上，记下称量结果；第1步，我们把12个小球上的编码第1位为1的放在天平左边，编码第1位为2的放在天平的右边，编码第0位为1的不放在天平上，记下称量结果；如此下去，编码有N位，我们就称量N次，得到N组结果。
考察一下结果的状态：天平平衡、天平左边轻于右边、天平左边重于右边。咦？怎么也是3种。（hia hia，无巧不成书嘛，好戏还在后面）我们用0来表示天平平衡，用1来表示天平左边轻于右边，用2来表示天平左边重于右边；这样，称量了N次，我们就得到了一个N位的结果编码，它也是三进制编码。注意：这个编码有可能和某个小球的编码相同呢！：）
你似乎隐隐约约已经意识到了什么了吧。好，现在就把问题挑明：得到的结果编码，和非标准小球的编码一样，或者有直接的对应关系。（这个关系是什么？往下看）
如果我们确定了一组小球的称量方法（对应于12个小球的3进制编码），现在反过来考虑，原来某一步放天平左盘的小球现在放在天平右盘，原来放天平左盘的小球现在放在天平右盘，原来没放在天平上的小球应然不放在天平上。那么这样得到的小球编码（也是12个）和原来的重复吗？显然不重复，我们把由这种对应关系得到的编码叫做对偶码(这里下个定义：把编码中的每一位数码，1换成2，2换成1，0不变，得到新编码叫做原编码的对偶码。如22102的对偶码是11201，或者说22101和11201互为对偶码)。这时候，你会考虑这样一个问题了——3位的3进制编码有多少个？答案是有3^3=27个（记做3^N），比上面提到的24个编码还多3个。为什么要研究这个对称码？因为我们把A,B,C,D球放在左盘，把A’,B’,C’,D‘球放到右盘——与我们把A’,B’,C’,D‘球放在左盘，把A,B,C,D球放到右盘，其称量意义是一样的，得到结果是一样的，我们要避免这种重复操作。所以说，实现这种算法，很重要的一点是选码——在互为一对对偶码的编码中选择一个来给小球编号。
到这里，我想你一定猜出来了——27比上面的24个编码多出的3个是什么码？他们是000，111，222。000和自身为对偶码，111和222互为对偶码。为什么要去掉他们3个？我想还是不放在这里说明了，要解决这个问题你得看看后面的数学证明先！
于是，我们得出结论：如果正确选择了一组3进制码，分别用来给小球编号，那么严格按照小球编码的称量过程得到的结果代码，必然是非标准球的代码，或者是他的对偶码。（由于我们给小球的编码中，任意两个小球的编码不互为对偶码，所以，我们的称量操作唯一确定了非标准小球）此结论的证明方法过于繁复（我用word打了4页），所以放在文后供打包下载。
下面说说程序实现编码的具体过程。

参考上图，我们首先取得用一个code数组来存放编码，为了节省空间，在我的程序里code数组存放的是十进制编码，我用GetTheBall.num2Code()和GetTheBall.code2Num()来实现三进制和十进制之间的相互转换。我们首先把编码全部存入数组，然后去掉000,111,222这三个编码，然后再剩余的编码中再删掉一半，得到的12个编码标记给小球就行了。对于1开头的编码我们选择的是比111大的所有编码，对于2开头的编码，我们划去“1开头我们选的那部分编码”的对偶码，对于0开头的编码，我们选择的是从左向右的编码位中，第一个不为0的数码是1的编码（此处酷似好难理解，其实第一个不为0的数码不是1就是2，我们删掉了是2的那一半）。
好了，数数看，看好删了一半剩了一半。按照上图的编码方式，经过操作得到的结果码，如果在小球编码中，那个编码的小球就是非标准球，且比标准球轻。如果结果码不在小球编码中，那么结果码是非标准球的对偶码，非标准球比标准球重。

偶的代码如下（java source）:

////:BalanceWeightsBalls.java/** * 天平找非标准球问题 * * 题目： 12个小球中有一个的重量与其他的不等，要求用一个天平经过3次 * 秤量取出重量特殊的一个，请用代码模拟秤量的过程。 * * 解答： 称小球问题的正规通用解法也3、4种，不过我还是比较推崇3进制法， * 因为它有一种料敌在先的快感！ * * 说明： 本程序并不局限于12球称3次,本程序给出的是一种通用算法，你也可 * 以测试一下39个球称4次，120球称5次等等等等。：） * *author FreeDebug *//** * Balance类模拟了天平，并用private保护了用户指定的小球重量的数据， * 所以，本次仿真非常真实，童叟无欺！^_^ */class Balance { //-- 用小球的重量构造天平 public Balance(int ballMax, int abnormalBallNum, int abor) { ballWeight = new int[ballMax]; for (int i=0; i<ballMax; i++ ) ballWeight[i] = 10; if (abor == 1) ballWeight[abnormalBallNum] = 5; // lighter than normal else ballWeight[abnormalBallNum] = 15; // weighter than normal } //-- 称重量。左边的球重量之和小于右边的，返回1；否则返回2。 public static int weigh( int[] left, int[] right) { int leftWeight = 0, rightWeight = 0; for ( int i = 0; i < left.length; i++ ) leftWeight += ballWeight[left[i]]; for ( int i = 0; i < right.length; i++ ) rightWeight += ballWeight[right[i]]; return leftWeight == rightWeight ? 0 : ( leftWeight < rightWeight ? 1 : 2); } private static int[] ballWeight;}/** * 嘿嘿，全部核心操作都在这里，仔细看哟！ */class GetTheBall { public GetTheBall(int mBall, int mTime) { maxBall = mBall; maxTime = mTime; } public int[] code2Num( int code ) { int[] rs = new int[maxTime]; int iTmp = code; for (int i=0; i<maxTime; i++) { rs[maxTime-1-i] = iTmp % 3; iTmp /= 3; } return rs; } public int num2Code( int[] num ) { int rs = 0, o = 1; for (int i=0; i<maxTime; i++) { rs += num[maxTime-1-i]*o; o *= 3; } return rs; } public int getAllelomorph( int code ) { int rs; int[] num = new int[maxTime]; num = code2Num( code ); for (int i=0; i<maxTime; i++) if ( num[i] == 1 ) num[i] = 2; else if ( num[i] == 2 ) num[i] = 1; rs = num2Code( num ); return rs; } public static int powerOf3( int order ) { int rs = 1; for (int i=0; i<order; i++) { rs *= 3; } return rs; } public void coreWork () { int maxCode = maxBall*2+3; int[] code = new int[maxCode]; int[] ball = new int[maxBall]; int count = 0; int[] buf; //---- Codes .... for( int i=0; i<maxCode; i++) code[i] = i; //--- 00xxxx… count = powerOf3(maxTime-2); code[0] = -1; for( int i=0; i<count; i++) { buf = code2Num( code[i] ); for ( int j=0; j<buf.length; j++){ if (buf[j] == 2) code[i] = -1; if (buf[j] != 0) break; } } //--- 01xxxx… ==> good //--- 02xxxx… for( int i=count*2; i<count*3; i++ ) code[i] = -1; //--- 100000… ~ 111111… & del allelomorph in 2xxxxx… for( int i=count*3; i<count*3+(count*3-1)/2+1; i++) code[i] = -1; //--- 1xxxx…2 ~ 122222… ==> good //--- 2xxxx…0 ~ 22222…1 ==> del allelomorphi(i) for (int i=count*3+(count*3-1)/2+1; i<count*6; i++) for (int j=count*6; j<count*9; j++) if ( getAllelomorph(i) == j) code[j] = -1; //---- del 222222 ====> code[code.length-1] = -1; //--- Marks ball ... count = 0; for ( int i=0; i<maxCode; i++) if (code[i] != -1) { ball[count++] = code[i]; } //--- Weighs ball ... int[] left = new int[maxBall]; int[] right = new int[maxBall]; int[] weighResult = new int[maxTime]; for (int i=0; i<maxTime; i++){ int leftCount = 0, rightCount = 0; for (int j=0; j<maxBall; j++) { buf = code2Num( ball[j] ); if (buf[i] == 1) left[leftCount++] = j; if (buf[i] == 2) right[rightCount++] = j; } P.rintln("第 " + (i+1) +" 次称量:"); P.rint("放在做在天平左盘的小球编号 : "); for (int j=0; j<leftCount; j++ ) P.rint(" "+(left[j]+1)); P.rintln(" "); P.rint("放在做在天平左盘的小球编号 : "); for (int j=0; j<rightCount; j++ ) P.rint(" "+(right[j]+1)); P.rintln(" "); weighResult[i] = Balance.weigh( left, right ); if ( weighResult[i] == 0) P.rintln( " 称量结果：左盘和右盘一样重 "); else if (weighResult[i] == 1) P.rintln( " 称量结果：左盘轻于右盘 " ); else P.rintln(" 称量结果：左盘重于右盘 "); P.rintln(" "); } int wRs; boolean light = false; wRs = num2Code( weighResult ); for (int i =0; i<maxBall; i++) { if (code[ball[i]] == wRs) { P.rint(" 非标准球的编号是："+(i+1)); P.rintln( " 它比标准球轻！"); } else if (getAllelomorph(code[ball[i]]) == wRs ) { P.rint(" 非标准球的编号是："+(i+1) ); P.rintln(" 它比标准球重！"); } } } private int maxBall; //=12 private int maxTime; //=3}//---- predigest print function callclass P { public static void rint(String s) { System.out.print( s ); } public static void rintln(String s) { System.out.println( s ); }}public class BalanceWeightsBalls { public static void main(String[] args) { P.rintln("天平称小球问题"); P.rintln(" "); int maxBall = 12; //输入要称的小球数目 int maxTime = 3; //输入题目规定的称量的次数 int abormalBall = 9; //输入非标准球的编号，编号从1开始记，1<= abormalBall <= maxBall int abor = 2; //输入非标准球比标准球是轻还是重,1表示比标准球轻，2表示比标准球重 //根据上面用户的设定信息构造Balance类（天平） if (abormalBall<1 || abormalBall>maxBall) P.rint("输入错误，非标准球编号错误！"); if (!(abor==1 || abor==2)) P.rint("输入错误，非标准球轻重设置错误"); Balance bal = new Balance(maxBall, abormalBall-1, abor ); //由于Balance类用private修饰小球的信息，所以GetTheBall类 //并只知道那个小球是非标准球，以及它比标准球轻还是重。 //GetTheBall类只能通过Balance.weigh()方法来得到每一次的称量结果。 //这样做确保了仿真的公正性。 if ( !(( GetTheBall.powerOf3(maxTime) - 3 ) / 2 == maxBall) ) { P.rintln("题目有误，无法称量出非标准球，或者 "+maxTime
+" 并不是在 "+maxBall+" 个球中找出一个非标准球的最小的称量次数"); }else { GetTheBall gtb = new GetTheBall( maxBall, maxTime ); gtb.coreWork(); //好了，看看结果吧! } }}////:~
好了，讲到这里就告一段落了。其实，要想领会透彻这个算法的含义，为什么要这么编码，这么编码为什么正确，还必须经过严格的数学证明才行。
用三进制法解决天平称小球问题，我得道于我的师兄安兴华，本文所附的数学证明也非本人所作，可能是源于COI国家队的某个高手，我不清楚作者名姓，那篇文章也是个残本，可能有误，放在这里是为了给初学的朋友提供些资料。所以发现问题请不吝指点，知道原始出处和原著作者的请与我联系。
我的源码(java版)
相关的数学证明

-------------
乾坤一笑 写于2004年7月11日 转载请标明出处和原文链接

posted on 2005-08-21 13:35 乾坤一笑 阅读(3611) 评论(2) 编辑 收藏

 

[开喜]

果然很枯燥。。。 你真是一个诚实的人。