C+语言程序设计第十一讲.ppt

1 1、从任意、从任意、从任意、从任意n n个数中找出最大数和最小数，并将它们相互交换后个数中找出最大数和最小数，并将它们相互交换后个数中找出最大数和最小数，并将它们相互交换后个数中找出最大数和最小数，并将它们相互交换后输出。输出。输出。输出。2 2、将一个数组中的数循环左移。、将一个数组中的数循环左移。、将一个数组中的数循环左移。、将一个数组中的数循环左移。3 3、输入若干学生的成绩，计算平均分，并输出低于平均分的学、输入若干学生的成绩，计算平均分，并输出低于平均分的学、输入若干学生的成绩，计算平均分，并输出低于平均分的学、输入若干学生的成绩，计算平均分，并输出低于平均分的学生成绩。生成绩。生成绩。生成绩。4 4、从任意、从任意、从任意、从任意n n个数（允许有重复）中删除某一个数个数（允许有重复）中删除某一个数个数（允许有重复）中删除某一个数个数（允许有重复）中删除某一个数k k。5 5、输入整数、输入整数、输入整数、输入整数n n，将其各位数字取出后，重新组合成一个新的最，将其各位数字取出后，重新组合成一个新的最，将其各位数字取出后，重新组合成一个新的最，将其各位数字取出后，重新组合成一个新的最大的整数。大的整数。大的整数。大的整数。6 6、将一个数组中的数逆序重新存放后输出。、将一个数组中的数逆序重新存放后输出。、将一个数组中的数逆序重新存放后输出。、将一个数组中的数逆序重新存放后输出。作作 业业例例例例5 5：输入若干个正整数，以输入若干个正整数，以输入若干个正整数，以输入若干个正整数，以0 0或负数结束，将其中或负数结束，将其中或负数结束，将其中或负数结束，将其中个位不为个位不为个位不为个位不为0 0的数输出，并统计满足条件的数据个数。的数输出，并统计满足条件的数据个数。的数输出，并统计满足条件的数据个数。的数输出，并统计满足条件的数据个数。输入输入x n=0 count+for i=0 to n-1ai%10!=0T输出输出aiF x0an=xcount=0n+输入输入x#include void main()int a100,x,n,i,count;n=0;count=0;cinx;while(x0)an=x;n+;cinx;for(i=0;in;i+)if(ai%10!=0)coutai;count+;cout个数是：个数是：n;cinn;for(i=0;in;i+)for(i=0;iai;cinai;m=0;m=0;for(i=0;in;i+)for(i=0;in;i+)if(ai%5if(ai%5=0)0)bm=ai;bm=ai;m+;m+;for(i=0;im;i+)for(i=0;im;i+)coutbi;coutbi;输入输入nm=0 m+for i=0 to n-1ai%5=0Tbm=aiF for i=0 to n-1输入输入ai for i=0 to m-1输出输出bi基本思想：假设数组基本思想：假设数组基本思想：假设数组基本思想：假设数组a a已经按已经按已经按已经按由小到大由小到大由小到大由小到大的顺序排的顺序排的顺序排的顺序排好序，设三个变量好序，设三个变量好序，设三个变量好序，设三个变量low,highlow,high和和和和midmid分别代表首元素，分别代表首元素，分别代表首元素，分别代表首元素，最后一个元素以及中间元素的下标，初值分别为：最后一个元素以及中间元素的下标，初值分别为：最后一个元素以及中间元素的下标，初值分别为：最后一个元素以及中间元素的下标，初值分别为：low=0low=0、high=n-1high=n-1、mid=(low+high)/2mid=(low+high)/2。从中间元素。从中间元素。从中间元素。从中间元素开始查找，用开始查找，用开始查找，用开始查找，用x x和和和和amidamid比较，此时有三种情况：比较，此时有三种情况：比较，此时有三种情况：比较，此时有三种情况：1)1)若若若若x=amid x=amid，则查找成功；，则查找成功；，则查找成功；，则查找成功；2)2)若若若若x amid x amid x amid，则令，则令，则令，则令low=mid+1low=mid+1折半查找法折半查找法例：数组元素为：例：数组元素为：例：数组元素为：例：数组元素为：5,13,19,21,37,56,64,75,80,88,925,13,19,21,37,56,64,75,80,88,921.1.查找查找查找查找x=21 x=21 的情况的情况的情况的情况(1)low=0;high=10;mid=(0+10)/2=5(1)low=0;high=10;mid=(0+10)/2=5 5 13 19 21 37 56 64 75 80 88 92 5 13 19 21 37 56 64 75 80 88 92lowlowmidmidhighhigh因为因为因为因为amidxamidx，所以向左找，令，所以向左找，令，所以向左找，令，所以向左找，令high=mid-1=4high=mid-1=4(2)low=0;high=4;mid=(0+4)/2=2(2)low=0;high=4;mid=(0+4)/2=2 5 13 19 21 37 56 64 75 80 88 92 5 13 19 21 37 56 64 75 80 88 92lowlowmidmidhighhigh因为因为因为因为amidxamidx，所以向右找，令，所以向右找，令，所以向右找，令，所以向右找，令low=mid+1=3low=mid+1=3(3)low=3;high=4;mid=(3+4)/2=3(3)low=3;high=4;mid=(3+4)/2=3 5 13 19 21 37 56 64 75 80 88 92 5 13 19 21 37 56 64 75 80 88 92lowlowmidmidhighhigh因为因为因为因为amid=xamid=x，查找成功，所查元素的下标为，查找成功，所查元素的下标为，查找成功，所查元素的下标为，查找成功，所查元素的下标为midmid0 01 12 23 34 45 56 67 78 89 910100 01 12 23 34 45 56 67 78 89 910100 01 12 23 34 45 56 67 78 89 91010(1)low=0;high=10;mid=(0+10)/2=5(1)low=0;high=10;mid=(0+10)/2=5因为因为因为因为amidxamidx，所以向右找，令，所以向右找，令，所以向右找，令，所以向右找，令low=mid+1=6low=mid+1=6(2)low=6;high=10;mid=(6+10)/2=8(2)low=6;high=10;mid=(6+10)/2=8 5 13 19 21 37 56 64 75 80 88 92 5 13 19 21 37 56 64 75 80 88 92lowlowmidmidhighhigh因为因为因为因为amidxamidxamidx，所以向左找，令，所以向左找，令，所以向左找，令，所以向左找，令high=mid-1=8high=mid-1=82.2.查找查找查找查找x=85 x=85 的情况的情况的情况的情况 5 13 19 21 37 56 64 75 80 88 92 5 13 19 21 37 56 64 75 80 88 92lowlowmidmidhighhigh此时此时此时此时lowhighlowhigh，查找失败，查找失败，查找失败，查找失败0 01 12 23 34 45 56 67 78 89 910100 01 12 23 34 45 56 67 78 89 910100 01 12 23 34 45 56 67 78 89 91010#include#include void main()void main()int a100,i,n,x,low,high,mid;int a100,i,n,x,low,high,mid;cinn;cinn;for(i=0;in;i+)for(i=0;iai;cinai;cinx;cinx;low=0;low=0;high=n-1;high=n-1;while(while(low=highlow=high)mid=(low+high)/2;mid=(low+high)/2;if(x=amid)if(x=amid)break;break;else if(xamid)else if(xamid)high=mid-1;high=mid-1;elseelselow=mid+1;low=mid+1;if(if(x=amidx=amid)coutYES:mid;coutYES:mid;elseelsecoutNO;coutNO;#include#include void main()void main()int i,j,temp,n,a100;int i,j,temp,n,a100;cinn;cinn;for(i=0;in;i+)for(i=0;iai;cinai;for(i=0;in-1;i+)for(i=0;in-1;i+)for(j=i+1;jn;j+)for(j=i+1;jaj)if(aiaj)temp=ai;temp=ai;ai=aj;ai=aj;aj=temp;aj=temp;for(i=0;in;i+)for(i=0;in;i+)coutai;coutai;例：将任意例：将任意n个数由小到大排序。个数由小到大排序。排排 序序#include#include void main()void main()int i,j,n,temp,int i,j,n,temp,didi,a100;,a100;cinn;cinn;for(i=0;in;i+)for(i=0;iai;cinai;for(i=0;in-1;i+)for(i=0;in-1;i+)di=i;di=i;for(j=i+1;jn;j+)for(j=i+1;jaj)if(adiaj)di=j;di=j;if(i!=di)if(i!=di)temp=ai;temp=ai;ai=adi;ai=adi;adi=temp;adi=temp;for(i=0;in;i+)for(i=0;in;i+)coutai;coutaia1a0a1，则交换；然后比较第二个数与第三个则交换；然后比较第二个数与第三个则交换；然后比较第二个数与第三个则交换；然后比较第二个数与第三个数；依次类推，直至第数；依次类推，直至第数；依次类推，直至第数；依次类推，直至第n-1n-1个数和第个数和第个数和第个数和第n n个数比较为个数比较为个数比较为个数比较为止止止止第一趟冒泡排序，结果最大的数被安置在第一趟冒泡排序，结果最大的数被安置在第一趟冒泡排序，结果最大的数被安置在第一趟冒泡排序，结果最大的数被安置在最后一个元素位置上最后一个元素位置上最后一个元素位置上最后一个元素位置上;（2 2）对前）对前）对前）对前n-1n-1个数进行第二趟冒泡排序，结果使个数进行第二趟冒泡排序，结果使个数进行第二趟冒泡排序，结果使个数进行第二趟冒泡排序，结果使次大的数被安置在第次大的数被安置在第次大的数被安置在第次大的数被安置在第n-1n-1个元素位置个元素位置个元素位置个元素位置;（3 3）重复上述过程，共经过）重复上述过程，共经过）重复上述过程，共经过）重复上述过程，共经过n-1n-1趟冒泡排序后，趟冒泡排序后，趟冒泡排序后，趟冒泡排序后，排序结束。排序结束。排序结束。排序结束。相邻两数比较，大数相邻两数比较，大数 小数小数 3 38 84 42 21 13 38 84 42 21 13 38 84 42 21 13 34 48 82 21 13 34 42 28 81 13 34 42 21 18 8第第第第一一一一趟趟趟趟3 34 42 21 18 83 34 42 21 18 83 32 24 41 18 83 32 21 14 48 8第第第第二二二二趟趟趟趟3 32 21 14 48 82 23 31 14 48 82 21 13 34 48 8第第第第三三三三趟趟趟趟2 21 13 34 48 81 12 23 34 48 8第第第第四四四四趟趟趟趟a1 a2 a3 a4 a5 j=1 to 4 j=1 to 3 j=1 to 2 j=1 to 1由小到大排序由小到大排序#include#include void main()void main()int a100,n,i,j,temp;int a100,n,i,j,temp;scanf(%d,&n);scanf(%d,&n);for(i=1;i=n;i+)for(i=1;i=n;i+)scanf(%d,&ai);scanf(%d,&ai);for(i=1;in;i+)for(i=1;in;i+)for(j=1;j=n-i;j+)for(j=1;jaj+1)if(ajaj+1)temp=aj;temp=aj;aj=aj+1;aj=aj+1;aj+1=temp;aj+1=temp;for(i=1;i=n;i+)for(i=1;i=n;i+)printf(%5d,ai);printf(%5d,ai);1 13 34 49 98 85 52 23 35 52 24 46 67 76 62 21 1a0a0a1a1a2a2a3a30 01 12 23 3a00a00a01a01a02a02a03a03a10a10a11a11a12a12a13a13a20a20a21a21a22a22a23a23a30a30a31a31a32a32a33a33a二维数组的基本概念二维数组的基本概念类型名类型名 数组名数组名常量常量1 常量常量2;例如：例如：int a34;整型二维数组整型二维数组 名字为名字为a3 3行行行行a0a0 a0 a0 存储结构存储结构存储结构存储结构 逻辑结构逻辑结构逻辑结构逻辑结构a00数组数组a 定义定义定义定义4 4列列列列共共12个元素个元素 a0 a0 a0 a0 a1 a10 a1 a11 a1a12 a1a13 a2a20 a2a21 a2a22 a2a23是一个矩阵或一张表格是一个矩阵或一张表格第第0行行第第1行行第第2行行第第0列列 第第1列列 第第2列列 第第3列列a01a02a03a10a11a12a13a20a21a22a23按行存储按行存储按行存储按行存储a0a0a1a1a2a20 1 2 3一维数组个数一维数组个数一维数组中一维数组中元素的个数元素的个数分行初始化分行初始化例例 int a23=int a23=1,21,2,4 4 ;例例 int a 3=int a 3=1,21,2,4 4 ;部分初始化部分初始化部分初始化部分初始化 a00a00 a01a01 a02a02 a10a10 a11a11 a12a12 1 12 20 04 40 00 0行长度可以省略行长度可以省略行长度可以省略行长度可以省略例例例例 int a23=int a23=1,2,31,2,3,4,5,64,5,6 ;a00a00 a01a01 a02a02 a10a10 a11a11 a12a12 1 12 23 34 45 56 6全部初始化全部初始化全部初始化全部初始化 a00a00 a01a01 a02a02 a10a10 a11a11 a12a12 1 12 20 04 40 00 0按存储顺序初始化按存储顺序初始化例例例例 int a23=int a23=1,2,41,2,4;例例例例 int a23=int a23=1,2,3,4,5,61,2,3,4,5,6;全部初始化全部初始化全部初始化全部初始化 部分初始化部分初始化部分初始化部分初始化 例例例例 int a 3=int a 3=1,2,3,4,51,2,3,4,5;行长度可以省略行长度可以省略行长度可以省略行长度可以省略a00a00 a01a01 a02a02 a10a10 a11a11 a12a12 1 12 23 34 45 56 6a00a00 a01a01 a02a02 a10a10 a11a11 a12a12 1 12 24 40 00 00 0a00a00 a01a01 a02a02 a10a10 a11a11 a12a12 1 12 23 34 45 50 0 1 2 3 4 5 6 7 8 9 10 11 12二维数组的输入和输出二维数组的输入和输出例例1：将一个：将一个34矩阵输入到数组中并按行输出。矩阵输入到数组中并按行输出。#include stdio.h#include stdio.hvoid main()void main()int a34,i,j;int a34,i,j;for(i=0;i3;i+)for(i=0;i3;i+)for(j=0;j4;j+)for(j=0;j4;j+)scanf(%d,scanf(%d,&aij);aij);for(i=0;i3;i+)for(i=0;i3;i+)for(j=0;j4;j+)for(j=0;j4;j+)printf(%3d,aij);printf(%3d,aij);printf(n);printf(n);0 10 1 2 2 3 30 01 12 2举举 例例例例2：写结果。：写结果。#include#include void main()void main()int i,x33=6,5,4,3,2,1;int i,x33=6,5,4,3,2,1;for(i=0;i3;i+)for(i=0;i3;i+)printf(%d,xi2-i);printf(%d,xi2-i);6 5 06 5 04 3 04 3 02 1 02 1 00 1 20 1 20 0 1 1 2 2032例例3:程序功能是求二维数组每列元素的平均值，修改程序中程序功能是求二维数组每列元素的平均值，修改程序中的错误。的错误。#include iostream.h#include iostream.h#define M 3;#define M 3;void main()void main()int aMM=1,2,3,4,5,6,7 int aMM=1,2,3,4,5,6,7 int i,j;int i,j;for(i=0;iM;i+)for(i=0;iM;i+)for(j=0;jM;j+)for(j=0;jM;j+)avei=avei+aij;avei=avei+aij;avei=avei/M;avei=avei/M;for(j=0;jM;j+)for(j=0;jM;j+)cout avej;cout avej;#include iostream.h#include iostream.h#define M 3#define M 3void main()void main()int aMM=1,2,3,4,5,6,7 int aMM=1,2,3,4,5,6,7;int i,j;int i,j;float aveM ;float aveM ;for(i=0;iM;i+)for(i=0;iM;i+)for(j=0;jM;j+)for(j=0;jM;j+)avei=avei+a avei=avei+aj j i i;avei=avei/M;avei=avei/M;for(j=0;jM;j+)for(j=0;jM;j+)cout avej;cout avej;=0=0#include#include void main()void main()int a5050,m,n,i,j,row,column,max;int a5050,m,n,i,j,row,column,max;cinmn;cinmn;for(i=0;im;i+)for(i=0;im;i+)for(j=0;jn;j+)for(j=0;jn;j+)scanf(%d,&aij);scanf(%d,&aij);max=a00;max=a00;for(i=0;im;i+)for(i=0;im;i+)for(j=0;jn;j+)for(j=0;jn;j+)if(maxaij)if(maxaij)max=aij;max=aij;row=i;row=i;column=j;column=j;printf(max=%d,row=%d,column=%d,max,row,column);printf(max=%d,row=%d,column=%d,max,row,column);例例例例4:4:4:4:求二维数组中最大元素值及其行列号求二维数组中最大元素值及其行列号求二维数组中最大元素值及其行列号求二维数组中最大元素值及其行列号row=0;column=0;row=0;column=0;例例5：将二维数组行列元素互换，存到另一个数组中：将二维数组行列元素互换，存到另一个数组中a=a=1 2 31 2 34 5 64 5 6b=b=1 41 42 52 53 63 6举举 例例#include#include#include#include void main()void main()int a5050,b5050;int a5050,b5050;int m,n,i,j;int m,n,i,j;cinmn;cinmn;for(i=0;im;i+)for(i=0;im;i+)for(j=0;jn;j+)for(j=0;jaij;cinaij;for(i=0;in;i+)for(i=0;in;i+)for(j=0;jm;j+)for(j=0;jm;j+)bij=aji;bij=aji;for(i=0;in;i+)for(i=0;in;i+)for(j=0;jm;j+)for(j=0;jm;j+)cout coutsetw(3)setw(3)bij;bij;coutendl;coutendl;沿主对角线将矩阵沿主对角线将矩阵沿主对角线将矩阵沿主对角线将矩阵a a a a翻转所得翻转所得翻转所得翻转所得到的矩阵就是到的矩阵就是到的矩阵就是到的矩阵就是a a a a的转置矩阵的转置矩阵的转置矩阵的转置矩阵v 矩阵的和运算矩阵的和运算1 2 34 5 67 8 9+1 1 16 5 49 8 7=2 3 410 10 1016 16 16v 矩阵的积运算矩阵的积运算1 2 34 5 67 8 93 2 16 5 49 8 7=？1*3+2*6+3*9i i行上的元素分别与行上的元素分别与行上的元素分别与行上的元素分别与j j列上的元素相乘后列上的元素相乘后列上的元素相乘后列上的元素相乘后的累加和作为结果的累加和作为结果的累加和作为结果的累加和作为结果矩阵的矩阵的矩阵的矩阵的ijij矩阵的运算矩阵的运算v 矩阵的差运算矩阵的差运算1 2 34 5 67 8 9+1 1 16 5 49 8 7=0 1 2-2 0 2-2 0 2例例6：打印杨辉三角形。：打印杨辉三角形。(a+b)(a+b)n n 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1#include#include#define M 30#define M 30void main()void main()int aMM=0,i,j,n;int aMM=0,i,j,n;scanf(%d,&n);scanf(%d,&n);for(i=0;in;i+)for(i=0;in;i+)ai0=1;ai0=1;aii=1;aii=1;for(i=2;in;i+)for(i=2;in;i+)for(j=1;ji;j+)for(j=1;ji;j+)aij=ai-1j+ai-1j-1;aij=ai-1j+ai-1j-1;for(i=0;in;i+)for(i=0;in;i+)for(j=0;j=i;j+)for(j=0;j=i;j+)printf(%5d,aij);printf(%5d,aij);printf(n);printf(n);举举 例例012340 1 2 3 4作作 业业看实验指导书看实验指导书P140程序调试程序调试运行错误的判断与调试运行错误的判断与调试1、编写程序，从矩阵中找、编写程序，从矩阵中找“鞍点鞍点”。如果某个元素是。如果某个元素是“鞍点鞍点”，那么该元素在所处的行中最大，列上最小，也可能没有鞍点。，那么该元素在所处的行中最大，列上最小，也可能没有鞍点。要求：如果有鞍点，输出鞍点的值，以及其所处的行和列下标，要求：如果有鞍点，输出鞍点的值，以及其所处的行和列下标，否则输出否则输出NO。输入分。输入分m+1行：第一行为行：第一行为m和和n的值，以下的值，以下m行行代表二维数组，其中每一行包括代表二维数组，其中每一行包括n个数。个数。样例输入：样例输入：3 4 1 2 4 3 5 6 7 8 6 8 9 4 样例输出：样例输出：4 0 2 作作 业业样例输入：样例输入：3 4 1 2 3 4 5 6 7 0 8 7 6 5 样例输出：样例输出：NO 2、编写程序，计算两个矩阵（均为、编写程序，计算两个矩阵（均为2行行2列）之积。输入分列）之积。输入分2*2行：前两行为第一个矩阵，后两行为第二个矩阵。行：前两行为第一个矩阵，后两行为第二个矩阵。样例输入：样例输入：1 2 4 5 3 5 1 7 3、编写程序，输出矩阵（、编写程序，输出矩阵（3行行3列）的左上三角。列）的左上三角。样例输入：样例输入：1 2 3 4 5 6 7 8 9 作作 业业样例输出：样例输出：5 19 17 55 样例输出：样例输出：1 2 3 4 5 7 4、编写程序，输出、编写程序，输出n层正方形图案。正方形图案最外层是第一层正方形图案。正方形图案最外层是第一层，每层用的数字和层数相同。层，每层用的数字和层数相同。样例输入：样例输入：3 5、编写程序，计算二维数组中各行之和、各列之和以及所有元、编写程序，计算二维数组中各行之和、各列之和以及所有元素之和。素之和。样例输入：样例输入：2 3 1 2 3 4 5 6 作作 业业样例输出：样例输出：1 1 1 1 11 2 2 2 11 2 3 2 11 2 2 2 11 1 1 1 1 样例输出：样例输出：6 15 5 7 9 21 6、编写程序，找出、编写程序，找出m行行n列的二维数组中每行元素的最大值以列的二维数组中每行元素的最大值以及每列元素的最小值。输入分及每列元素的最小值。输入分m+1行：第一行为行：第一行为m和和n的值，以的值，以下下m行代表二维数组，其中每一行包括行代表二维数组，其中每一行包括n个数。输出分两行：第个数。输出分两行：第一行为每行元素的最大值，第二行为每列元素的最小值。一行为每行元素的最大值，第二行为每列元素的最小值。样例输入：样例输入：3 31 2-1-3 4 27 9 8样例输出：样例输出：2 4 9-3 2-1 作作 业业