第七章课下解程题

第六章数组6.1用筛选法求100之内的素数解：所谓“筛法”指的是“埃拉托色尼筛法”。埃拉托色尼是古希腊的著名数学家。他采取的方法是，在一张纸上写上1到1000的全部整数，然后逐个判断它们是否素数，找出一个非素数，找出一个非素数，就把它挖掉，最后剩下的就是素数。具体做法如下：（1）先将1挖掉（因为1不是素数）（2）用2去除它后面的各个数，把能被2整除的数挖掉，即把2的倍数挖掉。（3）用3去除它后面各数，把3的倍数挖掉。（4）分别用4、5…各数作为除数去除这些数以后的各数。这个过程一直进行到在除数后面的数已全被挖掉为止。例如在1~50之间的素数，要一直进行到除数为47为止。事实上，可以简化，如果需要找1~n范围内的素数表，只需进行到除数为n（取其整数）即可。例如对1~50，只需进行到将7作为除数即可。上面的算法可表示为：（1）挖去1（2）用下一个未被挖去的数p去除p后面各数，把p的倍数挖掉；（3）检查p是否小于n的整数部分（如果n=1000，则检查p31?），如果是，则返回（2）继续执行，否则就结束；（4）剩下的数就是素数。用计算机解此题，可以定义一个数组a，a[1]~a[n]分别代表1~n这n个数。如果检查出数组a的某一元素的值是非素数，就使它变为0，最后剩下不为0的就是素数。程序如下：#includestdio.h#includemath.hintmain(){inti,j,n,a[101];for(i=1;i=100;i++)//a[0]不用，只用a[1]到a[100]a[i]=i;//使a[1]到a[100]的值为1到100a[1]=0;//先“挖掉”a[1]for(i=2;isqrt(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=1,n=0;i=100;i++){if(a[i]!=0)//选出值不为0的数组元素，即素数{printf(%5d,a[i]);n++;}//累计本行已输出的数据个数if(n==10){printf(\n);n=0;}}printf(\n);return0;}6.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个中最小的数。第二轮将a[2]与a[3]~a[10]比较，将剩下9个数中的最小者a[i]与a[2]对换，此时a[2]中存放的是10个中第二小的数。依此类推，共进行9轮比较，a[1]~a[10]就已按由小到大的顺序存放了。程序如下：#includestdio.hintmain(){inti,j,min,temp,a[11];printf(enterdata:\n);for(i=1;i=10;i++){printf(a[%d]=,i);scanf(%d,&a[i]);}printf(\n);printf(theorginalnumbers:\n);for(i=1;i=10;i++)printf(%5d,a[i]);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];a[i]=a[min];a[min]=temp;//将a[i+1]~[10]中最小者与a[i]对换}printf(\nthesortednumbers:\n);for(i=1;i=10;i++)printf(%5d,a[i]);printf(\n);return0;}6.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]中。程序如下：#includestdio.hintmain(){inta[11]={1,4,5,9,13,16,19,28,40,100};intnum,i,j;for(i=0;i10;i++)printf(%5d,a[i]);printf(\n);scanf(%d,&num);if(numa[9])a[10]=num;else{for(i=0;i10;i++)if(a[i]num){for(j=9;j=i;j--)a[j+1]=a[j];a[i]=num;break;}}for(i=0;i11;i++)printf(%5d,a[i]);printf(\n);return0;}6.5将一个数组中的值按逆序重新存放，例如原来的顺序为：8，6，5，4，1。要求改为：1，4，5，6，8。解：以中间的元素为中心，将其两侧对称的元素的值互换即可。程序如下：#includestdio.h#defineN5intmain(){inta[N],i,temp;printf(enterarraya:\n);for(i=0;iN;i++)scanf(%d,&a[i]);printf(arraya:\n);for(i=0;iN;i++)printf(%4d,a[i]);for(i=0;iN/2;i++)//循环的作用是将对称的元素的值互换{temp=a[i];a[i]=a[N-1-i];a[N-1-i]=temp;}printf(\nNow,arraya:\n);for(i=0;iN;i++)printf(%4d,a[i]);printf(\n);return0;}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行第2个数是第（3）是第3行第2个数（2）和第3行第1个数（1）之和。可以这样表示：a[i][j]=a[i-1][j]+a[i-1][j-1]，其中i为行数，j为列数。程序如下：#includestdio.h#defineN11intmain(){inti,j,a[N][N];//数组为11行11列，0行0列不用for(i=1;iN;i++){a[i][1]=1;//使第1列元素的值为1a[i][i]=1;//使对角线元素的值为1}for(i=3;iN;i++)for(j=2;j=i-1;j++)a[i][j]=a[i-1][j-1]+a[i-1][j];//等于上一行同列和前一列两个数之和for(i=1;iN;i++){for(j=1;j=i;j++)printf(%6d,a[i][j]);printf(\n);}printf(\n);return0;}6.7输出魔方阵，所谓魔方阵是指这样的方阵，它的每一行、每一列和对角线之和均相等。例如：三阶魔方阵为816357492要求输出由1~n2之间的自然数构成的魔方阵。解：魔方阵中各数的排列规律如下：（1）将1放在第一行中间一列。（2）从2开始直到n×n止各数依次按下列规则存放：每一个数存放的行比前一个数的行数减1，列数加1（例如上面的三阶魔方阵，5在4的上一行后一列）。（3）如果上一数的行数为1，则下一个数的行数为n（指最下一行）。例如，1在第1行，则2应放在最下一行，列数同样加1。（4）当上一个数的列数为n时，下一个数的列数应为1，行数减1。例如，2在第3行最后一列，则3应放在第2行第1列。（5）如果按上面规则确定的位置上已有数，或上一个数是第1行第n列时，则把下一个数放在上一个数的下面。例如，按上面的规定，4应该放在第1行第2列，但该位置已被1占据，所以4就放在3的下面。由于6是第1行第3列（即最后一列），故7放在6下面。程序如下：#includestdio.hintmain(){inta[16][16],i,j,k,p,n;p=1;while(p==1){printf(entern(n=1to15):);//要求阶数为1至15之间的奇数scanf(%d,&n);if((n!=0)&&(n=15)&&(n%2!=0))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((i1)&&(jn))//i为行，j为列{i=i+2;j=j-1;}else{if(i1)i=n;if(jn)j=1;}if(a[i][j]==0)a[i][j]=k;else{i=i+2;j=j-1;a[i][j]=k;}}//输出魔方阵for(i=1;i=n;i++){for(j=1;j=n;j++)printf(%5d,a[i][j]);printf(\n);}return0;}6.8找出一个二维数组中的鞍点，即该位置上的元素在该行上最大，在该列上最小。也可能没有鞍点。解：一个二维数组最多有一个鞍点，也可能没有。解题思路：先找出一行中值最大的元素，然后检查它是否该列中的最小值，如果是，则是鞍点（不需要再找别的鞍点了），输出该鞍点；如果不是，则再找下一行的最大数……如果每一行的最大数都不是鞍点，则此数组无鞍点。程序如下：#includestdio.h#defineN4#defineM5intmain(){inti,j,k,a[N][M],max,maxj,flag;for(i=0;iN;i++)for(j=0;jM;j++)scanf(%d,&a[i][j]);for(i=0;iN;i++){max=a[i][0];//开始时假设a[i][0]最大maxj=0;//将列号0赋给maxj保存for(j=0;jM;j++)//找出第i行中的最大数if(a[i][j]max){max=a[i][j];//将本行的最大数存放在max中maxj=j;//将最大数所在的列号存放在maxj中}flag=1;//先假设是鞍点,以flag为1为代表for(k=0;kN;k++)if(maxa[k][maxj])//将最大数和其同列元素相比{flag=0;//如果max不是同列最小,表示不是鞍点,令flag1为0continue;}if(flag)//如果flag1为1表示是鞍点{printf(a[%d][%d]=%d\n,i,maxj,max);//输出鞍点的值和所在的行、列号break;}}if(!flag)//如果flag为0表示鞍点不存在printf(itisnotexist!\n);return0;}6.9有15个数按从大到小的顺序存放在一个数组中。输入一个数，要求用折半查找法找