砝码已知有 20 个质量算法思想

上海众渊砝码厂———

砝码已知有 20 个质量算法思想

已知有 20 个质量分别为 1 , 3, 9, 27， . . . 3^1 9 的砝码; 开始物体放在天平左
边的托盘中， 通过在左盘和右盘添加砝码使天平达到平衡。要求左边不放砝码时，
输出 empty, 否则输入两盘所加的砝码。 例如： 左盘放入质量为 5 的物体， 则在
左盘放入质量分别为 1 和 3 的砝码， 右盘放入质量为 9 的砝码， 则有 5+1 +3=9，
即左边等于右边， 天平达到平衡 。
输入样例：
9
5
20
40
输输出样例：
empty 9
1 , 3 9
1 , 9 3, 27
empty 1 , 3, 9, 27

算法思想：

 1. 先将放入的物体转换成三进制， 存入数组 a 中； 2. 扫描数组 a， 查
找是否有2 的出现， 因为三进制数只出现 0, 1, 2, ； 如果不出现 2 则直接输出 3^i(i
为数组下标（if(a[i] !=0) ） cout<<pow(3, i) ; ) ， 因为每个质量的砝码只有一个，
所以不能出现 2， 下面消灭 2； 3、 如果数组 a 中出现 2， 分两种情况， （1） 、
如果 2 的前面出现 0， 则把数组 a 中 2 到 0 之间的数（包含 2， 不包含 0） 赋予
0， 并将 0 换成 1； （2） 、 如果扫描完整个数组 2 前面都没有出现 0， 则则把 2
到**位的 1 赋 0， 再将数组增加一位， 增加的一位赋值 1， 执行此 处跳出循环；
反复扫描；
4、 第 3 步得到的数组按照**步的方法输出即可； **于左盘中所加的砝码有两
种方法计算， 不出现 2 的情形在此不再赘述。 **种方法（容易想到， 个人感
觉算法复杂度有点大。 ） ： 将数组 a 转换成 10 进制， 直接与原来的数作差， 再
转换成三进制（存入数组 b） 输出即可； 第二种方法： 就是在第二步赋 0 的同时，
初始化数组 b[i] (将 b 中的各位数赋 0) ， 将 b[i] =1(a 中不是**个 2（相对扫
描到的 2 而言） 且为 2 的不进行此操作) 。 要的就是数组 b;
通过以上方法得到的数组 a 与 b 中的 1 在数组中的位置是错开的， 不会出现相同的位置都
出现 1 , 且数组 a 和 b 中都不出现 2. ； 而且你会惊奇的发现 b+物体质量=a;
算法举例： 比如在左盘加入质量为 1409 的物体， 转换成三进制为： 1221012； 这例子包含
各种**情形， 我想应该**代表性吧。 为了方便我只写每一步计算结果：
a. 1221100, b. 11->a. 10001100, b. 1010011.
**终 a 为： 10001100； b 为： 1010011， 而 1221012+1010011（b） =10001100(a) ;巧吧。 。 。
上海众渊砝码厂————

砝码 http://www.jjtianping.com/

砝码 http://www.11fama.com/