1、先说小点的数的阶乘计算:
// n! unsigned long fac(int n) { if(n == 0) return 1; else return n * fac(n - 1); }
2、如果需要稍微提高效率,还可以:
unsigned long fac_ex(int n) { if(n == 0 || n == 1) return 1; else return n * (n - 1) * fac(n - 2); }
3、依此类推,继续想提高一点效率:
unsigned long fac_ex1(int n) { if(n == 0 || n == 1) return 1; else if(n == 2) return 2; else return n * (n - 1) * (n - 2) * fac(n - 3); } unsigned long fac_ex3(int n) { if(n == 0 || n == 1) return 1; else if(n == 2) return 2; else if(n == 3) return 6; else return n * (n - 1) * (n - 2) * (n - 3) * fac(n - 4); }
4、如果不像用递归,那就用下面的,效率比递归的要好:
unsigned long fac_ex2(int n) { unsigned long ret = 1; for(int i = 2; i <= n; ++i) { ret *= i; } return ret; }
5、如果对空间要求不高,可以把一些数据计算出来,放在静态区:
unsigned long fac_ex10(int n) { static int facArr[] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, fac_ex2(11)}; // fac_ex2(11) will be calculated only once if(n >= 0 && n < sizeof(facArr) / sizeof(facArr[0])) return facArr[n]; else return n * (n - 1) * (n - 2) * (n - 3) * (n - 3) * (n - 3) * (n - 4) * (n - 5) * (n - 6) * (n - 7) * (n - 8) * (n - 9) * (n - 10) * fac(n - 11); }
6、上面的是放在函数里面,也可以放在文件作用域里或全局作用域:
static int facArr[] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, fac_ex2(11)}; // fac_ex2(11) will be calculated only once, at the initialization of the app
7、上面的不讨论了,现在讨论大整数阶乘:
// 大整数阶乘 void fac_bigInteger(int n, int result[], int maxSize, int *resultLen) { if(maxSize < 1) return; memset(result, 0, maxSize * sizeof(int)); result[0] = 1; int currLen = 1; for(int j = 2; j <= n; ++j) { int carry = 0; for(int k = 0; k < maxSize && k < currLen; ++k) { int temp = result[k] * j + carry; if(temp < 10) { result[k] = temp; carry = 0; } else { carry = temp / 10; result[k] = temp - carry * 10; } } if(carry > 0) { char buf[512]; sprintf(buf, "%d", carry); int currLenTemp = currLen; for(int i = strlen(buf) - 1; i >= 0; --i) { result[currLenTemp++] = buf[i] - '0'; } currLen = currLenTemp; } } *resultLen = currLen; }
测试代码:
void ccTestFac() { #if 1 int arr[1024]; int len; fac_bigInteger(50, arr, 1024, &len); for(int i = len - 1; i >= 0; --i) { std::cout << arr[i]; } std::cout << endl; std::cout << len << std::endl; #endif }