回复:(暴风)新手,问题。
/*---------------------------------------------------------------------------
File name: sumOfFactorials.cpp
Author: HJin (email: fish_sea_bird [at] yahoo [dot] com )
Created on: 7/15/2007 02:23:48
Environment: Windows XP Professional SP2 English +
Visual Studio 2005 v8.0.50727.762
我想求1!+2!+3!+..+n!, n = 12。
(n> 12 will overflow the 32-bit integers.)
Output:
1 1 1
2 3 3
3 9 9
4 33 33
5 153 153
6 873 873
7 5913 5913
8 46233 46233
9 409113 409113
10 4037913 4037913
11 43954713 43954713
12 522956313 522956313
Press any key to continue . . .
*/
#include <iostream>
using namespace std;
/** version 1 --- one of the best algorithms.
O(1) space + O(n) time.
*/
int sumOfFactorials(int n);
/** version 2
O(n) space + O(n) time.
Thus, version 1 is better.
*/
int sumOfFactorials2(int n);
int main()
{
for(int i=1; i<=12; ++i)
{
cout<<i<<"\t"<<sumOfFactorials(i)<<"\t\t"<<sumOfFactorials2(i)<<endl;
}
return 0;
}
int sumOfFactorials(int n)
{
int currFactorial = 1;
int currSum = 1;
int k;
for( k = 2; k<=n; ++k)
{
currFactorial *= k;
currSum += currFactorial;
}
return currSum;
}
int sumOfFactorials2(int n)
{
if(n<1)
{
return 1;
}
int *factorials = new int[n];
int i;
factorials[0] = 1;
for(i=1; i<n; ++i)
{
factorials[i] = (i+1) * factorials[i-1];
}
for(i=0; i<n-1; ++i)
{
factorials[n-1] += factorials[i];
}
// use i to store the result
i = factorials[n-1];
delete [] factorials;
return i;
}
[此贴子已经被作者于2007-7-15 17:40:10编辑过]