欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

求阶乘以及求各项阶乘和问题

程序员文章站 2024-03-15 17:15:18
...

下午做了一道笔试题,试求各项阶乘和的问题,也就是求 : 1! + 2! + ... + n!。

一开始没什么思路,那就想着暴力求。。。就是从1~n,求每一项的阶乘,再求和,效率肯定低,当时脑子浑噩,脑子里想着这样肯定是有重复相乘的,但就是没能想出优化的T_T

好吧,那就先来暴力求解吧。关于求阶乘的,用了递归求解(关键当时递归还给漏了个n,还是渣啊),想到可能会数很大,就暂时用了long型

/**
	 * 求n的阶乘
	 * @param n
	 * @return
	 */
	 long getFactorial(int n) {
		if(n == 0 || n == 1)
			return 1;
		
		return n*getFactorial(n-1);
	}
再从1~n遍历求和

long getFactorialSum(int n) {
		if(n == 1)
			return 1;
		
		long result = 1;
		
		for (int i = 2; i <= n; i++) {
			
			result += getFactorial(i);
		}
		return result;
	}
应该是可以解决了。。。。


但是刚交了卷,出来后再想了一下,竟然想通了。。。

发现求阶乘: n! = n * (n-1)!,而求和中我们完全可以从底层开始求起,并用一个变量记录当前的阶乘项,每轮把它乘上i,不就相当于就得 n!了,再把这项加到和中就可以了,完全不用单独去求阶乘,这也是基于了所谓的动态规划,把前面的结果拿来用,不用重复计算。上代码

/**
	 * 求: 1! + 2! + ... + n!
	 * @param n
	 * @return
	 */
	long getFactorialSum(int n) {
		if(n == 1)
			return 1;
		
		long result = 1;
		long currentFactorial = 1; //记录第i项阶乘结果的
		
		for (int i = 2; i <= n; i++) {
			currentFactorial *= i ;
			result += currentFactorial;
		}
		return result;
	}


相关标签: 求阶乘