資料結構與演算法 課程教學投影片.

Presentation on theme: "資料結構與演算法 課程教學投影片."— Presentation transcript:

1 資料結構與演算法 課程教學投影片

2 第四章–陣列結構的演算法應用 本章各段大綱 4-1 多項式的運算 4-2 捉大頭抽籤遊戲 4-3 魔術方塊 4-4 對獎演算法與資料結構

3 4-1 多項式的運算 p(x)=anxn+an-1xn-1+…+a1x1+a0（運算式） 陣列表示法範例如下:
1 2 n n+1 陣列 an an-1 a1 a0 註標 多項式階次要加以紀錄（紀錄於註標0的內容） 註標(i)與指數的關係是 指數=n-i+1

4 4-1 多項式的運算 練習2 方程式係數以陣列表示為p(m)=a31m31+a15m15+a7m7+a3m3+a1m1
法二指標之對應表 練習2 方程式係數以陣列表示為p(m)=a31m31+a15m15+a7m7+a3m3+a1m1 法一:設p(m)=a(31)m31+a(15)m15+a(7)m7+a(3)m3+a(1)m1，以基本陣列表示法進行運算 法二:以右表之關係式列出註標x與指數y的關係 令p(m)=a(4)m31+a(3)m15+a(2)m7+a(1)m3+a(0)m1， 假設關係式具有 y=a*2x+b 型式，將下表x,y帶入，可解得 y=2*2x-1=2(x+1)-1，因此演算法可以迴圈及陣列帶入計算 註標x 指數y 1 3 2 7 15 4 31 法一:基本陣列表示法之演算法 int a[n+2],i,pk=0,k=2; //此演算法中n=31 a[32]=n; // 存放項目大小, a[0]存放x0係數 a[1]=1;a[3]=3; a[7]=3;... // 給定係數 for(i=0;i<=n;i++) pk=pk+a[i]*pow(k,i); // k=2, pow()得到2i 法二:壓縮陣列表示法(於後說明)之演算法 int a[n+2],i,pk=0,k=2; //此演算法中n=4 a[5]=n; // a[5]不為係數項,用於存放項目大小 a[0]=1;a[1]=3; a[2]=7;... // 給定係數 for(i=0;i<=n;i++) pk=pk+a[i]*pow(k,pow(2,(i+1))-1); // k=2, pow()得到2i 此演算法的時間複雜度與空間複雜度均O(n) (n為迴圈大小，也是冪次項大小) 此演算法的時間複雜度與空間複雜度均O(n) (注意:為迴圈大小，非冪次項大小)

5 4-1 多項式的運算 p(x)=3x100+2x50+ x25+4 （運算式，求p(k)） 以基本陣列存放註標及係數，過於浪費空間
法一:壓縮陣列表示法如下: V陣列代表係數，但V(0)放項目數m W陣列代表冪次 Index 1 2 ... m V an ai a0 W n i Index 1 2 3 4 V W 100 50 25 int V[4+1],W[4+1],i,pk,k=2, m=4; V[0]=m; V[1]=3;V[2]=2;... // 設定係數 for(i=1;i<=m;i++) pk=pk+V[i]*pow(k,W[i]);

6 4-1 多項式的運算 p(x)=3x100+2x50+ x25+4 （運算式） 法二:壓縮陣列表示如下:
設非零項目m個，一維陣列W共2m+1，註標0存放項目m，其餘註標依序放入非零項目的係數及冪次。 1 2 3 4 ... 2m-1 2m W m an n ai i 第1項 第m項 1 2 3 4 5 6 7 8 W 100 50 25

7 以k帶入多項式，第i項值為：W[2*i-1]*pow(k,W[2*i])
p(x)=3x100+2x50+ x25+4 以k帶入多項式，第i項值為：W[2*i-1]*pow(k,W[2*i]) 1 2 3 4 5 6 7 8 W 100 50 25 第1項 第2項 第3項 第4項 以係數看 項次與註標關係 關係式為2*i-1 以冪次看 項次與註標關係 關係式為2*i int W[2*4+1],i,pk,k=2, m=4; //m為項次 W[0]=m; W[1]=3;W[2]=100;... // 設定係數,冪次 for(i=1;i<=m;i++) pk=pk+W[2*i-1]*pow(k,W[2*i]); 項次 註標 1 2 3 5 4 7 項次 註標 1 2 4 3 6 8 空間複雜度:所需的空間數為2m+2(法一) 及2m+1(法二) ，複雜度為O(m) 時間複雜度:即迴圈數，O(m)

8 4-1-4 兩個變數的多項式的運算 -基本陣列表示法
基本陣列表示法如下， 宣告二維陣列(m+1)*(n+1): 範例 P(x,y)=x3+2x2y+3x+4y4+5y2+6 x0 x1 : xm y0 y1 ………… yn a00 a01 ………… a1n a10 a11 ………… a2n am1 an2 ………… amn 1 2 3 4 6 5 計算時只要使用陣列的走訪 (由左至右，由上至下) for(i=0;i<=m;i++) for(j=0;j<=n;j++) Pk=pk+A[i][j]*(x**i)*(y**j); 注意:此非完整C程式語法

9 4-1-4 兩個變數的多項式的運算 -壓縮陣列表示法
p(x,y)=x100+2x50y50+3x25y50+4y100+5 要以基本陣列表示時，此陣列有(m+1）*(n+1)空間，但只利用五個元素，因此以壓縮陣列表示較為節省空間 法一：壓縮陣列表示法1如下:V存放係數，XW存放X的冪項，YW存放Y的冪項，時間複雜度O(mn) 1 2 3 4 5 V XW 100 50 25 YW

10 4-1-4 兩個變數的多項式的運算 -壓縮陣列表示法
p(x,y)=x100+2x50y50+3x25y50+4y100+5 法一：稀疏矩陣的壓縮陣列表示法 1 2 3 4 5 V XW 100 50 25 YW int V[m+1],XW[m+1],YW[m+1]… for(i=0;i<=m;i++) pk=pk+V[i]*(x**XW[i])*(y**YW[i]); 若共m個非零項，所需空間 3m+1，空間複雜度O(m) 執行迴圈m 次，時間複雜度O(m) ，效率比基本矩陣運算高出許多

11 4-1-4 兩個變數的多項式的運算 -壓縮陣列表示法
p(x,y)=x100+2x50y50+3x25y50+4y100+5 （運算式） 法二：稀疏矩陣的壓縮陣列表示法如下: 1 2 3 4 5 6 … 3r-2 3r-1 3r r 第一項 係數 X冪次 Y冪次 第二項 第r項 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 100 50 25

12 4-1-4 兩個變數的多項式的運算 -壓縮陣列表示法
p(x,y)=x100+2x50y50+3x25y50+4y100+5 （運算式） 法二：稀疏矩陣的壓縮陣列表示法 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 100 50 25 int V[3m+1]…//非零項有m項 for(i=0;i<=m;i++) pk=pk+V[3*i-2]*(x**V[3*i-1])*(y**V[3*i]); 若共m個非零項，所需空間 3m+1，空間複雜度O(m) 執行迴圈m 次，時間複雜度O(m) ，效率比基本矩陣運算高出許多

13 4-1 多項式的運算 4-1-5 多項式相加 基本陣列表示法的演算法 將相同註標的A矩陣與B矩陣資料相加即可 01 02 03 04 05
06 07 08 09 10 /* 演算法名稱：兩個多項式相加的演算法 (兩個多項式的項數要相同) */ /* 輸入：二個用陣列代表的多項式 */ /* 輸出：用陣列代表的二個多項式相加的結果 */ poyadd(A,B,C,n) { int A[n+2],B[n+2],C[n+2],i; for (i=1;i<=n;i++) C[i]=A[i]+B[i]; }

14 4-1 多項式的運算 多項式相加 陣列AV,AW代表A(x)多項式的係數及冪次，陣列BV,BW代表B(x)多項式的係數及冪次，底下為壓縮陣列表示法的演算法 比較A[i]及B[j] ，如果 i或j超過m，到步驟五 如果AW[i]=BW[j] ，即冪次相同，則CV[k]=AV[i]+BV[j] ，CW[k]=AW[i] ，k是目前多項式的項數，AW[i]及BW[j]運算後，i,j均往後加一 如果AW[i]>BW[j] ，即AW[i]冪次較高，則CV[k]=AV[i] ，CW[k]=AW[i] ，i往後加1，回至步驟1，再重新檢查。 如果AW[i]<BW[j] ，即BW[j]冪次較高，則CV[k]=BV[j] ，CW[k]=BW[j] ，j往後加1，回至步驟1，再重新檢查。 如果i=m+1，而j<m+1，代表B陣列尚有資料尚未運算，將B陣列剩餘的值全部搬到C陣列目前位置之後；如果i<m+1，而j=m+1，代表A陣列尚有資料尚未運算，將A陣列剩餘的值全部搬到C陣列目前位置之後。 範例:假設有二個多項式A(x)=x3+2x+2，B(x)=2x3+2x2+3，求C(x)=A(x)+B(x) ?

15 4-1 多項式的運算-多項式相加 範例:假設有二個多項式A(x)=x3+2x+2，B(x)=2x3+2x2+3，求C(x)=A(x)+B(x) ? 1 2 3 AV AW 1 2 3 BV BW 1 2 3 4 CV CW

16 4-1 多項式的運算-多項式相加

17 4-1 多項式的運算 有關兩個多項式相加減的詳細演算法 (兩個多項式的項數不同),請參考程式4_1.cpp的函式
　void polyadd(AV,AW,BV,BW,CV,CW); polyadd演算法必須走訪過所有A、B陣列中的項目，所以走訪次數為A項次數+B項次數，假設A（x），B（x）多項式的非零項目分別有m1和m2個，則其時間複雜度為O(m1+m2)，0≤m1,m2≤n。最差情況是m1=m2=n，時間複雜度為O(n) 多項式減法運算的演算法與加法運算的演算法相類似，只是將加法運算改為減法運算

18 4-2 捉大頭抽籤遊戲 遊戲解釋: 捉大頭抽籤遊戲如下一頁的附圖，最上面一排是參加抽籤者的名字，最下面一排是籤號、獎品或工差。每個人依序順著直線往下走，當碰到有橫線時，即轉向橫向前進，碰到直線再往下，以此累堆，則只要橫線不要跨過3條直線（只能跨在二直線之間），則此遊戲執行完畢後，最上面一排的每個人會一一對應到最下面一排的位直，且是1對1對應。

19 4-2 捉大頭抽籤遊戲 人名 簽號

20 4-2 捉大頭抽籤遊戲 遊戲的原理是應用到矩陣的交換運算，當你每劃一條橫線時，即代表這兩條直線的資料順序交換 例如上一頁的圖中，
原來{A0,A1,A2,A3,A4}順序的資料，經過第0層橫線後的順序為{A1,A0,A3,A2,A4}，再經過第1層橫線後的順序為{A1,A3,A0,A2,A4}，以此類堆，到最後一排的順序為{A4,A1,A0,A2,A3}，對應到{P0,P1,P2,P3,P4}。

21 4-2 捉大頭抽籤遊戲

22 4-2 捉大頭抽籤遊戲 範例: 右圖之 變數設計 A陣列存放人名 A B C D... 0 1 2 3... ... 1 0 3 2...
... B陣列存放編號 隨著演算過程變更順序 1 2 3 ... 1 3 2 ... ... B陣列最後結果 3 1 2 ... P陣列存放簽號 1 2 ... 預設2號為大頭

23 4-2 捉大頭抽籤遊戲 陣列M存放路徑佈局 1 2 3 A B C D... 0 1 2 3... 1 0 3 2... ...
... 1 2 3

24 4-2 捉大頭抽籤遊戲 捉大頭抽籤遊戲的演算法如下, 其中bighead演算法的時間複雜度計算是走訪M陣列元素的次數，共有(mr+1)*(mc+1)，其時間複雜度為O(mr*mc)。 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 /* 演算法名稱：捉大頭抽籤遊戲的演算法 */ /* 輸入：用陣列代表的資料,mr是最大層編號，mc是最大橫線編號 */ /* 輸出：捉大頭抽籤遊戲的結果 */ void bighead(A,B,P,M,mr,mc) { int i,j; for(i=0;i<=mr;i++) for(j=o;j<=mc;j++) if(M[i][j]==1)swap(B[j],B[j+1]); for(j=0;j<=mc;j++) printf(“第%d位抽籤者，名字%C，對應到籤號%d”， B[j],A[B[j]],P[j]); /*假設A陣列存放字元*/ }

25 4-3 魔術方塊 「魔術方塊」是一個古老的問題，它是在一個n×n的矩陣中填入1到n2的數字，n為奇數，使得每一行、每一列，每條對角線、橫線及直線加總的值都相等，例如圖4-4即為3×3和5×5的魔術方塊。

26 4-3 魔術方塊 H.Coxeter提出產生魔術方塊的規則如下，且這規則可用程式來實作。
由1開始填資料，且放在第0列的中間位置，如果是n×n的魔術方塊，則宣告陣列A為此魔術方塊，註標編號由0~n-1，所以中間位置為(n-1)/2。 將魔術方塊想像成上下左右相接，往左上角填入下一個數字，則有下列情況： (A)位置超出上方範圍，則用最底層相對應的位置。 (B)位置超出左邊範圍，則用最右邊相對應的位置。 (C)如果找到的位置已放入資料，則位置調為下一行，同一列位置且放入下一個數字。 (D)如果找到的位置未放入資料，則放入下一個數字。

27 4-3 魔術方塊 以3×3魔術方塊的產生方式為例，說明如下： 1. (n-1)/2=(3-1)/2=1，所以M[0][1]=1

28 4-3 魔術方塊 2. (0,1)位置往左上的位置為(-1,0)，-1超出範圍，調整位置為(2,0)，放入2。

29 4-3 魔術方塊 3. (2,0)位置往左上的位置為(1,-1)，-1超出範圍，調整位置為(1,2)，放入3。

30 4-3 魔術方塊 4. (1,2)位置往左上的位置為(0,1)，目前已有資料，調整位置為往下，新位置為(2,2)，放入4。

31 4-3 魔術方塊 5. (2,2)位置往左上的位置為(1,1)，放入5。

32 4-3 魔術方塊 6. (1,1)位置往左上的位置為(0,0)，放入6。

33 4-3 魔術方塊 7. (0,0)往左上的位置為(-1,-1)，-1超出範圍，調整位置為(2,2)，但(2,2)已有資料，所以往下，新位置為(1,0)，放入7。

34 4-3 魔術方塊 8. (1,0)往左上的位置為(0,-1)，-1超出範圍，調整範圍為(0,2)，放入8。

35 4-3 魔術方塊 9. (0,2)往左上的位置為(-1,-1)，-1超出範圍，調整範圍為(2,1)，放入9。

36 4-3 魔術方塊 公式推演 位置(i,j)左上角位置為(i-1,j-1) 若(i-1)<0，則x座標調整為(i-1+n)
若(j-1)<0，則y座標調整為(j-1+n) 不管是否超出範圍，(i,j)左上角座標可以用下式求得 若放置位置已有資料時則下移一行 p=(i-1+n)%n g=(j-1+n)%n p=(i+1)%n 課本範例及光碟程式均有錯

37 4-3 魔術方塊 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 /* 演算法名稱：魔術方塊的演算法 */ /* 輸入：一個正方形陣列M和維度n，n必須是奇數 */ /* 輸出：魔術方塊 */ void square(int *M,int n) { int p,q,k; p=0; q=(n-1)/2; M[0][q]=1; for(k=2;k<=n*n;k++) p=(p-1+n)%n; q=(q-1+n)%n; if(M[p][q]>0) p=(p+2+n)%n; q=(q+1+n)%n; M[p][q]=k; }else{ } 課本範例及光碟程式均有錯

38 4-3 魔術方塊 square演算法中由一個迴圈所構成，其執行了n2-1次，時間複雜度為O(n2)，而n×n的魔術方塊至少要填入n2個數字，至少須Ω(n2)的時間，所以square演算法已達解這個問題的最佳演算法，其時間複雜度可表示為θ(n2)。

39 4-4 對獎演算法與資料結構 一般對獎的方式有許多型式
統一發票對獎(統一發票號碼的後幾位與開獎號碼相同) 序號對獎(用搖號碼球或抽籤方式開出中獎號碼，再從對獎資料中找尋是否有相同序號者)及樂透彩對獎。 以台灣發行的樂透彩為例，簽注的方式是從1到42的號碼中選出6個不重覆的號碼a0，a1，a2，a3，a4，a5，而主辦單位會開出6個號碼P0，P1，P2，P3，P4，P5，外加一個特別號P6，得獎方式如下頁

40 4-4 對獎演算法與資料結構 頭獎： 貳獎： 參獎 肆獎 伍獎
{ a0，a1，a2，a3，a4，a5}={ P0，P1，P2，P3，P4，P5} 即6個號碼完全相同。 貳獎： { a0，a1，a2，a3，a4，a5}中的5個號碼出現在{ P0，P1，P2，P3，P4，P5}中 且另1個號碼等於P6。 參獎 { a0，a1，a2，a3，a4，a5}中有5個號碼出現在{ P0，P1，P2，P3，P4，P5}中 且另1個號碼不等於P6。 肆獎 { a0，a1，a2，a3，a4，a5}中有4個號碼出現在{ P0，P1，P2，P3，P4，P5}中。 伍獎 { a0，a1，a2，a3，a4，a5}中有3個號碼出現在{ P0，P1，P2，P3，P4，P5}中。

41 4-4 對獎演算法與資料結構

42 4-4 對獎演算法與資料結構

43 4-4 對獎演算法與資料結構 第一個演算法 lottol演算法用了三個迴圈來比較A和P陣列的值，總共執行6×6×n=36n的比較次數，時間複雜度為O(n)。 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 /* 演算法名稱：對獎的演算法一 */ /* 輸入：對獎號碼陣列P,簽注號碼陣列A,n為號碼個數 */ /* 輸出：對獎結果陣列C */ void lottol(P,A,C,n) { int i,j,k; for(i=0;i<=n-1;i++) for(j=0;j<=5;j++) for(k=0;k<=5;k++) if(A[i][j]==p[k]) C[i]=C[i]+1; }

44 4-4 對獎演算法與資料結構 第二個演算法 條件:
1. 如果lotto1演算法所用的資料結構陣列P除了特別號之外，其餘6個中獎號碼已排序過 2. 陣列A中的每行(row)資料已排序 比較的方法可以用類似多項式加法polyadd演算法一樣，第0個中獎號碼P[0]和第0個簽注號碼A[k][0]比較，則有下列情況： P[0]=A[k][0]，用i代表P的註標，j代表A的第2維註標，則i=i+1，j=j+1，預備再比較下一個號碼。 P[0]>A[k][0]，代表P[0]比較大，則P[0]再準備與下一個A[k][1]比較，即j=j+1。 P[0]<A[k][0]，代表P[0]比較小，則準備下一個P[1]與A[k][0]相比較，即i=i+1。

45 4-4 對獎演算法與資料結構 所以調整上述的想法後，其演算法步驟如下： i=0;j=0。 如果i或j超出5，跳至步驟6。
如果P[i]=M[k][j]，則count[k]=count[k]+1，i=i+1，j=j+1，回到步驟2。 如果P[i]>M[k][j]，則j=j+1，回到步驟2。 如果P[i]<M[k][j]，則i=i+1，回到步驟3。 結束。

46 4-4 對獎演算法與資料結構

47 4-4 對獎演算法與資料結構 由上述演算步驟和說明可得知lotto2演算法如下 01 02 03 04 05 06 07 08 09 10
11 12 13 14 15 16 17 18 19 20 21 22 23 24 /* 演算法名稱：對獎的演算法二 */ /* 輸入：對獎號碼陣列P,簽注號碼陣列A,n為號碼個數 */ /* 輸出：對獎結果陣列C */ void lotto2(P,A,C,n) { int i,j,k; for(k=0;k<=n-1;k++) i=o;j=0; while(i<=6&&j<=6) if(P[i]==A[k][j]) i++;j++; C[k]=C[k]+1; } else if(P[i]>A[k][j]) i++; else j++;

48 4-4 對獎演算法與資料結構 述lotto2演算法用了一個不定迴圈while，執行迴圈的次數最少6次(當6個號碼都一樣時)，最多12次(當i，j的值皆從0開始，逐步遞增到6時)，如果有n筆資料，則最佳情況是執行6n次，最差情況是執行12n次，時間複雜度雖然也是O(n)，但是就實際執行次數來看，它比reloto1演算法的固定36n次，兩者相比為1/6~1/3倍，即lotto2較lotto1快3至6倍。而且lotto2演算法是用到多項式加法polyadd演算法的原理，所以學習「資料結構與演算法」時，所學習過的方法或結構，並不是只限用於解決該類問題而已，而是廣泛地吸收各種演算法的原理和結構設計，以利於應用在各類問題的解答。

49 4-4 對獎演算法與資料結構 第三個演算法 前述lotto1及lotto2研算法以比較數字為基礎
只要提取陣列註標的值再加以累加即可得到相同數字的個數 方法: 陣列P的大小改為43(註標由0~42) ，陣列數值以0或1標示中簽號碼 例如中獎號碼為5,10,15,22,32,42，則P陣列為 簽注號碼為A[k][j] ，欲知第k筆的第j個號碼是否中獎，只要提出P陣列註標為A[k][j]的值即可知道，並將其值加到C[k]中 C[k]=C[k]+P[A[k][j]] 如果號碼相同，則C[k]會加1否則加0 要計算一筆資料中獎號碼，只要用一層迴圈取得簽注號碼，再應用上述程式即可。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 . 41 42 for(j=0;j<6;j++) C[k]=C[k]+P[A[k][j])

50 4-4 對獎演算法與資料結構

51 4-4 對獎演算法與資料結構

52 4-4 對獎演算法與資料結構 01 02 03 04 05 06 07 08 09 10 11 /* 演算法名稱：對獎的演算法三 */
/* 演算法名稱：對獎的演算法三 */ /* 輸入：對獎號碼陣列P,簽注號碼陣列A,n為號碼個數 */ /* 輸出：對獎結果陣列C */ void lotto3(P,A,C,n) { int k,j; for(k=0;k<=n-1;k++) for(j=0;j<=6;j++) C[k]=C[k]+P[A[k][j]]; }

53 4-4 對獎演算法與資料結構 第4個演算法 將多個數字的比較換算為一個數字的比較 （執行時間：比較敘述 > 一般的四則運算）
樂透數字為6個1~42的數字(現在小樂透1~38,大樂透為1~49) 以原先設計的開獎陣列P每個號碼(由小到大)分別乘上1005, 1004, 1003, 1002, 1001, 1000, 則得到新數字PM PM=1005*P[0]+1004*P[1]+1003*P[2]+1002*P[3]+1001*P[4]+1000*P[5]

54 4-4 對獎演算法與資料結構 例如6個號碼5，10，15，22，32，42經上述公式換算結果PM= 。則樂透彩的演算法如下： 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 /* 演算法名稱：對獎的演算法四 */ /* 輸入：對獎號碼陣列P,簽注號碼陣列A,n為號碼個數 */ /* 輸出：對獎結果陣列C */ void lotto4(P,A,C,n) { int i,j; long PM,AM; PM=0;AM=0; for(i=0;i<=6;i++) PM=PM+P[i]*10**(2*i) for(i=0;i<=n-1;i++) for(j=0;j<=6;j++) AM=AM+A[i][j]*10**(2*j); if(PM==AM) C[i]=C[i]+1; }

55 4-4 對獎演算法與資料結構 lotto4演算法的執行次數計算包括產生PM的6次，產生AM共有6n次，比較PM和AM共有n次，所以共有6+6n+n=6+7n次，時間複雜度是O(n)。 但lotto4只能比較出數字是否完全一樣，且數字序列必須先排序過，因為第k筆的數字全中時C[k]=1，否則C[k]=0，而lotto3演算法可由C[k]的值得知簽中幾個號碼，C[k]的值界於0~6之間。 Lotto4演算法主要是介紹有時候設計演算法時，可以朝數字系統方向思考，例如第13章介紹的雜湊函數即是利用雜湊法將資料安排在特定的位置，可利用於資料的搜尋，此即大家所執知的雜湊搜尋演算法。

56 4-4-5 問卷調查與電腦閱卷 以電腦閱卷模仿lotto3演算法為例，假設題目皆是選擇題，選答有1，2，3，4四種情況，共有m題，答對者給4分，答錯者倒扣1分，則可以宣告答案的陣列A為二維陣列，第1維是題目序號，第2維是答案序號，陣列中所存放的值是4或-1，4代表選答正確給4分，-1代表選答錯誤倒扣1分，則其結構如下：

57 4-4-5 問卷調查與電腦閱卷 另考生作答的資料以二維陣列S來存放，第1維是考生序號，第2維是題目序號，S陣列存放的資料為作答資料，則其陣列結構如下：

58 4-4-5 問卷調查與電腦閱卷

59 4-4-5 問卷調查與電腦閱卷 電腦閱卷的演算法如下： 01 02 03 04 05 06 07 08 09 10 11
/* 演算法名稱：電腦閱卷的演算法 */ /* 輸入：A為答案陣列資料,S作答陣列資料 */ /* 輸出：K為考生的陣列成績資料 */ void comexam(A,S,K,m,q,n) { int A[m+1][q+1],S[n][m+1],K[n]; for(i=0;i<=n-1;i++) for(j=0;j<=m;j++) R[i]=R[i]+A[j][S[i][j]]; }