关于阶乘的一些讨论

我们今天要讨论的问题大意是:给定一个数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阶乘的和。

标签

赞这篇文章

分享到

1个评论

给作者留言

关于作者

残阳似血(@秦续业),程序猿一枚,把梦想揣进口袋的挨踢工作者。现加入阿里云,研究僧毕业于上海交通大学软件学院ADC实验室。熟悉分布式数据分析(DataFrame并行化框架)、基于图模型的分布式数据库和并行计算、Dpark/Spark以及Python web开发(Django、tornado)等。

博客分类

点击排行

标签云

扫描访问

主题

残阳似血的微博