当前位置:首页 > 开发 > 编程语言 > 编程 > 正文

据说是2012年10月人人网校招的一道笔试题-给出一个重物重量为X,另外提供的小砝码重量分别为1,3,9。。。3^N。 将重物放到天平左侧,问在两边如何添加砝码

发表于: 2012-10-28   作者:bylijinnan   来源:转载   浏览:
摘要: public class ScalesBalance { /** * 题目: * 给出一个重物重量为X,另外提供的小砝码重量分别为1,3,9。。。3^N。 (假设N无限大,但一种重量的砝码只有一个) * 将重物放到天平左侧,问在两边如何添加砝码使两边平衡 * * 分析: * 三进制 * 我们约定括号表示里面的数是三进制,例如 47=(1202
public class ScalesBalance {

	/**
	 * 题目:
	 * 给出一个重物重量为X,另外提供的小砝码重量分别为1,3,9。。。3^N。 (假设N无限大,但一种重量的砝码只有一个)
	 * 将重物放到天平左侧,问在两边如何添加砝码使两边平衡
	 * 
	 * 分析:
	 * 三进制
	 * 我们约定括号表示里面的数是三进制,例如 47=(1202)
	 * 先看天秤右侧。放的全是砝码,由于一种重量的砝码只有一个,那么右侧的重量之和,用三进制表示的话,只包含0和1
	 * 要使两边平衡,那么左边的重量和的三进制也应该只包含0和1
	 * 那么答案就出来了:想办法使得左边的值只包含0和1,那就是把重物里面三进制表示里面的2变成0——对应的位置加1即可
	 * 将重物的重量转化为三进制,从最低位开始
	 * 1.遇到0 无操作 
	 * 2.遇到1 右边放  
	 * 3.遇到2 左边放 然后进位 
	 * 
	 * 在实际程序的书写中,
	 * 1、我们判断一个数三进制的表示里面某一位是0还是1还是2,直接对3求余就可以了;然后右移一位(除以3),再对3求余,则求得更高一位是0还是1还是2
	 * 2、统计放了什么砝码时,将对应的二制进位置为1,例如 3={11}{二进制},表示放了3^0和3^1这两个砝码;当然用数组存放也可以,只是浪费了空间
	 * 3、下面代码的balance函数的返回值永远是true,因为任意一个正整数都可以表示为三进制
	 */
	public static void main(String[] args) {
		for (int i = 1; i<= 100; i++) {
			boolean ok = balance(i);
			if (!ok) {
				System.out.println("error!");
			}
		}
	}

	/**
	 * @param weight	重物的重量,应该是一个正整数
	 * @return 是否可使得天秤平衡
	 */
	public static boolean balance(int weight) {
		if (weight <= 0) {
			System.out.println("invalid input.");
			return false;
		}
		int origin = weight;		//备份
		int left = 0;		//左边放了什么砝码
		int right = 0;		//右边放了什么砝码
		int i = 0;		//判断第i位是0是1还是2。0是最低位
		while (weight != 0) {
			int tmp = weight % 3;		
			if (tmp == 2) {
				weight += 1;
				left = left | (1 << i);		//对应的二进制位置1
			} else if (tmp == 1) {
				right = right | (1 << i);
			}
			i++;
			weight /= 3;
		}
		
		//上面已经求得答案了,现在输出验证一下
		StringBuilder sbLeft = new StringBuilder("" + origin);
		int sumLeft = origin;
		if (left != 0) {
			int power = 1;
			while (left != 0) {
				int value = left & 1;
				if (value == 1) {
					sbLeft.append(" + " + power);
					sumLeft += power;
				}
				power *= 3;
				left = left >> 1;
			}
		}
		
		int sumRight = 0;
		StringBuilder sbRight = new StringBuilder();
		if (right != 0) {
			int m = 1;
			while (right != 0) {
				int value = right & 1;
				if (value == 1) {
					sbRight.append(" + " + m);
					sumRight += m;
				}
				m *= 3;
				right = right >> 1;
			}
		}
		System.out.println(sbLeft.toString() + " = " + sbRight.substring((" + ").length()).toString());
		System.out.println(sumLeft + "," + sumRight);
		return sumLeft == sumRight;
		
	}
}

据说是2012年10月人人网校招的一道笔试题-给出一个重物重量为X,另外提供的小砝码重量分别为1,3,9。。。3^N。 将重物放到天平左侧,问在两边如何添加砝码

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
人人校招笔试题 人人校招笔试题 ---9月22日,人人校招笔试题 1、给定一个有序数组a,长度为len,和
人人校招笔试题 ---9月22日,人人校招笔试题 1、给定一个有序数组a,长度为len,和一个数X,判断A数
今天偶然整理东西,突然发现的试卷,应该是实验室的某师兄或者师姐送的吧,丢了挺可惜的,就放在这
本博客(http://blog.csdn.net/livelylittlefish )贴出作者(阿波)相关研究、学习内容所做的笔记
今天在网上溜达看到一篇不错的文章,网址是: http://blog.csdn.net/chinainvent/archive/2006/10/1
某公司的一道ruby笔试题 我的解题思路: 对每个数字做一个对应关系,数字 - 对应需要*号数量的表达
分布式系统中的RPC请求经常出现乱序的情况。 写一个算法来将一个乱序的序列报序输出,列如,假设起
今天在网上溜达看到一篇不错的文章,网址是: http://blog.csdn.net/chinainvent/archive/2006/10/1
战报交流:战场上不同的位置有N个战士(n>4),每个战士知道当前的一些战况,现在需要这n个战士
今天偶然整理东西,突然发现的试卷,应该是实验室的某师兄或者师姐送的吧,丢了挺可惜的,就放在这
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号