2.3　循环的代价

例题2-4　阶乘之和

输入 n ，计算 S ＝1！＋2！＋3！＋…＋ n ！的末6位（不含前导0）。 n ≤10 6 ， n ！表示前 n 个正整数之积。

样例输入：

10

样例输出：

37913

【分析】

这个任务并不难，引入累加变量 S 之后，核心算法只有“for（int i＝1；i＜＝n；i＋＋）S＋＝i！”。不过，C语言并没有阶乘运算符，所以这句话只是伪代码，而不是真正的代码。事实上，还需要一次循环来计算i！，即“for（int j＝1；j＜＝i；j＋＋）factorial * ＝j；”。代码如下：

程序2-7　阶乘之和（1）

#include<stdio.h>
int main()
{
  int n, S = 0;
  scanf("%d", &n);
  for(int i = 1; i <= n; i++)
  {
    int factorial = 1;
    for(int j = 1; j <= i; j++)
      factorial *= j;
    S += factorial;
  }
  printf("%d\n", S % 1000000);
  return 0;
}

注意累乘器factorial（英文“阶乘”的意思）定义在循环里面。换句话说，每执行一次循环体，都要重新声明一次factorial，并初始化为1（想一想，为什么不是0）。因为只要末6位，所以输出时对10 6 取模。

提示2-15： 在循环体开始处定义的变量，每次执行循环体时会重新声明并初始化。

有了刚才的经验，下面来测试一下这个程序： n ＝100时，输出-961703。直觉告诉我们：乘法又溢出了。这个直觉很容易通过“输出中间变量”法得到验证，但若要解决这个问题，还需要一点数学知识。

提示2-16： 要计算只包含加法、减法和乘法的整数表达式除以正整数 n 的余数，可以在每步计算之后对n取余，结果不变。

在修正这个错误之前，还可以进行更多测试：当 n ＝10 6 时输出什么？更会溢出不是吗？但是重点不在这里。事实上，它的速度太慢！下面把程序改成“每步取模”的形式，然后加一个“计时器”，看看究竟有多慢。

程序2-8　阶乘之和（2）

#include<stdio.h>
#include<time.h>
int main()
{
  const int MOD = 1000000;
  int n, S = 0;
  scanf("%d", &n);
  for(int i = 1; i <= n; i++)
  {
    int factorial = 1;
    for(int j = 1; j <= i; j++)
      factorial = (factorial * j % MOD);
    S = (S + factorial) % MOD;
  }
  printf("%d\n", S);
  printf("Time used = %.2f\n", (double)clock() / CLOCKS_PER_SEC);
  return 0;
}

上面的程序再次使用到了常量定义，好处是可以在程序中使用代号MOD而不是常数1000000，改善了程序的可读性，也方便修改（假设题目改成求末5位正整数之积）。

这个程序真正的特别之处在于计时函数clock（）的使用。该函数返回程序目前为止运行的时间。这样，在程序结束之前调用此函数，便可获得整个程序的运行时间。这个时间除以常数CLOCKS_PER_SEC之后得到的值以“秒”为单位。

提示2-17： 可以使用time.h和clock（）函数获得程序运行时间。常数CLOCKS_PER_SEC和操作系统相关，请不要直接使用clock（）的返回值，而应总是除以CLOCKS_PER_SEC。

输入“20”，按Enter键后，系统瞬间输出了答案820313。但是，输出的Time used居然不是0！其原因在于，键盘输入的时间也被计算在内——这的确是程序启动之后才进行的。为了避免输入数据的时间影响测试结果，可使用一种称为“管道”的小技巧：在Windows命令行下执行echo 20|abc，操作系统会自动把20输入，其中abc是程序名 ⁽⁸⁾ 。如果不知道如何操作命令行，请参考附录A。笔者建议每个读者都熟悉命令行操作，包括Windows和Linux。

在尝试了多个 n 之后，得到了一张表，如表2-1所示。

由表2-1可知：第一，程序的运行时间大致和 n 的平方成正比（因为 n 每扩大1倍，运行时间近似扩大4倍）。甚至可以估计 n ＝10 6 时，程序大致需要近5个小时才能执行完。

提示2-18： 很多程序的运行时间与规模 n 存在着近似的简单关系。可以通过计时函数来发现或验证这一关系。

第二，从40开始，答案始终不变。这是真理还是巧合？聪明的读者也许已经知道了：25！末尾有6个0，所以从第5项开始，后面的所有项都不会影响和的末6位数字——只需要在程序的最前面加一条语句“if（n＞25）n＝25；”，效率和溢出都将不存在问题。

本节展示了循环结构程序设计中最常见的两个问题：算术运算溢出和程序效率低下。这两个问题都不是那么容易解决的，将在后面章节中继续讨论。另外，本节中介绍的两个工具——输出中间结果和计时函数，都是相当实用的。 CZiVBDuWxGA173mzbDTB1eonsH0a5EXvanbTLyPLTUv7WE5xvJChBBmusc+jrrQR