计算概论b马思伟2014讲稿lecture10程序设计数组

1、计算概论(Introduction to Computing) 马思伟北京大学数字媒体研究所 第十讲第十讲 程序设计程序设计-数组数组2 2 2 2 2 2 2 2关于练习o 数据输入o 错误：scanf(“%d”, a); scanf(“%d”, a10); scanf(“%d”, &ai);o 元素交换o t=ai; ai=aj; aj=t; o 边界条件o for(i=0; iN; i+)o t=ai; ai=aN-1-i; aN-1-i=t; o 数组的输出o 必须一个元素一个元素的输出o 错误：printf(“%d”, a), printf(“%d”, a10)o for(i

2、=0; iN; i+) printf(“%d ”, ai);o 注意：没有换行，连续输出 o 3 3 3 3 3 3 3 3错误示例4 4 4 4 4 4 4 4数组的定义o 数组定义方法如下：o 数据类型 变量名 数组元素个数= 数组元素初值;o 其中“= 数组元素初值 ”部分可以省略。o 一些数组定义的例子：o int score5;o char cards4 = a, 0, r, W;o float point2 = 2.56, 23.43;o double distances4 ;5 5 5 5 5 5 5 5数组在内存中的布局6 6 6 6 6 6 6 6数组元素的遍历o 可以用一个

3、循环语句给数组的所有元素赋值，或顺序访问它的每个元素。例如：o int i;o int student100；o int odd=0, even=0;o for (i=0; i100；i+) o o studenti = i+1;o if (studenti % 2) = 0)o o even+;o elseo o odd+;o o 7 7 7 7 7 7 7 7多维数组o 二维数组的定义：数组的数组o 类型 变量名数组行数数组列数=初值列表,初值列表o 二维数组的例子：o int matrix1010=0;o int n2323=1,2,3,2,4,6;o double scoresSTUD

4、ENT_NUMCOURSE_NUM;o 其他多维数组可以此类推8 8 8 8 8 8 8 8多维数组数据存储o 二维数组，行列索引的表格9 9 9 9 9 9 9 9多维数组数据存储o 二维数组在内存中的一维顺序排放1010101010101010多维数组在内存中的布局1111111111111111二维数组初始化o 初始化:o #define NUMROWS 3o #define NUMCOLS 4o int valNUMROWSNUMCOLS = 8,16,9,52,o 3,15,27,6,o 14,25,2,10 ;o int valNUMROWSNUMCOLS = 8,16,9,52,

5、3,15,27, 6,14,25,2,10;11121212121212121212Next rowNext column 1313131313131313二维数组存储o int ar 34;o i = ar13;13ar04 = ?1414141414141414141515151515151515例题：找出成绩最好的学生151616161616161616问题分析o For each student:o calculate the average score；o is the highest ever recorded?o mark the student; record the scor

6、e;o (else)o next student;o print out the marked student;161717171717171717171818181818181818Exp: ASCII art array of characters18191919191919191919Exp: ASCII art array of characters (cont.)202020202020202020Exp: ASCII art array of characters (cont.)2121212121212121Exp: ASCII art array of characters (

7、cont.)212222222222222222多维数组的使用o 计算全年级180名学生每个学生8门课的平均成绩和每门课全年级平均成绩o 求解过程o 定义一个1808的二维数组记录各门课成绩o 录入每个人各门课成绩o 计算每名学生的平均成绩并打印出来o 计算每门课程的平均成绩并打印出来2323232323232323多维数组的使用2424242424242424多维数组的使用2525252525252525多维数组的使用o 例：一个正方形灰度图片上，肿瘤是一块矩形区域，肿瘤边缘所在的像素点在图片中用0表示，其他肿瘤内和肿瘤外的点都用255表示，现需要计算肿瘤内部的像素点个数（不包括肿瘤边缘上的

8、点）。已知肿瘤边缘平行于图像的边缘2626262626262626多维数组的使用o 解题思路o 需要设计一个二维数组o 通过循环找到肿瘤的第一个点和最后一个点o 根据点坐标计算面积即可o 程序设计o 定义一个1000 x1000的二维数组o 输入正方形区域的边长o 输入区域中所有的点o 找出第一个点o 找出最后一个点o 计算其所求区域面积2727272727272727多维数组的使用n#include nint area10001000nint main()nn int n; n scanf(“%d”, &n); n int f=-1, re=0, i, j, star1, star2

9、, end1, end2; n for(i=0; in; i+)n for(j=0; jn; j+)n n scanf(“%d”, &areaij); n if(areaij=0 & f=-1)n n star1=i+1; n star2=j+1;n f=1;n 2828282828282828 if(areaij=0) end1=i-1; end2=j-1; re= (end1-star1+1)*(end2-star2+1) printf(“%dn”, re); return 0; 2929292929292929课上练习o 编程序产生杨辉三角o 1o 1 1o 1 2 1o

10、 1 3 3 1o 1 4 6 4 13030303030303030小结o 二维数组定义、初始化、存储、访问3131313131313131思考题问题描述问题描述有有 n 个人，编号为个人，编号为 1, 2, . . ., n, 站成一圈。沿着圈顺序数，站成一圈。沿着圈顺序数，每到第每到第m个人就把他杀掉，这样一直进行下去，直到只个人就把他杀掉，这样一直进行下去，直到只剩下一个人，那个人就活下来。约瑟夫很聪明，他总会剩下一个人，那个人就活下来。约瑟夫很聪明，他总会想办法站到一个合适的位置上，使得自己能够成为最后想办法站到一个合适的位置上，使得自己能够成为最后一个，从而活下来。例如：一个，从而

11、活下来。例如：n = 6 ， m = 5 时，被杀的时，被杀的顺序是顺序是5, 4, 6, 2, 3 ，而，而 1 最终活下来。最终活下来。 给定给定n, m,求出最后留下的人的编号位置求出最后留下的人的编号位置12345612346123612313startendstartendstartendendstartstartend3232323232323232约瑟夫环问题o 1。使用数组，删除人移动数组o 2。使用数组，删除人用一个标记表示，不用移动数据12345612346123612313startendstartendstartendendstartstartend123456startendstartendstartendendstartstartend1234-16123-1-16123-1-1-11-13-1-13333333333333333约瑟夫环问题o 3。数学解法，复杂度低o N个人的序列o 1 2 3 4k-1 k k+1 .n o 杀掉一个人的序列o 1 2 3 4k-1 k+1 .n o 重排序列o k+1 .n 1 2.