資訊處理 94 年程式語言大意考古題

考慮下列程式片段： for I= 1 to n-1 for J=I+1 to n if S(I) > S(J) then begin Temp = S(I); S(I) = S(J); S(J) = Temp endif ㈠若S 陣列元素個數為10（即n=10），則上述程式片段之比較動作共做了幾次？ （10 分） ㈡上述程式片段之功能為何？（10 分）

考慮下列程式片段： k :=(j+13)/27 loop: if k > 10 then goto out k :=k + 1 i := 3 * k - 1 goto loop out: 請以BASIC, PASCAL, FORTRAN, C, JAVA, COBOL中任一種語言改寫上述程式片段 使其沒有goto 指令。（20 分）

試算出下列程式片段之時間複雜度 ㈠（10 分） for i = 0 to n do begin j = i; while j ≠ 0 do j = j/2; end ㈡（10 分） i ← 1 ; j ← 0; for k ← 1 to n do {j ← i+j; i ← j-i;} return j; 94 年交通事業鐵路人員、公路人員升資考試試題 代號：61240 級 別： 士級晉佐級 科 別： 公路：資訊處理

㈠請畫出下述結構之流程圖。（10 分） for (x=2; x<10; x++) { … } ㈡請將下述程式片段以一個if-then-else 指令表示之。（10 分） if X>5 then goto 80 X = X+1 goto 90 80 X = X+2 90 stop

數學上求兩數的最大公因數（Greatest Common Divisor, 簡稱GCD）可使用歐幾里德 （Euclid）的輾轉相除法來完成。規則是“兩數m 與n 的最大公因數等於這兩數的差 和較小數的最大公因數＂，由此可看出遞迴規則如下： 遞迴關係式是 ⎩ ⎨ ⎧ > = = 0 ), % , ( 0 , ) , ( n if n m n GCD n if m n m GCD 請寫一個遞迴程式（任一程式語言）來計算m 與n 兩數（m > n）的最大公因數。 （20 分）