第5章
利用数组处理批量数据
　　５．１　用筛选法求１００ 
之内的素数。
解
： 
解题思路。所谓“筛法”指的是“埃拉托色尼（Ｅｒａｔｏｓｔｈｅｎｅｓ）筛法”。埃拉托色尼
是古希腊的著名数学家。他采取的方法是，在一张纸上写上１～１０００ 
的全部整数，然后逐
个判断它们是否是素数，找出一个非素数，就把它挖掉，最后剩下的就是素数，见图５.
１ 
。

　　......................................

① 
２３ ④ ５ ⑥ ７ ⑧ ⑨ ⑩ 
１１ 
..
.. 
１３ .. 
....
.. 
１９ 
..............
.. 
２９ 
............
........
.. 
２３ 
..
.. 
......
.. 
３１ 
..
.. 
..
.. 
..

.. 
１７ ..
３７ 
....................
..


.. 
..
.. 
..
.. 
４１ 
......
.. 
４７ 
..
.. 
..

.. 
４３ 
............
…
图　５.
１


具体做法如下。

（１） 
先将
１ 
挖掉（因为
１ 
不是素数）。
（２） 
用
２ 
去除它后面的各个数，把能被
２ 
整除的数挖掉，即把
２ 
的倍数挖掉。
（３） 
用
３ 
去除它后面各数，把
３ 
的倍数挖掉。
（４） 
分别用４，５…各数作为除数去除这些数以后的各数。这个过程一直进行到在除
数后面的数已全被挖掉为止。例如在图５.
１ 
中找１～５０ 
的素数，要一直进行到除数为４７ 
为止。事实上，可以简化，如果需要找１～
ｎ 
的素数表，只须进行到除数为
ｎ （ 
取其整数
） 
即可。例如对１～５０，只须进行到将７（即５０ 
的整数部分）作为除数即可。请读者思考为
什么
？ 
上面的算法可表示如下。

（１） 
挖去１。
（２） 
用下一个未被挖去的数
ｐ 
去除
ｐ 
后面各数，把
ｐ 
的倍数挖掉。
（３） 
检查
ｐ 
是否小于
ｎ 
的整数部分（如果ｎ＝１０００，则检查ｐ＜３１？）
， 
如果是，则返回
（２）继续执行，否则就结束。
（４） 
剩下的数就是素数。
用计算机解此题，可以定义一个数组ａ。数组元素ａ［１
］ 
～ａ［ｎ
］ 
分别代表１～
ｎ 
这
ｎ 
个数。如果检查出数组
ａ 
的某一元素的值是非素数，就使它变为０，最后剩下不为
０ 
的就
是素数。

编写程序如下。


　４３ 
　　#include<stdio.h> 
#include<math.h>　　　　　　　　　　//程序中用到求平方根函数sqrt 
int main() 
　{ int i,j,n,a[101];　　　　　　　　/　/定　义a 数组包含101 个元素
　for (i=1;i<=100;i++)　　　　　　//　a　[0]不用,只用a[1]~a[100] 
　　　a[i]=i;　　　　　　　　　　　　//使a[1]~a[100] 的值为1~100 
　a[1]=0;　　　　　　　　　　　　　　//先"挖掉"a[1] 
　for (i=2;i<sqrt(100);i++) 
　　for (j=i+1;j<=100;j++) 
　　{ if(a[i]!=0 && a[j]!=0) 
　　　　if (a[j]%a[i]= =0) 
　　　　　a[j]=0;　　　　　　　　　//把非素数“挖掉” 　　} 
　printf("\n"); 
　for (i=2,n=0;i<=100;i++) 
　　{if (a[i]!=0)　　　　　　　　　/　/选　出值不为0 的数组元素,即素数　
　　　{printf("%5d",a[i]);　　　　/　/输　出素数,宽度为5 列
　　　n++;　　　　　　　　　　　　　//累计本行已输出的数据个数
　　} 
　　if(n= =10) 
　　　{ printf("\n"); 
　　　　n=0; 
　　　} 
　　} 
　printf("\n"); 
　return 0; 
} 
运行结果： 
　　
2 3 5 7 11 13 17 19 23 29 
31 37 41 43 47 53 59 61 67 71 
73 7 83 89 97 
输入数组ａ 各元素
ｆｏｒ （ｉ ＝ １； ｉ≤９； ｉ＋＋） 
ｍｉｎ ＝ ｉ 
ｆｏｒ （ｊ ＝ ｉ＋１； ｊ≤１０； ｊ＋＋） 
　　Ｔ ａ ［ｍｉｎ］＞ａ［ｊ］ Ｆ　　
ｍｉｎ ＝ ｊ 
交换ａ［ｍｉｎ］与ａ［ｉ］ 
输出已排序的１０ 个数
图　５.２ 
５．２　用选择法对１０ 个整数排序。
解： 解题思路。选择法的思路如下： 设有１０ 个元素ａ［１］ ～ ａ［１０］， 将ａ［１］ 与ａ［２］ ～ 
ａ［１０］比较，若ａ［１］比ａ［２］ ～ ａ［１０］都小，则不
进行交换，即无任何操作。若ａ［２］ ～ ａ［１０］中
有一个以上比ａ［１］ 小，则将其中最大的一个
（假设为ａ［ｉ］） 与ａ［１］ 交换，此时ａ［１］中存
放了１０ 个数中最小的数。第２ 轮将ａ［２］与
ａ［３］ ～ ａ［１０］比较，将剩下９ 个数中的最小者
ａ［ｉ］与ａ［２］对换，此时ａ［２］中存放的是１０ 个
中第二小的数。以此类推，共进行９ 轮比较， 
ａ［１］ ～ ａ［１０］ 就已按由小到大的顺序存放了。
Ｎ.Ｓ 图如图５.２ 所示。

　４４ 
编写程序如下。
　　#include<stdio.h> 
int main() 
　{ int i,j,min,temp,a[11]; 
　printf("enter data:\n"); 
　for (i=1;i<=10;i++) 
　{printf("a[%d]=",i); 
　　scanf("%d",&a[i]);　　　　//输入10 个数
　} 
　printf("\n"); 
　printf("The orginal numbers:\n"); 
　for (i=1;i<=10;i++) 
　　printf("%5d",a[i]);　　　　/　/输　出　这　10 个数
　printf("\n"); 
　for (i=1;i<=9;i++)　　　　　/　/　以　下　8 行是对10 个数排序
　　{min=i; 
　　for (j=i+1;j<=10;j++) 
　　　if (a[min]>a[j]) min=j; 
　　temp=a[i];　　　　　　　　　//以下3 行将a[i+1]～ a[10]中最小者与a[i]对换
　　a[i]=a[min]; 
　　a[min]=temp; 
　　} 
　printf("\nThe sorted numbers　:\　n　")　;　　　　//输出已排好序的10 个数
　for (i=1;i<=10;i++) 
　　printf("%5d",a[i]); 
　printf("\n"); 
　return 0; 
} 
运行结果： 
　　enter data: 
a[1]=1 ↙ 
a[2]=16 ↙ 
a[3]=5 ↙ 
a[4]=98 ↙ 
a[5]=23 ↙ 
a[6]=119 ↙ 
a[7]=18 ↙ 
a[8]=75 ↙ 
a[9]=65 ↙ 
a[10]=81 ↙ 
The orginal numbers: 
　　1　16　　5　98　23　119　18　75　65　81　

　４５ 
The sorted numbers: 
　　1　　5　16　18　23　65　75　81　98　119　
５．３　求一个３×３ 的整型二维数组对角线元素之和。
解： 编写程序如下。
　　#include<stdio.h> 
int main() 
　{ int a[3][3],sum=0; 
int i,j; 
　printf("enter data:\n"); 
　for (i=0;i<3;i++) 
　　for (j=0;j<3;j++) 
　　　　scanf("%d",&a[i][j]); 
　for (i=0;i<3;i++) 
　　sum=sum+a[i][i]; 
　printf("sum=%6d\n",sum); 
　return 0; 
} 
运行结果： 
　　enter data: 
1 ↙ 
2 ↙ 
3 ↙ 
4 ↙ 
5 ↙ 
6 ↙ 
7 ↙ 
8 ↙ 
9 ↙ 
sum=　　15 
关于输入数据方式的讨论： 
在程序的ｓｃａｎｆ 语句中用％ｄ 作为输入格式控制，上面输入数据的方式显然是可行
的。其实也可以在一行中连续输入９ 个数据，如： 
　　1 2 3 4 5 6 7 8 9 ↙ 
结果也一样。在输入９ 个数据并按回车键后，这９ 个数据被送到内存中的输入缓冲区中， 
然后逐个送到各个数组元素中。下面的输入方式也是正确的： 
　　1 2 3 ↙ 
4 5 6 ↙ 
7 8 9 ↙ 
或者：

　４６ 
　　1 2 ↙ 
3 4 5 6 ↙ 
7 8 9 ↙ 
都是可以的。
请考虑，如果将程序第７ ～ ９ 行改为
　　for (j=0;j<3;j++) 
　scanf(" %d %d %d",&a[0][j],&a[1][j],&a[2][j]); 
应如何输入？ 是否必须一行输入３ 个数据，如： 
　　1 2 3 ↙ 
4 5 6 ↙ 
7 8 9 ↙ 
答案是可以按此方式输入，也可以不按此方式输入，而采用前面介绍的方式输入，不论分
多少行、每行包括几个数据，只要求最后输入９ 个数据即可。
程序中用的是整型数组，运行结果是正确的。如果用的是实型数组，只须将程序第４ 
行的ｉｎｔ 改为ｆｌｏａｔ 或ｄｏｕｂｌｅ 即可，并且在ｓｃａｎｆ 函数中使用％ｆ 或％ｌｆ 格式声明。
５．４　已有一个已排好序的数组，要求输入一个数后，按原来排序的规律将它插入数
组中。
解： 解题思路。设数组ａ 有ｎ 个元素，而且已按升序排列，在插入一个数时按下面的
方法处理： 
（１） 如果插入的数ｎｕｍ 比ａ 数组最后一个数大，则将插入的数放在ａ 数组末尾。
（２） 如果插入的数ｎｕｍ 不比ａ 数组最后一个数大，则将它依次和ａ［０］ ～ ａ［ｎ－１］ 比
较，直到出现ａ［ｉ］ ＞ｎｕｍ 为止，这时表示ａ［０］ ～ ａ［ｉ －１］各元素的值比ｎｕｍ 小，ａ［ｉ］ ～ 
ａ［ｎ－１］ 各元素的值比ｎｕｍ 大。ｎｕｍ 理应插到ａ［ｉ－１］ 之后、ａ［ｉ］之前。怎样才能实现此
目的呢？ 将ａ［ｉ］～ ａ［ｎ－１］ 各元素向后移一个位置（即ａ［ｉ］变成ａ［ｉ＋１］，…，ａ［ｎ－１］变成
ａ［ｎ］）。然后将ｎｕｍ 放在ａ［ｉ］中。Ｎ.Ｓ 图见图５.３。
显示初始数组
输入待插入的数值ｎｕｍ 
　　　ｎｕｍ＞末尾元素
　Ｔ Ｆ　
ｎｕｍ 
插在数
组尾
ｆｏｒ （ｉ ＝ ０； ｉ＜１０； ｉ＋＋） 
　　　ａ （ｉ）＞ｎｕｍ 
　Ｔ Ｆ 
ｎｕｍ 插在ａ（ｉ）处
将原第ｉ 个元素之后的
所有元素下标依次增１ 
输出结果
图　５.３

　４７ 
　　编写程序如下。
　　#include<stdio.h> 
int main() 
　{ int a[11]={1,4,6,9,13,16,19,28,40,100}; 
　int temp1,temp2,number,end,i,j; 
　printf("array a:\n"); 
　for (i=0;i<10;i++) 
　　printf("%5d",a[i]); 
　printf("\n"); 
　printf("insert data:"); 
　scanf("%d",&number); 
　end=a[9]; 
　if (number>end) 
　　a[10]=number; 
　else 
　{for (i=0;i<10;i++) 
　　{if (a[i]>number) 
　　　{temp1=a[i]; 
　　　　a[i]=number; 
　　　　for (j=i+1;j<11;j++) 
　　　　　{temp2=a[j]; 
a[j]=temp1; 
temp1=temp2; 
　　　　　} 
　　　　　break; 
　　　} 
　　} 
　} 
　printf("Now, array a:\n"); 
　for (i=0;i<11;i++) 
　　printf("%5d",a[i]); 
　printf("\n"); 
　return 0; 
} 
运行结果： 
　　array a: 
　　1　　4　　6　　9　13　16　19　28　40　100 
insert data: 5 ↙ 
Now,array a: 
　　1　　4　　5　　6　　9　13　16　19　28　40　100

　４８ 
　　５．５　将一个数组中的值按逆序重新存放。例如，原来顺序为８，６，５，４，１，要求改为
１，４，５，６，８。
解： 解题思路。以中间的元素为中心，将其两侧对称的元素的值互换。例如，将８ 和
１ 互换，将６ 和４ 互换。Ｎ.Ｓ 图见图５. ４。
显示初始数组元素
ｆｏｒ （ｉ ＝ ０； ｉ＜Ｎ ／ ２； ｉ＋＋） 
第ｉ 个元素与第Ｎ－ｉ－１ 个元素互换
显示逆序存放的各数组元素
图　５. ４ 
编写程序如下。
　　#include<stdio.h> 
#define N 5　　　　　　　　　　//定义N 代表5 
int main() 
　{ int a[N],i,temp; 
　printf("enter array a:\n"); 
　for (i=0;i<N;i++) 
　　scanf("%d",&a[i]); 
　printf("array a:\n"); 
　for (i=0;i<N;i++) 
　　printf("%4d",a[i]); 
　for (i=0;i<N/2;i++)　　　　//　循　环的作用是将对称的元素的值互换
　　{ temp=a[i]; 
　　　a[i]=a[N-i-1]; 
　　　a[N-i-1]=temp; 
　　} 
　printf("\nNow,array a:\n"); 
　for (i=0;i<N;i++) 
　　printf("%4d",a[i]); 
　printf("\n"); 
　return 0; 
} 
运行结果： 
　　enter array a: 
8 6 5 4 1 ↙ 
array a: 
　　8　　6　　5　　4　　1 
Now, array a: 
　　1　　4　　5　　6　　8

　４９ 
　　５．６　输出以下的杨辉三角形（要求输出１０ 行）。
　　11
　1 
1　2　1 
1　3　3　1 
1　4　6　4　1 
1　5　10　10　5　1 
.
解： 解题思路。杨辉三角形是（ａ＋ｂ）ｎ 展开后各项的系数。例如： 
（ａ＋ｂ）０ 展开后为１　　　　　　　　　　　　　　　系数为１ 
（ａ＋ｂ）１ 展开后为ａ＋ｂ　　　　　　　　　　　　系数为１， １ 
（ａ＋ｂ）２ 展开后为ａ２ ＋２ａｂ＋ｂ２ 　　　　　　　　　系数为１， ２， １ 
（ａ＋ｂ）３ 展开后为ａ３ ＋３ａ２ ｂ＋３ａｂ２ ＋ｂ３ 　　　　　　系数为１， ３， ３， １ 
（ａ＋ｂ）４ 展开后为ａ４ ＋４ａ３ ｂ＋６ａ２ ｂ２ ＋４ａｂ３ ＋ｂ４ 系数为１， ４， ６， ４， １ 
以上就是杨辉三角形的前５ 行。杨辉三角形各行的系数有以下的规律： 
（１） 各行第一个数都是１。
（２） 各行最后一个数都是１。
（３） 从第３ 行起，除上面指出的第一个数和最后一个数外，其余各数是上一行同列和
前一列两个数之和。例如，第４ 行第２ 个数（３）是第３ 行第２ 个数（２）和第３ 行第１ 个数
（１）之和。可以这样表示： ａ［ｉ］［ｊ］ ＝ ａ［ｉ－１］［ｊ］＋ａ［ｉ－１］［ｊ－１］，其中，ｉ 为行数，ｊ 为列数。
编写程序如下。
　　#include<stdio.h> 
#define N　10 
int main() 
　{ int i,j,a[N][N];　　　　　　　　　　　//数组为10 行10 列
　for (i=0;i<N;i++) 
　　　　{a[i][i]=1;　　　　　　　　　//使对角线元素的值为1 
　　　　　a[i][0]=1;　　　　　　　　　//使第1 列元素的值为1 
　　　　} 
　for (i=2;i<N;i++)　　　　　　　　//从第3 行开始处理
　　for (j=1;j<=i-1;j++) 
　　　a[i][j]=a[i-1][j-1]+a[i-1][j]; 
　for (i=0;i<N;i++) 
　　{for (j=0;j<=i;j++) 
　　　printf("%6d",a[i][j]);　　//输出数组各元素的值
　　printf("\n"); 
　　} 
　printf("\n"); 
　return 0; 
}

　５０ 
说明： 数组元素的序号是从０ 开始算的，因此数组中０ 行０ 列的元素实际上就是
杨辉三角形中第１ 行第１ 列的数据，以此类推。
运行结果： 
　　11
　　1 
1　　2　　1 
1　　3　　3　　1　　
1　　4　　6　　4　　1 
1　　5　　10　　10　　5　　1 
1　　6　　15　　20　　15　　6　　1 
1　　7　　21　　35　　35　　21　　7　　1 
1　　8　　28　　56　　70　　56　　28　　8　　1 
1　　9　　36　　84　126　126　　84　　36　　9　　1 
５．７　输出“魔方阵”。所谓魔方阵是指这样的方阵，它的每一行、每一列和对角线之
和均相等。例如，三阶魔方阵为
８　１　６ 
３　５　７ 
４　９　２ 
要求输出由１ ～ ｎ２ 的自然数构成的魔方阵。
解： 解题思路。魔方阵的阶数ｎ 应为奇数。要将１ ～ ｎ２ 的自然数构成魔方阵，可按以
下规律处理： 
（１） 将１ 放在第１ 行中间一列。
（２） 从２ 开始直到ｎ×ｎ，各数依次按下列规则存放： 每一个数存放的行比前一个数的
行数减１，列数加１（例如上面的三阶魔方阵，５ 在４ 的上一行后一列）。
（３） 如果上一数的行数为１，则下一个数的行数为ｎ（指最下一行）。例如，１ 在第１ 
行，则２ 应放在最下一行，列数同样加１。
（４） 当上一个数的列数为ｎ 时，下一个数的列数应为１，行数减１。例如，２ 在第３ 行
最后一列，则３ 应放在第２ 行第１ 列。
（５） 如果按上面规则确定的位置上已有数，或上一个数是第１ 行第ｎ 列时，则把下一
个数放在上一个数的下面。例如，按上面的规定，４ 应该放在第１ 行第２ 列，但该位置已
被１ 占据，所以４ 就放在３ 的下面。由于６ 是第１ 行第３ 列（即最后一列），故７ 放在６ 
下面。
按此方法可以得到任何阶的魔方阵。
Ｎ.Ｓ 图见图５.５。

　５１ 
输入魔方阵的阶数ｎ 
使ａ 数组的所有元素为０ 
将１ 放在第１ 行中间一列上
ｆｏｒ （ｋ ＝ ２； ｋ＜ ＝ ｎ.ｎ； ｋ＋＋） 
ｉ ＝ ｉ－１， ｊ ＝ ｊ＋１ 
　　　上一个数在第１ 行、第ｎ 列
　Ｔ Ｆ　　
ｉ ＝ ｉ＋２ 
ｊ ＝ ｊ－１ 
上一个数在第１ 行
　　Ｔ Ｆ　　
ｉ ＝ ｎ 
上一个数在第ｎ 列
　　Ｔ Ｆ　　
ｊ ＝ １
ａ ［ｉ］［ｊ］未填数
　　Ｔ Ｆ　　
ａ［ｉ］［ｊ］ ＝ ｋ ｉ ＝ ｉ＋２ 
ｊ ＝ ｊ－１ 
ａ［ｉ］［ｊ］ ＝ ｋ 
输出魔方阵ａ［ｎ］［ｎ］ 
图　５.５ 
编写程序如下。
　　#include<stdio.h> 
int main() 
　{ int a[15][15],i,j,k,p,n; 
　p=1; 
　while(p= =1) 
　　{printf("enter n(n=1 to 15):");　　　　//要求阶数为1~15 的奇数
　　scanf("%d",&n); 
　　if ((n!=0) && (n<=15) && (n%2!=0))　//检查n 是否为1~15 的奇数
　　　　p=0; 
　　} 
　//初始化　
　for (i=1;i<=n;i++) 
　　for (j=1;j<=n;j++) 
　　　　a[i][j]=0; 
　//建立魔方阵　
　j=n/2+1; 
　a[1][j]=1; 
　for (k=2;k<=n.n;k++) 
　　{i=i-1; 
　　j=j+1; 
　　if ((i<1) && (j>n)) 
　　　{i=i+2;