另一种阶乘问题（C/C++代码）

原题链接：题目65 - ACM在线评测系统

时间限制：3000 ms  |  内存限制：65535 KB

难度：1

描述

大家都知道阶乘这个概念，举个简单的例子：5！=1*2*3*4*5.现在我们引入一种新的阶乘概念，将原来的每个数相乘变为i不大于n的所有奇数相乘例如：5!!=1*3*5.现在明白现在这种阶乘的意思了吧！

现在你的任务是求出1!!+2!!......+n!!的正确值(n<=20)

输入

第一行输入一个a(a<=20)，代表共有a组测试数据
接下来a行各行输入一个n.

输出

各行输出结果一个整数R表示1!!+2!!......+n!!的正确值

样例输入

2
3
5

样例输出

5
23

解题思路：

要求出不大于n的所有奇数相乘，首先要看n是奇数还是偶数，假设n不小于5，若n为奇数，n!!=1*3*5...*n，若n为偶数，n!!=1*3*5...*(n-1)。任务是求出1!!+2!!......+n!!，可以用两个函数描述：

int f(int n)//求n!!
{
	if(n%2) return n==1?1:n*f(n-2);//n为奇数n!!=n*(n-2)!!
	return f(n-1);//n为偶数，n!!=(n-1)!!
}
int g(int n)//求1!!+2!!......+n!!
{
	return n?g(n-1)+f(n):0;
}

由于题目有多组数据，若用递归，每组数据求解会产生很多重复的过程，有没有方法既能消除递归又可以提高运算效率？有！用数组。由于n<=20，可以事先用循环累乘和累加为数组R[20+1]赋值，在输入测试用例之后一步就能查询到结果。

注意事项：

因为题目已经给出了n的范围，所以最好的方法是：求出答案直接赋值给数组。

参考代码：

#include<stdio.h>
int main(){
	int a,n=1,c=0,d=1,R[22]={0};
	scanf("%d",&a);
	while(n<21){
		d*=n;//阶乘
		c+=d;
		R[n]=c;//n为奇数
		c+=d;
		R[n+1]=c;//n+1为偶数
		n+=2;
	}
	while(a--){
		scanf("%d",&n);
		printf("%d\n",R[n]);
	}
	return 0;
}

优秀代码

#include<iostream>
using namespace std;
int main()
{
	int n,m,r[]={0,1,2,5,8,23,38,143,248,1193,
	2138,12533,22928,158063,293198,2320223,4347248,
	38806673,73266098,727995173,1382724248};
	cin>>n;
	while(n--)
	{
		cin>>m;
		cout<<r[m]<<endl;
	}
}