#include <iostream>
#include <math.h>
using namespace std;

long factorial(int n)
{
	int i;
	long result = 1;
	for (i=1; i<=n; i++)
		result *= i;
	return result;
}

long C(int n, int m)
{
	return factorial(n) / factorial(m) / factorial(n-m);
}

long f(int n)
{
	if (n==1 || n==2)
		return 1;
	if (n==3)
		return 4;
	int m = C(n, 2);
	int p = pow(2, m);
	long result = p;
	int i;
	for (i=1; i<n; i++)    //递归
	{
		result -= C(n, i)*f(i);
	}
	return result;
}

int main()
{
	int n;
	cin>>n;
	long result;
	while (n!=0)
	{
		result = f(n);
		cout<<result<<endl;
		cin>>n;
	}
	return 0;
}
主要是中间的递归如何改成递推式不会。

• Re:这是我的源代码，但是运行超时，请高手帮忙改一下。 (752) huatao 2008-03-23 10:17:46
• 这么多年了……改记忆化吧，n!每次都现算，f每次都现算……不TLE才怪 (2) applepi 2010-09-02 19:14:50