第七章课下解程题

1、第六章 数组6.1 用筛选法求100之内的素数解：所谓“筛法”指的是“埃拉托色尼筛法”。埃拉托色尼是古希腊的著名数学家。他采取的方法是，在一张纸上写上1到1000的全部整数，然后逐个判断它们是否素数，找出一个非素数，找出一个非素数，就把它挖掉，最后剩下的就是素数。具体做法如下：（1）先将1挖掉（因为1不是素数）（2）用2去除它后面的各个数，把能被2整除的数挖掉，即把2的倍数挖掉。（3）用3去除它后面各数，把3的倍数挖掉。（4）分别用4、5各数作为除数去除这些数以后的各数。这个过程一直进行到在除数后面的数已全被挖掉为止。例如在150之间的素数，要一直进行到除数为47为止。事实上，可以简化，如果需

2、要找1n范围内的素数表，只需进行到除数为（取其整数）即可。例如对150，只需进行到将7作为除数即可。上面的算法可表示为：（1）挖去1（2）用下一个未被挖去的数p去除p后面各数，把p的倍数挖掉；（3）检查p是否小于的整数部分（如果n=1000，则检查p31?），如果是，则返回（2）继续执行，否则就结束；（4）剩下的数就是素数。用计算机解此题，可以定义一个数组a，a1an分别代表1n这n 个数。如果检查出数组a的某一元素的值是非素数，就使它变为0，最后剩下不为0的就是素数。程序如下：#include#includeint main()int i,j,n,a101;for(i=1;i=100;i+)

3、 /a0不用，只用a1到a100ai=i; /使a1到a100的值为1到100a1=0; /先“挖掉”a1for(i=2;isqrt(100);i+)for(j=i+1;j=100;j+)if(ai!=0&aj!=0) if(aj%ai=0)aj=0; /把非素数“挖掉”printf(n);for(i=1,n=0;i=100;i+)if(ai!=0) /选出值不为0的数组元素，即素数 printf(%5d,ai); n+; /累计本行已输出的数据个数 if(n=10) printf(n); n=0; printf(n); return 0;6.2用选择法对10个整数排序（从小到大）解：选择排序

4、的思路：设有10个元素a1a10，将a1与a2a10比较，若a1比a2a10都小，则不进行交换，即无任何操作。若a2a10中有一个以上比a1小，则将其中最小的一个（假如为ai）与a1交换，此时a1中存放了10个中最小的数。第二轮将a2与a3a10比较，将剩下9个数中的最小者ai与a2对换，此时a2中存放的是10个中第二小的数。依此类推，共进行9轮比较，a1a10就已按由小到大的顺序存放了。程序如下：#includeint main()int i,j,min,temp,a11;printf(enter data:n);for(i=1;i=10;i+)printf(a%d=,i);scanf(%d

5、,&ai);printf(n);printf(the orginal numbers:n);for(i=1;i=10;i+)printf(%5d,ai);printf(n);for(i=1;i=9;i+) /以下8行是对10个数排序min=i;for(j=i+1;jaj) min=j;temp=ai;ai=amin;amin=temp; /将ai+110中最小者与ai对换printf(nthe sorted numbers:n);for(i=1;inum为止，这时表示a0到ai-1各元素的值比num小，ai到an-1各元素的值比num大。num理应插到ai-1之后，ai之前。怎样才能实现此目的

6、呢？将ai到an-1各元素向后移一个位置（即ai变成ai+1，an-1变成an）。然后将num放在ai中。程序如下：#includeint main()int a11=1,4,5,9,13,16,19,28,40,100;int num,i,j;for(i=0;ia9)a10=num;elsefor(i=0;inum)for(j=9;j=i;j-) aj+1=aj; ai=num; break;for(i=0;i11;i+)printf(%5d,ai);printf(n);return 0;6.5将一个数组中的值按逆序重新存放，例如原来的顺序为：8，6，5，4，1。要求改为：1，4，5，6，8

7、。解：以中间的元素为中心，将其两侧对称的元素的值互换即可。程序如下：#include#define N 5int main()int aN,i,temp;printf(enter array a:n);for(i=0;iN;i+)scanf(%d,&ai);printf(array a:n);for(i=0;iN;i+)printf(%4d,ai);for(i=0;iN/2;i+) /循环的作用是将对称的元素的值互换temp=ai;ai=aN-1-i; aN-1-i=temp;printf(nNow,array a:n);for(i=0;iN;i+)printf(%4d,ai);printf(

8、n);return 0;6.6输出杨辉三角形解：杨辉三角形是（a+b）n展开后各项的系数。例如：(a+b)0展开后为1 系数为1(a+b)1展开后为a+b 系数为1，1(a+b)2展开后为a2+2ab+b2 系数为1，2，1(a+b)3展开后为a3+3a2b+3ab2+b3 系数为1，3，3，1(a+b)4展开后为a4+4a3b+6a2b2+4ab3+b4 系数为1，4，6，4，1以上就是杨辉三角形的前5行。杨辉三角形各行的系数有以下的规律：（1）各行第一个数都是1（2）各行最后一个数都是1（3）从第3行起，除上面指出的第一个数和最后一个数外，其余各数是上一行同列和前一列两个数之和。例如：第4

9、行第2个数是第（3）是第3行第2个数（2）和第3行第1个数（1）之和。可以这样表示：aij=ai-1j+ai-1j-1，其中i为行数，j为列数。程序如下：#include#define N 11int main()int i,j,aNN; /数组为11行11列，0行0列不用for(i=1;iN;i+)ai1=1; /使第1列元素的值为1aii=1; /使对角线元素的值为1for(i=3;iN;i+)for(j=2;j=i-1;j+)aij=ai-1j-1+ai-1j; /等于上一行同列和前一列两个数之和for(i=1;iN;i+)for(j=1;j=i;j+)printf(%6d,aij);p

10、rintf(n);printf(n); return 0;6.7输出魔方阵，所谓魔方阵是指这样的方阵，它的每一行、每一列和对角线之和均相等。例如：三阶魔方阵为8 1 63 5 74 9 2要求输出由1n2之间的自然数构成的魔方阵。解：魔方阵中各数的排列规律如下：（1）将1放在第一行中间一列。（2）从2开始直到nn止各数依次按下列规则存放：每一个数存放的行比前一个数的行数减1，列数加1（例如上面的三阶魔方阵，5在4的上一行后一列）。（3）如果上一数的行数为1，则下一个数的行数为n（指最下一行）。例如，1在第1行，则2应放在最下一行，列数同样加1。（4）当上一个数的列数为n时，下一个数的列数应为1

11、，行数减1。例如，2在第3行最后一列，则3应放在第2行第1列。（5）如果按上面规则确定的位置上已有数，或上一个数是第1行第n列时，则把下一个数放在上一个数的下面。例如，按上面的规定，4应该放在第1行第2列，但该位置已被1占据，所以4就放在3的下面。由于6是第1行第3列（即最后一列），故7放在6下面。程序如下：#includeint main()int a1616,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)p=0;/初始化for(

12、i=1;i=n;i+)for(j=1;j=n;j+)aij=0;/建立魔方阵j=n/2+1;a1j=1;for(k=2;k=n*n;k+)i=i-1;j=j+1;if(in) /i为行，j为列i=i+2;j=j-1;elseif(in)j=1;if(aij=0) aij=k;elsei=i+2;j=j-1;aij=k;/输出魔方阵for(i=1;i=n;i+)for(j=1;j=n;j+) printf(%5d,aij); printf(n); return 0;6.8 找出一个二维数组中的鞍点，即该位置上的元素在该行上最大，在该列上最小。也可能没有鞍点。解：一个二维数组最多有一个鞍点，也可能

13、没有。解题思路：先找出一行中值最大的元素，然后检查它是否该列中的最小值，如果是，则是鞍点（不需要再找别的鞍点了），输出该鞍点；如果不是，则再找下一行的最大数如果每一行的最大数都不是鞍点，则此数组无鞍点。程序如下：#include#define N 4#define M 5int main()int i,j,k,aNM,max,maxj,flag;for(i=0;iN;i+)for(j=0;jM;j+)scanf(%d,&aij);for(i=0;iN;i+)max=ai0; /开始时假设ai0最大maxj=0; /将列号0赋给maxj保存for(j=0;jmax) max=aij; /将本行的

14、最大数存放在max中 maxj=j; /将最大数所在的列号存放在maxj中 flag=1; /先假设是鞍点,以flag为1为代表 for(k=0;kakmaxj) /将最大数和其同列元素相比 flag=0; /如果max不是同列最小,表示不是鞍点,令flag1为0 continue; if(flag) /如果flag1为1表示是鞍点printf(a%d%d=%dn,i,maxj,max); /输出鞍点的值和所在的行、列号 break;if(!flag) /如果flag为0表示鞍点不存在printf(it is not exist!n);return 0;6.9 有15个数按从大到小的顺序存放在

15、一个数组中。输入一个数，要求用折半查找法找出该数是数组中第几个元素的值。如果该数不在数组中，输出“不在表中”。解：从表列中查一个数最简单的方法是从第1个数开始顺序查找，将要找的数与表列中的数一一比较，直到找到为止（如果表列中无此数，则应找到最后一个数，然后判定“找不到”）但这种“顺序查找法”效率低，如果表列中有1000个数，且要找的数恰恰是第1000个数，则要进行999次比较才能得到结果。平均比较次数为500次。折半查找法是效率较高的一种方法。基本思路如下：假如有已按由小到大排好序的9个数，a1a9，其值分别为：1，3，5，7，9，11，13，15，17若输入一个数3，想查3是否在此数列中，先

16、找出表列中居中的数，即a5，将要找的数3与a5比较，a53，显然3应当在a1到a5范围内，而不会在a6到a9范围内。这样就可以缩小查找范围，甩掉a6到a9这一部分，即将查找范围缩小为一半。再找a1到a5范围内的居中的数，即a3，将要找的数3与a3比较，a3的值是5，发现a33，显然3应当在a1到a3范围内。这样又将查找范围缩小一半。再将3与a1到a3范围内的居中的数a2比较，发现要找的数3等于a2，查找结束。一共比较了3次。如果表列中有n个数，则最多比较的次数为int(log2n)+1。程序如下：#include#define N 15int main()int i,number,top,bo

17、tt,mid,loca,aN,flag=1,sign;char c;printf(enter data:n);scanf(%d,&a0); /输入第一个数i=1;while(i=ai-1) /如果输入的数不小于前一个数i+; /使数的序号加1elseprintf(enter this data again:n);/要求重新输入此数for(i=0;iN;i+)printf(%d,ai); /输出全部15个数while(flag)printf(input number to look for:); /问你要查找哪个数scanf(%d,&number); /输入要查找的数sign=0; /sign为

18、0表示尚未找到top=0; /top是查找区间的起始位置bott=N-1; /bott是查找区间的最末位置if(numberaN-1) /要查的数不在查找区间内loca=-1; /表示要查找的数不在正常范围内while(!sign)&(top=bott)mid=(bott+top)/2; /找出中间元素的下标if(number=amid) /如果要查找的数正好等于中间元素loca=mid; /记下该下标printf(has found %d,its position is %dn,number,loca+1);/由于下标从0算起，而人们习惯从1算起，因此输出数的位置要加1sign=1; /表示

19、找到了else if(numberamid) /如果要查找的数小于中间元素的值bott=mid-1; /只需从下标为0到mid-1的范围中找else /如果要查找的数不小于中间元素的值top=mid+1; /只需从下标为mid+1到bott的范围中找if(!sign|loca=-1) /sign为0或loca等于-1，意味着找不到printf(can not find %d.n,number);printf(continue or not(Y/N)?); /问你是否继续查找scanf(%c,&c); /不想继续查找输入N或nif(c=N|c=n)flag=0; /flag为开关变量，控制程序是

20、否结束运行return 0;6.10 有一篇文章，共有3行文字，每行有80个字符。要求分别统计出其中英文大写字母、小写字母、数字、空格以及其他字符的个数。#includeint main()int i,j,upp,low,dig,spa,oth;char text380;upp=low=dig=spa=oth=0;for(i=0;i3;i+)gets(texti);for(j=0;j=A&textij=a&textij=0&textij=9)dig+;else if(textij= )spa+;elseoth+;printf(nupper case:%dn,upp);printf(lower case:%dn,low);printf(digit :%dn,dig);printf(space :%dn,spa);printf(other :%dn,oth);return 0;6.13 编一程序，将两个字符串连接起来，不要用strcat函数。程序如下：#includeint main()char s180,s240;int i=0,j=0;scanf(%s,s1);scanf(%s,s2);while(s1i!=0)i+;while(s2j!=0)s1i+=s2j+;s1i=0;printf(the new string is:%sn,