腾讯2014年笔试附加题：用4个砝码称出重量在1到40克内的钻石，这4个砝码分别多重（钻石重量为整型）
其实题目是由梅式砝码问题演化而来，德·梅齐里亚克的法码问题(The Weight Problem of Bachet de Meziriac)原题描述为
一位商人有一个40磅的砝码,由于跌落在地而碎成4块.后来,称得每块碎片的重量都是整磅数,而且可以用这4块来称从1至40磅之间的任意整数磅的重物.问这4块砝码碎片各重多少?
需要分析是4个砝码
a+b+c+d=40;
如果有需要称重1，则必须有1个砝码是1
则a=1；
如果想称重2，则可以利用天平一边是砝码a=1，另一边是砝码b=3
则b=3；
称重3可以用砝码b
称重4可以使用砝码a+砝码b
此时如果需要称重5，必须借助于砝码c，也就是说推导算式：
砝码c - (砝码a+砝码b) = 1 + (砝码a+砝码b)
进一步总结
- 第一个砝码n(1)： 1
- 第二个砝码n(2)： n(2) - n(1) = n(1) + 1 即 n(2) = 2*∑(n(1))+1
- 第三个砝码n(3)： n(3)- (n(1)+n(2)) = (n(1)+n(2))+1 即 n(3) = 2*∑(n(2)...n(1))+1
- 第m个砝码n(m)： n(m) - (n(m-1)+n(m-2)+...+n(1)) = (n(m-1)+n(m-2)+...n(1))+1
即 n(m) = 2* ∑(n(m)...n(1))+1
其实这道题继续分析下去，发现其实就是利用n个砝码表示从1开始的连续的几个数。与总数40无关，只要求出前4个砝码，自然能到到需要的结果
利用递归解决问题
public class Meziriac {
public static int f(int n) {
if(n == 1) {
return 1;
}else {
int x = 0;
for(int i = 1; i < n; i++) {
x += f(i);
}
return x*2+1;
}
}
public static void main(String[] args) {
for(int i = 1; i <= 4; i++) {
System.out.println(f(i));
}
}
}
运行结果
运行结果
4个砝码求和自然是40
