《C++第八课一维数组课件.ppt》由会员分享，可在线阅读，更多相关《C++第八课一维数组课件.ppt（26页珍藏版）》请在三一文库上搜索。
1、C+第八课一维数组,一维数组,第8课,C+第八课一维数组,怎样用以学过知识解决下列问题,输入N个数,要求反向输出这N个数. 例如:输入 5 4 5 3 9 1 输出 1 9 3 5 4,C+第八课一维数组,分析,在解决这个问题时，要把很多数据保存下来，如果用以前的方法定义变量很麻烦，我们可以批量定义变量。最常用的方法是定义数组来解决。 int a10; a是数组名，10表示有10个变量，分别是 a0、a1、a9,且每个值取整型。,C+第八课一维数组,例1:输入N(N10)个数,要求反向输出这N个数. 例如:输入 5 4 5 3 9 1 输出 1 9 3 5 4,定义数组:int a10;,输入
2、: cinn; for (i=0;iai;,输出: for (i=n-1;i=0;i-) coutai;,C+第八课一维数组,一维数组的初始化,在定义数组时对数组元素赋以初值。例如： int a10=0,1,2,3,4,5,6,7,8,9; 可以只给一部分元素赋初值。例如： int a10=0,1,2,3,4; 在对全部数组元素赋初值时，可以不指定数组长度。例如： int a=1,2,3,4,5 两个数组转存，要用循环一一导入，不能直接赋值。 for (i=0;in;i+) ai=bi;,C+第八课一维数组,例2求不达均分的人数 （P1057） 输入n个(n=10)学生的成绩，统计有多少人的分
3、数低于平均分。 样例：输入：4 n=4,表示有4个人的成绩 80 88 44 90 输出： 1 只有1个人的分数低于平均分,1、先定义数组ai用来存放n个人的分数。 存入总分、均分的变量。 2、输入部分：在输入的过程中可以顺便统计一下总分。 3、计算均分 4、统计低于均分的人数。 5、输出。,C+第八课一维数组,P1072陶陶摘苹果,C+第八课一维数组,第一个应用：进制转换,例3将一个十进制整数转化为二进制数. 分析:例如将十进制数12转化为二进制数,方法如下:,把十进制数除以2, 用一个数组a来存放余数,将商作为新的数继续除以2,反复进行,一直除到商为0时停止。 输出：将a组数反向输出,C+
4、第八课一维数组,cinx; k=0; while ( ) k=k+1; /K是数组的下标指针 ak=x% 2; x=x / 2; for ( ) coutai;,C+第八课一维数组,P1098 十六进制中10用A表示，11用B. P1099,C+第八课一维数组,第二个应用：选择排序例4：选择排序:将n个整数按由小到大的顺序输出。样例：输入：6 表示有6个数 5 7 4 3 8 6 输出: 3 4 5 6 7 8,假设6个数据是：a=5 7 4 3 8 6 ，我们把1号位放最小数，就从2号位开始，一一与1号位比较，如果比它小，则交换，这样做到6号位，就使得1号位存放一个最小的数，下面再把2号位放
5、次小的数，从3号位开始比较，以此类推，直至n-1号位。如： a1 a2 a3 a4 a5 a6 5 7 4 3 8 6 5 7 4 3 8 6 a1与a2比较，不交换 5 7 4 3 8 6 a1与a3比较，交换 4 7 5 3 8 6 a1与a4比较，交换 3 7 5 4 8 6 a1与a5比较，不交换 a1与a6比较，不交换 这时，a1就是最小的一个数，下面再进行确定a2，方法同样，最后确定a5，a6不必确定。,C+第八课一维数组,参考程序如下:,cinn; int an+5; /多定义几个 for (i=1;iai; for (i=1;iaj) swap(ai,aj); for (i=1
6、; i=n;i+) coutai“ “;,使用swap交换函数必须使用头文件#include 使用sort max min count函数也要使用这个头文件。 直接用sort 函数排序 如果数组a0-an-1 sort(a,a+n) 如果数组a1-an sort(a+1,a+n+1),sort(a+1,a+n+1),C+第八课一维数组,排序练习,P1102 排序默认的是由小到大排序，查名次的时候应该从后往前。 for (i=n;i=1;i-) if (ai=x) break; cout?;,C+第八课一维数组,P1124 最好不使用sort 排序，选择排序比较的时候要注意两种情况都交换： a数
7、组存编号 b数组存值，比较的时候： if (biaj) 输出的时候，每行要输出三个数。,C+第八课一维数组,基数排序,例7：将n个小于100的不同的正整数进行从小到大排序。 样例：输入： 5 4 3 5 6 1 输出：1 3 4 5 6 采用选择排序的运算次数是n2，可以采用另外一种方法： cinn; for (i=1;ix; ax=1; for (i=1;i0) couti“ “;,如果有相同的，则做一些改动：ax+;在输出的时候当ai1 的时候，必须全部输出。 优点：时间复杂度O(n)。 弱点：必须要知道数据的范围，且是整数。,C+第八课一维数组,练习 P1097 明明的随机数 分析：如果
8、采用一般的模拟方法来做，很麻烦，直接使用基数排序法。 P1096 用上述类似的方法。 数组的值开始都是0； 移走的，将数组的值变成1。 最后统计还有多少个值是0。,C+第八课一维数组,基数排序的运用,P1101 P1096 数组定义在函数外，默认值为0 读一对数，将数组中的这一部分变为1 最后统计数组中还有多少个数是0.,C+第八课一维数组,P1129 十个数的操作 a x输入 三种情况：(1)输出NO: if (x=a10) else for (i=1;i=x) break; /第i位数有可能等于或大于 if (ai=x) 第（2）种情况 else 第（3）种情况 ,C+第八课一维数组,第（
9、2）种情况： 将第i位删除 方法：从i位到n-1位，前面一位取后面一位的值。 for (j=i;j=i+1;j-) aj=aj-1; for (i=1;i=11;i+) coutai ;,C+第八课一维数组,约瑟夫问题：设有N个人依次围成一圈, 从第1个人起开始报数, 报到M的人出列,下一个人再从1起报数,报到M的人出列, 下一个人再从1起报数,如此继续, 直到所有人均出列为止. 设N个人的编号为1,2,.,N, 打印出出列的次序。例如：输入：N=6，M=3，则输出出列的顺序是：3 6 4 2 5 1,int i=0; ai初始化为1；/ai=1表示i在圈上。 for (j=1;jn) i=1
10、; p=p+ai; while (p!=m); /报一轮的模拟 ai=0; couti“ “; /输出，同时将这个人出圈 ,C+第八课一维数组,P1125,C+第八课一维数组,高精度算法 P1870,a100=1; b100=1；a数组作为1！，b数组存放和 for (i=2; i=n;i+) 求i的阶乘:a *i,结果用a数组存放； 求a +b ，结果用b数组存放； 输出：b数组的结果。,C+第八课一维数组,1 2 3 95 96 97 98 99 100,+,1,1,1,0,0,加法过程 g=0; 进率初始为0 for(i=maxn; i=1;i-) s=ai+bi+g; ai=s % 1
11、0; g=s / 10; ,0,a,s,g,C+第八课一维数组,输出部分： i=1; while （ai=0 ,C+第八课一维数组,高精度*单精度,输入时的第一个数用数组存放，而第二个数直接用一个整型变量存放。,1 2 97 98 99 100,a,b,*,S,乘法过程 g=0; 进率初始为0 for(i=maxn; i=1;i-) s=ai*b+g; ai=s % 10; g=s /10; ,C+第八课一维数组,a数组存放被减数，b数组存放减数,结果仍用a数组存放。 for (i=maxn; i=1;i-) if (aibi) ai-1=ai-1-1; ai=ai+10; ai=ai-bi; ,高精度减法,