計算概論b馬思偉2014講稿lecture10程序設計數(shù)組

1、計算概論(Introduction to Computing) 馬思偉北京大學數(shù)字媒體研究所 第十講第十講 程序設計程序設計-數(shù)組數(shù)組2 2 2 2 2 2 2 2關于練習o 數(shù)據(jù)輸入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 數(shù)組的輸出o 必須一個元素一個元素的輸出o 錯誤：printf(“%d”, a), printf(“%d”, a10)o for(i

2、=0; iN; i+) printf(“%d ”, ai);o 注意：沒有換行，連續(xù)輸出 o 3 3 3 3 3 3 3 3錯誤示例4 4 4 4 4 4 4 4數(shù)組的定義o 數(shù)組定義方法如下：o 數(shù)據(jù)類型 變量名 數(shù)組元素個數(shù)= 數(shù)組元素初值;o 其中“= 數(shù)組元素初值 ”部分可以省略。o 一些數(shù)組定義的例子：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數(shù)組在內存中的布局6 6 6 6 6 6 6 6數(shù)組元素的遍歷o 可以用一個

3、循環(huán)語句給數(shù)組的所有元素賦值，或順序訪問它的每個元素。例如：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多維數(shù)組o 二維數(shù)組的定義：數(shù)組的數(shù)組o 類型 變量名數(shù)組行數(shù)數(shù)組列數(shù)=初值列表,初值列表o 二維數(shù)組的例子：o int matrix1010=0;o int n2323=1,2,3,2,4,6;o double scoresSTUD

4、ENT_NUMCOURSE_NUM;o 其他多維數(shù)組可以此類推8 8 8 8 8 8 8 8多維數(shù)組數(shù)據(jù)存儲o 二維數(shù)組，行列索引的表格9 9 9 9 9 9 9 9多維數(shù)組數(shù)據(jù)存儲o 二維數(shù)組在內存中的一維順序排放1010101010101010多維數(shù)組在內存中的布局1111111111111111二維數(shù)組初始化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二維數(shù)組存儲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多維數(shù)組的使用o 計算全年級180名學生每個學生8門課的平均成績和每門課全年級平均成績o 求解過程o 定義一個1808的二維數(shù)組記錄各門課成績o 錄入每個人各門課成績o 計算每名學生的平均成績并打印出來o 計算每門課程的平均成績并打印出來2323232323232323多維數(shù)組的使用2424242424242424多維數(shù)組的使用2525252525252525多維數(shù)組的使用o 例：一個正方形灰度圖片上，腫瘤是一塊矩形區(qū)域，腫瘤邊緣所在的像素點在圖片中用0表示，其他腫瘤內和腫瘤外的點都用255表示，現(xiàn)需要計算腫瘤內部的像素點個數(shù)（不包括腫瘤邊緣上的

8、點）。已知腫瘤邊緣平行于圖像的邊緣2626262626262626多維數(shù)組的使用o 解題思路o 需要設計一個二維數(shù)組o 通過循環(huán)找到腫瘤的第一個點和最后一個點o 根據(jù)點坐標計算面積即可o 程序設計o 定義一個1000 x1000的二維數(shù)組o 輸入正方形區(qū)域的邊長o 輸入?yún)^(qū)域中所有的點o 找出第一個點o 找出最后一個點o 計算其所求區(qū)域面積2727272727272727多維數(shù)組的使用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 二維數(shù)組定義、初始化、存儲、訪問3131313131313131思考題問題描述問題描述有有 n 個人，編號為個人，編號為 1, 2, . . ., n, 站成一圈。沿著圈順序數(shù)，站成一圈。沿著圈順序數(shù)，每到第每到第m個人就把他殺掉，這樣一直進行下去，直到只個人就把他殺掉，這樣一直進行下去，直到只剩下一個人，那個人就活下來。約瑟夫很聰明，他總會剩下一個人，那個人就活下來。約瑟夫很聰明，他總會想辦法站到一個合適的位置上，使得自己能夠成為最后想辦法站到一個合適的位置上，使得自己能夠成為最后一個，從而活下來。例如：一個，從而

11、活下來。例如：n = 6 ， m = 5 時，被殺的時，被殺的順序是順序是5, 4, 6, 2, 3 ，而，而 1 最終活下來。最終活下來。 給定給定n, m,求出最后留下的人的編號位置求出最后留下的人的編號位置12345612346123612313startendstartendstartendendstartstartend3232323232323232約瑟夫環(huán)問題o 1。使用數(shù)組，刪除人移動數(shù)組o 2。使用數(shù)組，刪除人用一個標記表示，不用移動數(shù)據(jù)12345612346123612313startendstartendstartendendstartstartend123456startendstartendstartendendstartstartend1234-16123-1-16123-1-1-11-13-1-13333333333333333約瑟夫環(huán)問題o 3。數(shù)學解法，復雜度低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.