中国高等院校计算机基础教育课程体系规划教材C程序设计教程(第3版)学习辅导/谭浩强

第5章 利用数组处理批量数据 5.1用筛选法求100之内的素数。 解: 解题思路: 所谓“筛法”指的是“埃拉托色尼(Eratosthenes)筛法”。埃拉托色尼是古希腊的著名数学家。他采取的方法是，在一张纸上写上1～1000的全部整数，然后逐个判断它们是否是素数，找出一个非素数，就把它挖掉，*后剩下的就是素数，见图51。① ２ ３ ④ ５ ⑥ ７ ⑧ ⑨ ⑩ １１ 13 17 19 23 29 31 37 41 43 47 … 图51 具体做法如下: (1) 先将1挖掉(因为1不是素数)。 (2) 用2去除它后面的各个数，把能被2整除的数挖掉，即把2的倍数挖掉。 (3) 用3去除它后面各数，把3的倍数挖掉。 (4) 分别用4，5…各数作为除数去除这些数以后的各数。这个过程一直进行到在除数后面的数已全被挖掉为止。例如在图51中找1～50的素数，要一直进行到除数为47为止。事实上，可以简化，如果需要找1～n范围内的素数表，只须进行到除数为n(取其整数) 即可。例如对1～50，只须进行到将7(即50的整数部分)作为除数即可。请读者思考为什么? 上面的算法可表示如下: (1) 挖去1； (2) 用下一个未被挖去的数 p去除p后面各数，把p的倍数挖掉； (3) 检查p是否小于n的整数部分(如果n=1000，则检查p＜31?)，如果是，则返回(2)继续执行，否则就结束； (4) 剩下的数就是素数。 用计算机解此题，可以定义一个数组 a。数组元素a\[1\]～a\[n\] 分别代表1～n这n个数。如果检查出数组a的某一元素的值是非素数，就使它变为0，*后剩下不为0的就是素数。 编写程序如下:#include #include//程序中用到求平方根函数sqrt int main() { int i,j,n,a\[101\];//定义a数组包含101个元素 for (i=1;i a\[i\]=i; //使a\[1\]~a\[100\] 的值为1到100 a\[1\]=0; //先"挖掉"a\[1\] for (i=2;i for (j=i+1;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 {if (a\[i\]!=0)//选出值不为0的数组元素,即素数 {printf("%5d",a\[i\]);//输出素数,宽度为5列 n++; //累计本行已输出的数据个数 } if(n==10) { printf("\\n"); n=0; } } printf("\\n"); return 0; }运行结果:2357111317192329 31374143475359616771 737838997 输入数组a各元素for (i=1; i≤9; i++)min=ifor (j=i+1; j≤10; j++)a ［min］＞a［j］ TFmin=j交换a［min］与a［i］输出已排序的10个数图525.2用选择法对10个整数排序。 解: 解题思路: 选择法的思路如下: 设有10个元素a\[1\]～a\[10\], 将a\[1\] 与a\[2\]～a\[10\]比较，若a\[1\]比a\[2\]～a\[10\]都小，则不进行交换，即无任何操作。若a\[2\]～a\[10\]中有一个以上比a\[1\] 小，则将其中*大的一个(假设为a\[i\]) 与a\[1\] 交换，此时a\[1\]中存放了10个数中*小的数。第2轮将a\[2\]与a\[3\]～a\[10\]比较，将剩下9个数中的*小者a\[i\]与a\[2\]对换，此时a\[2\]中存放的是10个中第二小的数。依此类推，共进行9轮比较，a\[1\]～a\[10\] 就已按由小到大的顺序存放了。NS图如图52所示。 编写程序如下:#include int main() { int i,j,min,temp,a\[11\]; printf("enter data:\\n"); for (i=1;i {printf("a\[%d\]=",i); scanf("%d",&a\[i\]);//输入10个数 } printf("\\n"); printf("The orginal numbers:\\n"); for (i=1;i printf("%5d",a\[i\]);//输出这10个数 printf("\\n"); for (i=1;i {min=i; for (j=i+1;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 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 165 98 23119 18 75 65 81 The sorted numbers: 15 16 18 23 65 75 81 98119 5.3求一个3×3的整型二维数组对角线元素之和。 解: 编写程序如下:#include int main() { int a\[3\]\[3\],sum=0; int i,j; printf("enter data:\\n"); for (i=0;i for (j=0;j scanf("%d",&a\[i\]\[j\]); for (i=0;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关于输入数据方式的讨论: 在程序的scanf语句中用%d作为输入格式控制，上面输入数据的方式显然是可行的。其实也可以在一行中连续输入9个数据，如:1 2 3 4 5 6 7 8 9↙结果也一样。在输入完9个数据并按回车键后，这9个数据被送到内存中的输入缓冲区中，然后逐个送到各个数组元素中。下面的输入方式也是正确的:1 2 3↙ 4 5 6↙ 7 8 9↙或者:1 2↙ 3 4 5 6↙ 7 8 9↙都是可以的。 请考虑，如果将程序第7～9行改为for (j=0;j scanf(" %d %d %d",&a\[0\]\[j\],&a\[1\]\[j\],&a\[2\]\[j\]);应如何输入？是否必须一行输入3个数据，如:1 2 3↙ 4 5 6↙ 7 8 9↙答案是可以按此方式输入，也可以不按此方式输入，而采用前面介绍的方式输入，不论分多少行、每行包括几个数据，只要求*后输入完9个数据即可。 程序中用的是整型数组，运行结果是正确的。如果用的是实型数组，只须将程序第4行的int改为float或double即可，并且在scanf函数中使用%f或%lf格式声明。 5.4已有一个已排好序的数组,要求输入一个数后，按原来排序的规律将它插入数组中。 解: 解题思路: 设数组a有n个元素，而且已按升序排列，在插入一个数时按下面的方法处理: (1) 如果插入的数num比a数组*后一个数大，则将插入的数放在a数组末尾。 (2) 如果插入的数num不比a数组*后一个数大，则将它依次和a\[0\]～a\[n-1\] 比较，直到出现a\[i\]>num为止，这时表示a\[0\]～a\[i-1\]各元素的值比num小，a\[i\]～a\[n-1\] 各元素的值比num大。num理应插到a\[i-1\] 之后、a\[i\]之前。怎样才能实现此目的呢？将a\[i\]～a\[n-1\] 各元素向后移一个位置(即a\[i\]变成a\[i+1\]，…,a\[n-1\]变成a\[n\])。然后将num放在a\[i\]中。NS图如图53所示。显示初始数组输入待插入的数值numnum＞末尾元素