本书聚焦于在ACM竞赛中广泛应用的经典算法和编程技巧，通过丰富的示例代码帮助读者深入理解并熟练掌握这些关键技术。
### ACM竞赛常用算法及代码详解
#### 一、数学问题
**1. 精度计算——大数阶乘**
**语法**: `int result = factorial(int n);`
**参数**:
- `n`: 计算阶乘的数字。
**返回值**: 阶乘结果的位数。
**注意**:
- 该程序直接输出`n!`的结果。
- 使用长整型数组`a[]`来存储结果，并且需要包含头文件`math.h`.
**源程序**:
```c++
int factorial(int n) {
long a[10000];
int i, j, l, c, m = 0, w;
a[0] = 1;
for (i = 1; i <= n; i++) {
c = 0;
for (j = 0; j <= m; j++) {
a[j] = a[j] * i + c;
c = a[j] / 10000;
a[j] %= 10000;
}
if (c > 0) { m++; a[m] = c; }
}
w = m * 4 + log10(a[m]) + 1;
printf(%ld, a[m]);
for (i = m - 1; i >= 0; i--) printf(%4.4ld, a[i]);
return w;
}
```
**2. 精度计算——乘法（大数乘小数）**
**语法**: `mult(char c[], char t[], int m);`
**参数**:
- `c[]`: 被乘数，用字符串表示。
- `t[]`: 结果，用字符串表示。
- `m`: 乘数。
**返回值**: 无
**注意**:
- 需要包含`string.h`.
**源程序**:
```c++
void mult(char c[], char t[], int m) {
int i, l, k, flag, add = 0;
char s[100];
l = strlen(c);
for (i = 0; i < l; i++) s[l - i - 1] = c[i] - 0;
for (i = 0; i < l; i++) {
k = s[i] * m + add;
if (k >= 10) { s[i] = k % 10; add = k / 10; flag = 1; } else { s[i] = k; flag = 0; add = 0; }
}
if (flag) { l = i + 1; s[i] = add; } else l = i;
for (i = 0; i < l; i++) t[l - 1 - i] = s[i] + 0;
t[l] = \0;
}
```
**3. 精度计算——乘法（大数乘大数）**
**语法**: `mult(char a[], char b[], char s[]);`
**参数**:
- `a[]`: 被乘数，用字符串表示。
- `b[]`: 乘数，用字符串表示。
- `s[]`: 结果，用字符串表示。
**返回值**: 无
**注意**:
- 空间复杂度为 O(n^2).
- 需要包含`string.h`.
**源程序**:
```c++
void mult(char a[], char b[], char s[]) {
int i, j, k = 0, alen, blen, sum = 0;
char result[65];
int res[65][65] = {0};
alen = strlen(a);
blen = strlen(b);
for (i = 0; i < alen; i++)
for (j = 0; j < blen; j++) res[i][j] = (a[i] - 0) * (b[j] - 0);
for (i = alen - 1; i >= 0; i--) {
for (j = blen - 1; j >= 0; j--) sum += res[i + blen - j - 1][j];
result[k++] = sum % 10;
sum /= 10;
}
for (i = blen - 2; i >= 0; i--) {
for (j = 0; j <= i; j++) sum += res[i - j][j];
result[k++] = sum % 10;
sum /= 10;
}
if (sum != 0) {
result[k] = sum % 10; k++;
}
// 输出结果
for (int m = k - 1; m >= 0; m--) printf(%d, result[m]);
}
``
5星
