今天淘宝的笔试题

有个题是这样的：现在有7公斤大米，有50g和200g的砝码各一个，问怎样用最少的步骤称出1350g的大米？编程实现之

24 个解决方案

#1

1.把50g和200g的砝码放一边，称出250g米
2.把砝码放到米那一边，原来放砝码的那一边放上米，称出500g米
3.把第一次称出的250g和第二次称出的500g放一起，把50g的砝码放另一边，并在砝码那一边加米，知道平衡
4.把第3步两边的米加到一起就是1350g了

#2

不好意思，第一步错了，只要放200g的砝码就可以了

#3

贪心算法

#4

1.把7kg大米平均放在天平两边，取其中一份即3500g
2.同1步骤，取出1750g
3.天平一端放200g砝码，取出200g大米，剩余1550g
4.同3步骤，再取200g，剩余1350g
貌似步骤不怎么少呀

#5

题目没给秤，你们也能称出来？今天淘宝的笔试题

#6

1. 7公斤分两边，其中一边加200g砝码，分成3.6kg和3.4kg两份。
2. 3.4kg分两边，其中一边加200g砝码，分成1.8kg和1.6kg两份。
3. 从1.6kg取出200+50g，成功！

#7

说了是编程啊，用代码可以实现啊

#8

这是淘宝什么职位的面试题？

#9

该回复于2011-03-28 16:22:00被版主删除

#10


                int small =50;
		int big =200;
		int rice =0;
		int count =0;
		int max = small+big;
		while(max!=2000){
			rice+=max;
			max=rice+small+big;
			count++;
		}
		System.out.println("rice:"+rice);
		System.out.println("count:"+count);

#11

这个行么？

引用 10 楼 chenghaoorange 的回复:

Java code

                int small =50;
        int big =200;
        int rice =0;
        int count =0;
        int max = small+big;
        while(max!=2000){
            rice+=max;
      ……

#12

mark

#13

既然是编程实现，肯定就不是楼上几位这种了吧？要是称1400g不就完蛋了。。
动态规划就能解决

#14

6楼为正解，3步骤为标准答案，不过答案并不唯一，不过超过3步骤的肯定中间有值得优化的地方，这里另一种思路来解题：

假如天平为A、B两个秤盘；

步骤1：将200g砝码+50g砝码放在天平A，那么B上可以称出250g重量大米；
步骤2：将200g砝码+50g砝码移动到B上，即B秤盘上有500g重量，A上即可称出500g重量大米；
步骤3：此时将大米都放在A上，即A上有750g大米，再放上一个50g的砝码即有800g重量；将另一个砝码放在B上，即B上需要600g大米即可平衡；此时两个秤盘上的大米分别为750g+600g=1350g。

三次即可称出具体答案。

#15

不好意思，刚才说错了，6楼的哥们；

你可以看下，如果是用7.2kg除以2以后，还是剪掉2kg来得到比较小的数据嘛？那样两遍的天平的大米差距就不是2kg了吧，而是4kg了吧，3.4kg+3.6kg的确是7kg，但是你这个时候是带上天平的砝码算的。

#16

真是晕了，想通了，不好意思，呵呵

#17

都说了是用程序实现了了还在写！！！

#18

这么无聊的题目啊

#19

JAVA代码，我的超级麻烦的算法，希望对你有帮助

import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Map;
import java.util.Set;

public class Rice {
public static void main(String[] args) {
double resault = 1350;
double max = 7000;
LinkedList<Map<Double,Double>> l = new LinkedList<Map<Double,Double>>();
Set<Double> s = new HashSet<Double>();
s.add(0d);
s.add(max);
// s.add(resault);
Map<Double,Double> m0 = new HashMap<Double, Double>();
m0.put(0d,null);
m0.put(max, null);
// m0.put(resault, null);
l.add(m0);
int n = 0;
do{
n++;
Map<Double,Double> m = new HashMap<Double, Double>();
Iterator<Double> it = l.getLast().keySet().iterator();
while(it.hasNext()){
double d = it.next();
for (int i = 0; i < 27; i++) {
double dx = d;
if (i / 9 == 1) {
dx *= 2;
}
switch (i % 9) {
case 0:
dx += 250;
break;
case 1:
dx += 200;
break;
case 2:
dx += 150;
break;
case 3:
dx += 50;
break;
case 4:
dx += 0;
break;
case 5:
dx -= 50;
break;
case 6:
dx -= 150;
break;
case 7:
dx -= 200;
break;
case 8:
dx -= 250;
break;
}
if (i / 9 == 2) {
switch(i%9){
case 0:
case 8:
if(dx<=250){
dx=-1d;
}
break;
case 1:
case 7:
if(dx<=200){
dx=-1d;
}
break;
case 2:
case 6:
if(dx<=150){
dx=-1d;
}
break;
case 3:
case 5:
if(dx<=50){
dx=-1d;
}
break;
}
dx /= 2;
}
if(dx>=0&&dx<=max){
if(!s.contains(dx)){
System.out.println(dx);
m.put(dx, d);
s.add(dx);
}
if(!s.contains(max-dx)){
System.out.println(max-dx);
m.put(max-dx, d);
s.add(max-dx);
}
}
}
}
l.add(m);
}while(!s.contains(resault));
System.out.println("=============");
System.out.println(n);
System.out.println(s.size());
System.out.println("=============");
double dd = resault;
while(l.size()>1){
Map<Double,Double> m = l.pollLast();
dd = m.get(dd);
System.out.println(dd);
}
}
}

#20

引用 5 楼 ai_quaner 的回复:

题目没给秤，你们也能称出来？

哈哈

#21

至少三步吧

#22

学习学习，，，，

#23

了解下思路。。

#24

用50g的砝码称出50g,剩下的就是1350g

#1

#2