残阳似血的博客

我们今天要讨论的问题大意是：给定一个数n，判断是否存在一个数m，使得：n == ∑i!（这里共m个不同整数）。（n≤1000000)

说白了其实就是：给定一个数n，看看这个数能不能表示成从m个不同整数阶乘的和。

刚拿到题目可能没有思路。仔细考虑可以注意到，n的最大值为1000000，小于32位机器上的int型的最大值（2^31-1），最先可能想到的是枚举法，由于10!>1000000，所以可能出现的0-9这几个数，每个数都有出现或者不出现两种情况，如果枚举将会有2^10共1024种情况，这个数量也不小。这就意味着需要换个思路来考虑。

注意到，对于一个整数k（k>1），0! + 1! + ... + (k-1)! < k!（左边 < k * (k-1)! == k!），因此，我们可以得出结论，对于一个数n，假设一个数j，使得j! ≤ n 且 (j+1)! > n，那么n分解成阶乘和的数中必定包含j!，用反证法证明，假设不包含，由之前的结论，小于j的所有数的阶乘和都小于j!，当然也必小于n。因此，当n = n - j!后，再判断n是否等于新的j!，等于证明分解成功；否则就减去新的j!，并循环判断。

于是，我们很容易得出以下代码。

public final static int count = 10;
	
public static int[] Facs(){
	int temp = 1;
	int[] facs = new int[count];
		
	for(int i=0; i<count; i++){
		if(i != 0)
			temp = temp * i;
		facs[i] = temp;
	}
		
	return facs;
}
	
public static boolean facsSum(int n){
	int rest = n;
	int current = count - 1;
		
	int[] facs = Facs();
		
	while(rest >= 0 && current >= 0){
		if(rest >= facs[current]){
			rest -= facs[current];
		}
		current--;
	}
		
	if(rest == 0)
		return true;
	return false;
}

这里有个技巧，在上面的代码中，Facs函数把0到9的阶乘储存在一个数组当中。这里有的同学可能会这么写代码。

private static int factorials(int n){
	if(n<=1)
		return 1;
	return factorials(n-1)*n;
}

private static int[] Facs(){
	int[] retFacs = new int[count];
	for(int i=0; i<count; i++){
		retFacs[i] = factorials(i);
	}
	return retFacs;
}

注意到差别没有，其实我们上一次用到的阶乘存放在临时数中，下轮就可以直接拿来使用。第二种方法更直观，但是重复的运算、加上递归的使用，使代码的效率低了许多。

因此，大家可以试试只用一个循环来计算1到100阶乘的和。