1 循环展开 1
C 语言循环的小艺术 (3)
作者：Misakamm
博客：http://misakamm.com
前言
写代码，有两类追求，一种是追求实用（Coder），一种是追求代码艺术（Artist）我是
那种追实用追腻了，偶然追一下艺术（就是偶然和艺术有一腿）的那种 Coder。
本文作者 Misakamm（御坂美琴），如果你见本文发布 ID 并不是如上帐号，或者经联
系本人确认那个是盗用或相近 ID，那么即为转载文。自从连载文在猫爪做图标的文库站发了
不到一天，我就发现在某 D 站居然有一模一样的文章，连我的 PDF 都丝毫不改，可见我大
瓷器的某些人为了某些可能连利益都不算的东西在不择手段，太可怕了。
1 循环展开
这个标
题
快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题
其实不是问题，不过要说明这个问题，也需要例题。例题是这样的：
计算并输出以下式子的结果
1� 1
2
+
1
3
� 1
4
+
1
5
� ::::::� 1
1000
对于这个问题，输出结果应该是 0.692647，很多人可能这样子写：
1 #include
2 int main( void )
3 {
4 double sum = 0;
5 int i, v, mul = 1;
6 for ( i = 1; i <= 1000; ++i )
7 {
8 v = i * mul;
9 sum += 1.0 / v;
10 mul *= �1;
11 }
12 printf( ”%f”, sum );
13 return 0;
14 }
或者有人写成：
1 #include
2 int main( void )
3 {
1 循环展开 2
4 double sum = 0;
5 int i;
6 for ( i = 1; i <= 1000; ++i )
7 {
8 if ( i % 2 == 1 )
9 {
10 sum += 1.0 / i;
11 }
12 else
13 {
14 sum �= 1.0 / i;
15 }
16 }
17 printf( ”%f”, sum );
18 return 0;
19 }
但是你有没有想过这样来写？
1 #include
2 int main( void )
3 {
4 double sum = 0;
5 int i;
6 for ( i = 1; i < 1000; i += 2 )
7 {
8 sum += (1.0 / i) � (1.0 / (i+1));
9 }
10 printf( ”%f”, sum );
11 return 0;
12 }
不但循环判断没有了，代码也简化了，同时也更容易看懂了。当然这里说的循环展开，并
不是完全展开，是合理的展开一些，让代码更和谐。比如以上计算，明显的是以 2 为周期产
生变化，于是我们干脆的在每次循环直接做两步的运算，逻辑上是完全等价的，但让代码实现
上变得简洁，不过不是所有情况这个周期都这么明显。
同样的例子如计算 1+2-3-4+5+6-7-8+9+...+97+98-99-100
1 #include
2 int main( void )
3 {
4 int sum = 0;
1 循环展开 3
5 int i;
6 for ( i = 1; i < 100; i += 4 )
7 {
8 sum += i + (i+1) � (i+2) � (i+3);
9 }
10 printf( ”%d”, sum );
11 return 0;
12 }
事实上，对 i + (i+1) - (i+2) - (i+3) 化简的话，你会发现什么？
不过，并不总应该这样做，即使能让代码简化，但可能让代码变得不容易懂。如 fib 数
列：1,1,2,3,5,8,13,21,34,55,......
写一个
函数
excel方差函数excelsd函数已知函数 2 f x m x mx m 2 1 4 2拉格朗日函数pdf函数公式下载
求这个数列的第 n 项（假设 n 不大，小于 40）。定义 fib(0)=0,fib(1)=1，
我们写出这样一个函数：
1 int fib( int n )
2 {
3 int f[100] = {0, 1}, i;
4 for ( i = 2; i <= n; ++i )
5 {
6 f[i] = f[i � 1] + f[i � 2];
7 }
8 return f[n];
9 }
这种写法相当的好理解，尽管空间有点浪费。如果实在在意空间，那么使用滚动数组解
决：
1 int fib( int n )
2 {
3 int f[2] = {0, 1}, i;
4 for ( i = 2; i <= n; ++i )
5 {
6 f[i % 2] = f[(i � 2) % 2] + f[( i � 1 ) % 2];
7 }
8 return f[n % 2];
9 }
或者
1 int fib( int n )
2 {
3 int f1 = 0, f2 = 1, f, i;
2 循环链
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
4
4 if ( n <= 1 )
5 {
6 return n;
7 }
8 for ( i = 2; i <= n; ++i )
9 {
10 f = f1 + f2;
11 f1 = f2;
12 f2 = f;
13 }
14 return f2;
15 }
仍然能保持比较好的可读性。
不过，某本作为教材且买得非常广泛的书里（据说上千万册），写法使用了本节所介绍的
技巧，即循环展开来做，代码如下：
1 int fib( int n )
2 {
3 int f1 = 0, f2 = 1, i;
4 for ( i = 2; i <= n; i += 2 )
5 {
6 f1 = f1 + f2;
7 f2 = f1 + f2;
8 }
9 if ( n % 2 == 1 )
10 {
11 return f2;
12 }
13 return f1;
14 }
以上这段代码把滚动数组和循环展开两个技巧一起用上了，这个技巧的确让代码简洁了好
多，可是同时带来了理解上的困难，作为一本入门级别的书在这里耍弄技巧，让很多新人不知
所以然。所以使用本技巧，最好看看场合。
2 循环链表
Misakamm 提问：你觉得链表一定要用指针吗？见题目：10 个人依次站成一圈，编号
1-10，从 1 号开始向 2 号方向报数“1，2，3”，报到 3 的出列，然后出列的下一人再从
1 开始报，问出列的次序。
2 循环链表 5
这个问题，如果是手工计算，列表如下：1 2 3 4 5 6 7 8 9 10 先出圈 3,6,9，剩
下：1 2 4 5 7 8 10 再从 10 开始报，出圈 2,7,1，如此类推，最后出列次序是：3 6
9 2 7 1 8 5 10 4
好了，对于这个问题（我们先抛开数学解法不谈）你觉得你会写多长的代码？通常你光写
个链表模块就已经占了几十行了不是？很麻烦。如果不是链表，用标记法，那么已经出列的还
会多次遍历到，事实上，用链表写的话，意义直观，结构清晰，见如下代码：
1 #include
2 int main( void )
3 {
4 int n = 10, step = 3, out, pre, next[1000];
5 int i;
6 //scanf( ”%d%d”, &n, &step ); //如果需要手工输入数据
7 for ( i = 1; i < n; i++ )
8 {
9 next[i] = i + 1;
10 }
11 next[n] = 1;
12
13 for ( out = 1, pre = n; out <= n; ++out )
14 {
15 for ( i = 1; i < step; ++i )
16 {
17 pre = next[pre];
18 }
19 printf( ”␣%d”, next[pre] );
20 next[pre] = next[next[pre]];
21 }
22 return 0;
23 }
这个是链表解法，但你可能说，这里都没有指针！但我得要问你了，谁规定了链表非要使
用指针呢？没有！数据结构和你实现它所使用的数据类型根本没有关系。那我来解释一下这个
链表数据结构。这个结构在 next 这个数组里，next[i] 的值，表示它的下一个对象的下
标值，就这样简单的定义了一个链表。然后，我们这样子对它赋值：
1 for ( i = 1; i < n; i++ )
2 {
3 next[i] = i + 1;
4 }
5 next[n] = 1;
2 循环链表 6
表示第 i 个指向第 i+1 个，而第 n 个指向第一个，形成环链表。然后准备按题目的
规则来遍历这个链表。首先，pre 记录的，是准备报数的人的前一个（于是 next[pre] 就
是正要报数的人），out 记录当前是第几轮（或将要出圈的人是第几个），n 是总人数，step
是报到多少就出圈，于是这个内循环，就是 pre 沿着这个链表，前进 step-1 步：
1 for ( i = 1; i < step; ++i )
2 {
3 pre = next[pre];
4 }
走完这 step-1 步后，准备要报数的人必定是 next[pre]，直接输出它，然后这个人
要出列，所以 pre 的下一个人，改为 pre 的下下个人，就这么简单的把它从这链表中 T
掉了。
注意事项，如果你的编译器支持 C99 或更新的
标准
excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载
（甚至直接用的 C++ 编译），建议
改为如下代码：
1 #include
2 int main( void )
3 {
4 int n = 10, step = 3, next[1000];
5 //scanf( ”%d%d”, &n, &step );
6 for ( int i = 1; i < n; i++ )
7 {
8 next[i] = i + 1;
9 }
10 next[n] = 1;
11
12 for ( int out = 1, pre = n; out <= n; ++out )
13 {
14 for ( int i = 1; i < step; ++i )
15 {
16 pre = next[pre];
17 }
18 printf( ”␣%d”, next[pre] );
19 next[pre] = next[next[pre]];
20 }
21 return 0;
22 }
至于其它的非链表解法在本文不作介绍。
千万别以为复杂的数据结构非指针不可，很多 NOI/ACM 老手实现树和图，都直接开数
组表示（但不表示这种做法总是好事，必须看场合），最为经典的例子，可以参阅 heap（一
2 循环链表 7
种完全二叉树）的数组实现，指针在这里反而会很不利于程序的调试。
很多人说什么“指针是 c 语言的灵魂”“指针是 c 语言的精髓”，我不知道你们会怎么
看待这句话，但在我看来就是扯谈，就像“米就是饭桌上的精髓”差不多，汇编语言还到处
都是指针呢。c 没有给我们多么高明的东西，可以看成只是一堆原材料，“灵魂”和“精髓”，
在于如何去使用和搭配原材料。
连载文 1：http://wenku.baidu.com/view/e0ba89bc65ce0508763213cb.html
连载文 2：http://wenku.baidu.com/view/67afee1952d380eb62946dd4.html
Author: Misakamm
Blog: http://misakamm.com
浙公网安备 33021202002483