網頁

Tuesday 28 February 2012

1st Recursion

初學 PASCAL 時, 覺得 recursion 很難理解
當然現在知道 recursion 和 procedure call 原理都是一樣, 沒甚麼特別
(其實如果當年懂得 stack 的概念的話應該容易理解一點)
溫 342 procedure call 的時侯突然想起第一次寫 recursion, 便去找當年幼嫩的代碼

[PCOJ1057 Oil Deposits - Find #components in n*m grid]

var n, m, i, j, count : integer;
    v : array[0..105, 0..105] of boolean;
    s : array[0..105] of string;

procedure lab(x, y : integer);
var i, j : integer;
begin
   v[x, y] := true;
   for i:=-1 to 1 do
      for j:=-1 to 1 do begin
          if (x+i=0) or (x+i>n) or (y+j=0) or (y+j>m) then continue;
          if (v[x+i, y+j] = false) and (s[x+i, y+j] = '@')
          then lab(x+i,y+j);
      end;
end;

begin
   readln(n, m);
   for i:=1 to n do readln(s[i]);
   count := 0;

   for i:=1 to n do
       for j:=1 to m do
           if (v[i, j] = false) and (s[i,j] = '@') then begin
              lab(i, j);
              count := count+1;
           end;

   writeln(count);
end.

Tuesday 14 February 2012

Select k-th element in linear time

上週日提起 linear time 的 selection algorithm, 發現 wiki 寫得很詳細
原理很簡單, 只是原本 partial quick sort 選 pivot 的那部份改進

假設 PICK(A, k) = k-th element in A[]
原本是 random 選一個 pivot, 現在則是把 array A 分成 |A|/5 組
每組找出 5 個數中的 median, 叫作 B[0], B[1], .. B[|A|/5-1]

然後 call PICK(B, |B|/2) recursive 找出 B[] 真正的 median 作為 pivot
由於每個 B[i] 都至少大於/等於 3 個 element, 而 pivot 又大於/等於 |A|/10 個 B[] 中的數
所以 pivot 至少大於/等於(& 小於/等於) A 中 3/10 的 element, 即是 partition 後的 size 最大為原本的 7/10
然後便像原本 partial quick sort 做下去

得 T(N) = T(N/5) + T(7N/10) + O(N)
⇒ T(N) = c * N * (1 + 9/10 + 81/100 + ...) ≤ 10 * c * N = O(N)

一開始覺得 '5' 很神奇, 發現其實不一定要是 5
假設不是分為 |A|/5 組而是 |A|/k 組 (k = odd integer)
便會變成

T(N) = T(N/k) + T(N * (1 - (k+1)/4k)) + O(N)

T(N) 是 linear 的條件是 1/k + (1 - (k+1)/4k) < 1 即 k > 3
估計由於 5 是最小的 odd integer solution 所以是 5 吧 [利申: 我估的]

Monday 13 February 2012

Sem 4 4/13: FORTRAN & COBOL

原來沒有功課的四個星期過得真快
318 Asg 1 是要模擬一 object 在某房間內的 movement, 而且有一堆會 board



做法只是每次找最接近的 board, 計算 segment intersection
比較莫明奇妙的是 output
spec 要求把 path 上每一點都 truncate 至整數點, 再把整個 bitmap print 出來



很明顯 precision 會很有影響, 尤其是條 path pass through 交點時
雖然可以處理, 但是這份功課的重點已經開始偏離 programming languages 本身

FORTRAN

特別限制: 只能使用 if, goto, 不能使用 loop 等
據說是為了體驗 'the old times', 不過用 if goto 也很輕鬆
本身不支援 recursion, 所以整個 FORTRAN 感覺是線性的

比較麻煩的是 1)沒有 struct 2) procedure 不能 access global variable
1) 加上 FORTRAN 是一行一句使得 code 很難看
2) 由於要把所有相關的 variable pass 入去, 又是把 function 寫得很長

總括來說還是寫得很順手



COBOL

B stands for business, 好像是很古老的商業用 language
很明顯用來寫 geom 已經很莫明奇妙, 如果想體驗的話應該寫該種 language 應該寫的 program
COBOL 除了不適合用來計數外, 本身己經有一大堆缺憾

1) Define variable 竟然要一行一個




2) 接近英文的語法
眾多缺點中最差的一個, 例子:
ADD X TO Y GIVING Z
MOVE 1 TO X
據說設計的原意是 "讓不懂電腦的人也可看懂程序", 真是莫明奇妙
不懂電腦的人根本沒必要看懂, 懂電腦的看得很辛苦
幸好後來發現有 COMPUTE, 可以正常地打 arithmetic expression..

3) 莫明奇妙的限制
例如有 PERFORM N TIMES.. END-PERFORM (幸好有 loop 用)
但是卻不能在 N TIMES 中打 expression, 例如 PERFORM N-1 TIMES 是不行的

種種問題令段 program 寫得冗長又難看
雖然古老的 language 有很多不足很正常, 但是最莫明奇妙是要用來寫 geom 和搞 output format, precision 等, 令我對 318 的印象--