放麦子_蓝桥杯题目

今天做了个蓝桥杯的题目，放麦子。题目简单，确发掘了几种解法，感受到编程的魅力，记录分享一下。

你一定听说过这个故事。国王对发明国际象棋的大臣很佩服，

问他要什么报酬，大臣说：请在第1个棋盘格放1粒麦子，

在第2个棋盘格放2粒麦子，在第3个棋盘格放4粒麦子，

在第4个棋盘格放8粒麦子，......后一格的数字是前一格的两倍，

直到放完所有棋盘格（国际象棋共有64格）。

国王以为他只是想要一袋麦子而已，哈哈大笑。

当时的条件下无法准确计算，但估算结果令人吃惊：即使全世界都铺满麦子也不够用！

请你借助计算机准确地计算，到底需要多少粒麦子。

当然，这道题也是考察对大整数的计算，本题的数字一定是用BigInteger类型才能解决的，不然蓝桥杯不至于考这么low的题目。

第一种方法使用了递归。

import java.math.BigInteger;
public class Q_12 {
	public static void f(BigInteger sum,int k){
		if(k==64){
			System.out.println(sum);
			return;
		}
		sum = sum.add(BigInteger.valueOf(	(long)(Math.pow(2,k))	));
		//sum = sum.add(new BigInteger("2").pow(k));
		//两种算法均可
		f(sum,k+1);
	}
    public static void main(String[] args) {
    	BigInteger sum = BigInteger.ZERO;

    	f(sum,0);
    }
}

第二种解法，其实这样小的程序，使用递归反而占用了更多的资源，不如直接使用一个for循环。

第三种解法，算了半天，笨的我就是没想到，这个数就是（2^64-1） 。这道题简单的居然一行输出语句就能解决的地步。真是应该做很多反思，编程的目的是为了解放双手，

我们能用一行代码解决的问题却又花了大把时间去搞递归、循环，呵呵。生活中的事情不也是如此吗？ 反思，切记。

import java.math.BigInteger;
public class Q_12 {
	public static void main (String[] args) {
	BigInteger sum = BigInteger.ZERO;
	BigInteger base = new BigInteger("2");
	for(int i=0;i<64;i++){
		sum = sum.add(	base.pow(i)	);
	}

	System.out.println(sum);

	//一行解决问题
	System.out.println(	base.pow(64).subtract(BigInteger.ONE));
	}
}