星期一, 6月 25, 2007

計實

第一題:
基本的 GUI,平常作業有參與應不至於做不出來。


第二題 - Binary Search
二分搜尋法,要點在於區間的取捨,不論是前閉後開區間([)),或前閉後閉區間([]),各有不同的作法。
以在程式中最常見的前閉後開區間來說,當下界大於或等於上界時,就是搜尋結束之時。而上下界值的改變也是很重要的一環,程式碼如下:

while (l < u) {
int mid = (l + u) / 2;
if (array[mid] == number)
return true;
else if (array[mid] < number)
l = mid + 1;
else
u = mid;
}
return false;

上下界值改變的重點就在於 lower 要加1,但upper不用,因為下界是閉,代表包含此值,但 index 為 mid 之值已檢查過,因此應不在區間內,所以必須加1;而上界是開,代表不包含此值,因此直接設為 mid 便可。

第三題:遞迴作圖
以前中區學科有出過類似的題目(不過當時不是作圖,是求作標),概念上不難,難是難在要懂得如何在 GUI 介面上畫圖。其實這題算是我這次考試學到的東西吧!以前都還不知怎麼畫圖呢! XD

沒有留言: