03.梅氏砝码问题

腾讯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