1(a) 下列算法ALG1處理非負數的整數變量N，並將結果儲存至陣到X內，其索引為1至6。 ALG1

Presentation on theme: "1(a) 下列算法ALG1處理非負數的整數變量N，並將結果儲存至陣到X內，其索引為1至6。 ALG1"— Presentation transcript:

1 1(a) 下列算法ALG1處理非負數的整數變量N，並將結果儲存至陣到X內，其索引為1至6。 ALG1
步驟2: i = 0 步驟3: 當 N>=1，執行步驟 4至6 步驟4: X[6-i] = (N/2) 的餘數 步驟5: N = (N/2) 的整數部分 步驟6: i = i+1 for(i=1;i<=6;i++) X[i]=0; i=0; while(N>0){ X[6-i] = N%2; N = N/2; i++; } (i) 假設N=29。空運行 ALG1 N=29 N%2 N/2 1 14 0 7 1 3 1 1 1 0 (1) 填上 X 的內容。 X[1] X[2] X[3] X[4] X[5] X[6] 1 (2) 這個循環的迭代會有多少次? 5 DSE 2012

2 (ii) N可被 ALG1 處理，而不會產生錯誤的範圍是什麼? (range of N) 試簡略解釋。
∵迭代次數<=6, ∴N=63 (N/2=31,15,7,3,1,0) (iii) 細看在(a)(i) 內 X 值的樣式。ALG1 有什麼用途? Dec2Bin 十進制(N)轉二進制X[] (b) 下列算法ALG2處理非負數的整數變量N，並將結果儲存至陣列Y內，其索引為1至6。N 是少於 64 的。 ALG2 與陣列X作用相同 for(i=1; …) Y[i]=0; j=1; while(N>0){ if(N>=Z[j]){ Y[j]=1; N=N-Z[j]; } j++; 步驟1: 初始化 Y 每個元素的值為0 步驟2: j = 1 步驟3: 當 N>0，執行步驟 4至7 步驟4: 如果N>=Z[j]，則執行步驟5至6 步驟5: Y[j] = 1 步驟6: N = N-Z[j] 步驟7: j = j+1 DSE 2012

3 (i) 假設N=48。空運行 ALG2，填上 Y 的內容。 Y[1] Y[2] Y[3] Y[4] Y[5] Y[6] 1
以下為陣列 Z 的初始值。 for(i=1; …) Y[i]=0; j=1; while(N>0){ if(N>=Z[j]){ Y[j]=1; N=N-Z[j]; } j++; Z[1] Z[2] Z[3] Z[4] Z[5] Z[6] 32 16 8 4 2 1 (i) 假設N=48。空運行 ALG2，填上 Y 的內容。 Y[1] Y[2] Y[3] Y[4] Y[5] Y[6] 1 迭代2次 (ii) 在最壞的情況下，這個循環的迭代會有多少次? 6次 (N=63) (iii) 試舉出一個 N 值(N>0)，並說明 ALG2 比 ALG1 執行迭代較少。 N=32… ALG1:6次 N / 2= 16,8,4,2,1,0 ALG2:1次 N-32= 0 DSE 2012

4 其他可行的N 值: N 二進制 執行次數(ALG1)2 執行次數(ALG2) 2ⁿ 8 001000 4 3 16 010000 5
20 010100 24 011000 28 011100 32 100000 6 1 34 100010 36 100100 38 100110 40 101000 42 101010 44 101100 46 101110 48 110000 50 110010 52 110100 54 110110 56 111000 58 111010 60 111100 62 111110 其他可行的N 值: DSE 2012

5 (c) ALG2 以一種名為「ICT」 的程式編寫語言編寫， 其源程式將編譯為與機器無關的「ICT bytecode」， 不同平台
每當執行這個程式時，會使用「ICT虛擬機」 (ICT-VM) 解釋和執行「ICT bytecode」。下圖展示這個過程。 解釋和執行 源程式 編譯 ICT bytecode 智能手機內的ICT-VM 計算機內的ICT-VM 桌上電腦內的ICT-VM 其他安裝了ICT-VM的裝置 x.class x.java (i) 參考上圖，試舉出使用「ICT bytecode」的一個好處。 跨平台，可在不同平台上執行(或 具可移植性) (ii) 假設使用機器碼代替「ICT bytecode」。 (1) 這個過程便會改變。簡略描述新的過程。 (2) 這項更改會帶來什麼好處? 須要產生可執行的機械碼(exe)檔案 程式執行得較快。/ 因為沒有使用ICT-VM，需要較少資源運行程式。 DSE 2012

6 2. 某公司安裝一個智能卡考勤系統。員工進入公司時在閱讀器上拍卡， 到達時間便會儲存在智能卡內的一個堆疊stack。
(a) 這個堆疊可儲存最多31項到達時間的數據，它以陣列A和整數變量X建構。 X儲存下一個給堆疊可用的陣列元素的索引，當A已全滿，X便儲存32。 A[1]是第一個元素。 int A[32], X=32; 這個堆疊會在每月初時被初始化，移走堆疊內所有數據，而X=1。 A[31] : A[19] A[4] A[3] A[2] A[1] X = 1 指著空(未用)元素 DSE 2012

7 RET(A) 將會被調用 _____________ 次， X=___ call 19-3=16 4
POP(A) (i) RET(A)是讀取一個到達時間數據的子程式，並從A內移除。假設某智能卡已儲存首19天的到達時間，如要讀取第4天的時間，需要調用RET(A)多少次? 調用後X的值是什麼? RET(A) 將會被調用 _____________ 次， X=___ call 19-3=16 4 損失數據 (第5-19天的到達時間會被刪除) (ii) 在(a)(i) 內的運作需要多一個堆疊。 (1) 如果只採用A會有什麼事情發生? (2) 這個額外堆疊是如何運作? 堆疊指示標指向錯誤的元素來儲存新的到達時間。(錯誤指示標) 複製堆疊至另一臨時的堆疊，並從該臨時堆疊讀取數據。 (儲存數據處理) (iii) 如果這個堆疊，在下一個月繼續使用，而沒有被初始化，會什麼事情發生? 堆疊會產生上溢overflow錯誤。 DSE 2012

8 (b) 每張智能卡都以一個員工編號來識別。 下列結構圖展示這個考勤系統的一些模組
P Q 員工 編號 考勤系統 拍智能卡 來作考勤 其他模組 從智能卡讀取 員工編號 檢查 更新 考勤 數據 員工編號 符號 表示模組之間傳送的數據。符號 表示從有效性檢驗得出的資料。 (i) P是什麼? (ii) Q是什麼? 簡略描述Q的用途。 一個指示員工編號是否有效的標記 DSE 2012

9 (c) 該公司聘用一軟件公司開發此考勤系統。 (i) 軟件公司交付此系統前，會進行用戶驗收測試、系統測試和單元測試。
(1) 哪項測試應首先進行? (2) 哪項測試應最後進行? (3) 指出各種測試的主要目的。 用戶驗收測試： 系統測試： 單元測試： 單元測試 用戶驗收測試 驗收測試:：確保系統符合該公司的要求。 系統測試:：評估整個系統在統合(整合)個別模組後，是否符合規格的需求。 單元測試:：確保每個模組都會按已定義的規格執行其功能。 (ii) 該公司採用直接切入式方法來轉換系統。 (1) 這個方法的主要風險是什麼? (2) 儘管有這項風險，為什麼該公司仍採用這種方法。 若新系統有任何問題，整個系統均受到影響， 甚至不能運作。 它的成本(資金、人力、時間)是最低的。 DSE 2012

10 3. 某公司使用電腦程式，控制一座商業大廈內的升降機，該大廈的4部升降機的編號為1、2、3、4。升降機乘客在地下的控制面板按下樓層，程式便會搜尋及顯示升降機編號，如下列例子所示。地下的樓層是0。
輸入樓層 25 請乘搭升降機 3 (a) 當輸入樓層後，程式便會隨機選擇一部升降機移動至地下。子程式myrand會利用其輸入參數K，返回一個介乎(及包括) 0和K-1的隨機整數。試編寫附有輸入參數N 的子程式call_random，以模擬隨機選擇升降機，並返回升降機編號；而N儲存升降機的總數目。 int call_random(int N){ } return myrand(N)+1; // 1..N DSE 2012

11 為更有效使用外降機，子程式closest取代了call_random。
下列語句已在closest 前說明，MAXFLOOR 和 LIFTTOTAL 分別儲存這座大廈的最高樓層和升降機的總數目。 #define MAXFLOOR 60 #define LIFTTOTAL 4 (b) 為什麼使用 MAXFLOOR 和 LIFTTOTAL 是良好的程式編寫風格? 試舉出2個理由。 容易修改程式內的數值。/ 它令程式更易讀。 / 很容易改編程式，以便在該公司的其他大廈內使用。 DSE 2012

12 int LiftPos[LIFTTOTAL+1]={0,5,10,15,20};
(c) LiftPos 是一個儲存所有升降機位置的全程整數陣列，假設 LiftPos[i] 已儲存升降機i所在的樓層。 int LiftPos[LIFTTOTAL+1]={0,5,10,15,20}; 透過善用 MAXFLOOR 和 LIFTTOTAL， 編寫子程式 closest 返回接近地下的升降機編號，並符合下列的要求： 說明 cPos 和 cLift 為整數變量， 分別用來儲存某升降機所在位置和該升降機的編號; 說明 i 為整數變量，用來儲存索引， 利用一個 for 循環，尋找最接近地下的升降機。 int closet(){ int i, cPos, cLift=1; for(i=2;i<=LIFTTOTAL;i++) if(LiftPos[i]<LiftPos[cLift]) cLift =i; return cLift; } int closet(){ int i, cPos=MAXFLOOR, cLift; for(i=1;i<=LIFTTOTAL;i++) if(LiftPos[i]<cPos){ cLift =i; cPos = LiftPos[i]; } return cLift; DSE 2012

13 25 3 (d) 在系統開發期間，一名系統分析員向升降機乘客收集用戶要求。 (i) 建議系統分析員收集用戶要求的兩種方法。
與用戶面談 (管理層，乘客) 問卷調查 觀察 (例如實施電腦化前，觀察及取得升降機運作的第一手經驗) 審閱統計數據/文件 (例如等待升降機時間) (ii) 舉出一項乘客可能提出的用戶要求。 縮短乘客呼召升降機到地下的等待時間。 輸入樓層 25 請乘搭升降機 3 DSE 2012

14 4.(a) 文字檔 club.txt 最多可儲存100個字串， 每個字串最長可有6個字符，例如。 sports music chess
art ict ReadData 是一個按址調用(call by reference)子程式，它可讀入club.txt 的所有數據，並儲存至其形式參數(formal parameter) A內，而A是一個陣列。 (i) 寫出 ReadData 的形式參數表formal parameter list。 void ReadData(__a(i)__){ int i=0; FILE *infile; infile = fopen("club.txt","r"); _____a(ii)_____ fclose(infile); } char A[][] char A[100][7] char *A[] char **A (ii) 寫出一個 while 循環以完成 ReadData。 while (!feof(infile)){ fgets(A[i],10,infile); A[i][6]='\0'; i++; } while (fscanf(infile,"%s",A[i])!=EOF){ i++; } DSE 2012

15 (b) 以下算法利用插入排序法把A的數據，以遞升序排序，而A的大小為N，首個索引是0。 步驟1: 設j由1至N-1，執行步驟2至7
步驟2: Temp  A[j] 步驟3: i  j-1 步驟4: 當 i>=0和A[i]>Temp 執行步驟5至6 步驟5: A[i+1]  A[i] 步驟6: i  i-1 步驟7: A[i+1]  Temp // A[0]..A[N-1] // A[j] 左面1個 // A[i] 向右移 (i)按算法空運行，列出於第二遍及第三遍執行步驟7後A的內容。 A[0] A[1] A[2] A[3] A[4] 初始時 sports music chess art ict 第一遍 第二遍 第三遍 第四遍 chess music sports art ict DSE 2012

16 步驟4: 當 i>=0和A[i]>Temp 執行步驟5至6 步驟5: A[i+1]  A[i] 步驟6: i  i-1
插入排序法 insertion sort 步驟1: 設j由1至N-1，執行步驟2至7 步驟2: Temp  A[j] 步驟3: i  j-1 步驟4: 當 i>=0和A[i]>Temp 執行步驟5至6 步驟5: A[i+1]  A[i] 步驟6: i  i-1 步驟7: A[i+1]  Temp // A[0]..A[N-1] // A[j] 左面1個 // A[i] 向右移 額外的第一遍(j=0) 是多餘的 Temp = A[0] i = j-1 = -1 當 i>=0 和 A[i]>Temp // 不成立 A[0] = Temp (ii) 假設步驟1改動為 設j由0至N-1，執行步驟2至7 這樣對這個程式運行上會有什麼改變? 試簡略解釋。 (iii) 試描述當使用此算法，需要最長計算時間排序之A的內容。worst case A[0] A[1] A[2] A[3] A[4] 初始時 sports music ict chess art 所有數據都是反序的/倒序排列。 DSE 2012

17 (c) 某程式以邏輯語言(prolog)編寫，附有下列的事實和規則。 事實 Facts 屬於 程式子句
體育　(sports)學會 學生會union belongsto(sports, union), 音樂　(music)學會 學生會 belongsto(music, union). 棋藝　(chess)學會 belongsto(chess, union). 美術　(art)學會 belongsto(art, union). 長笛　(flute)組 音樂學會 belongsto(flute, music). 雙簧管(oboe)組 belongsto(oboe, music). 籃球　(basketball)組 體育學會 belongsto(basketball, sports). 規則 Rules 程式子句 若X屬於學生會，X便是一個學會。 club(X):- belongsto(X,union). 若X屬於一個學會Y，X便是一個組別。 group(X):- belongsto(X,Y) & club(Y). X,Y 變量 DSE 2012

18 ?- belongsto(chess, union). true.
以下的例子是一些查詢的結果。 查詢 結果 ?- belongsto(chess, union). true. ?- belongsto(science, union). false. ?- club(A). A = sports, music, chess, art. (i) 下列查詢的結果是什麼? (1) ?- group(volleyball). (2) ?- belongsto(B, music). (3) ?- group(C). false. B = flute, oboe. C = flute, oboe, basketball. (ii) 寫出尋找美術學會所屬組織的查詢。 ?- belongsto(art,Y). (iii) 與過程語言(C)比較，使用邏輯語言(prolog,lisp)有什麼好處? 邏輯語言專注於設立目標(「解決甚麼」) ， 並使用關係解決問題(事實與規則關聯起來)， 而不是明確指出如何解決問題。 What Facts & Rules How DSE 2012