TAG

首都機能移轉 (2) 歌詞 (2) 靠北文 (40) 戲言 (30) 糟糕 (7) ACG (23) Assembly (2) Boost (2) C (31) C++ (69) CMake (4) CSIE (67) Debian (34) Design_Pattern (2) Django (1) Eclipse (1) en_US (13) FFmpeg (3) FoolproofProject (26) FreeBSD (2) Git (4) GNU_Linux (65) IDE (5) Java (11) JavaScript (19) KDE (15) Khopper (16) KomiX (3) Kubuntu (18) Life (1) Lighttpd (2) Mac_OS_X (2) Opera (1) PHP (2) PicKing (2) Programing (21) Prolog (1) Python (7) QSnapshot (2) Qt (30) Qt_Jambi (1) Regular_Expression (1) Shell_Script (7) Talk (98) VirtualBox (7) Visual_Studio (13) Windows (18) zh_TW (36)

2007年6月24日 星期日

2ch上的動畫歌曲前200名

我也只認得其中的一半左右而已
有很大的原因是因為我沒有碰過鋼彈....另一個原因是我不夠老= =
不過也剛好找到不少以前就想收的歌....奔騰吧!驢子!XD
不過有一首怪怪的....就是EVA的某首....我好像沒聽過說(我不是說劇場版的插入歌)

2007年6月16日 星期六

程式設計期末考

昨天終於迎向第一個該死的期末考....
這次出乎意料的有三分之二都是作業題,早知道我就把作業全部印出來帶進去了= =

555:(30%)(Accepted)

很簡單,但是非常浪費時間的一題。尤其是這題是用pdf存檔,input又很長,結果我每次測試都不能複製貼上,只能慢慢打字;跟助教反應之後,他說:「對哦!沒想到的咧!」
這題我也是用非常鳥的方法,overload了istream又overload operator >....現在都不太想看自己的code= =

568:(20%)(Accepted)

作業題。找N!的最後一個非零數字。原則上不用用到大數,但是只單純去找個位數的話會遇到進位問題,因此要保留部分的位數。

825:(20%)

在迷宮找路徑。雖然是作業,不過我個人很不擅長這類題目,當時就沒做了,這次當然也沒做(汗)。

10017:(20%)

作業題。我強烈希望河內去死一死(笑)。

10409:(20%)(Accepted)

作業題。原則上應該是送分用的....可是助教說答對率比568還低。我想大家應該要養成看過所有題目後再下手寫的習慣的。

10791:(30%)

數學題。應該是這次所有題目裡最有趣的一題,可是我被那個該死的555拖到時間,等我用最後幾分鐘看了這題題目後,就覺得我應該也有辦法寫出來。可是寫了這題我就做不出555了,所以也沒什麼好可惜的。
題目是給你一個正整數N,則你可以找到無限多組其最小公倍數為N的數字集合,目的是要找出數字和最小的集合。我想這題應該跟質因數有關....因為要是乖乖地列出所有的數字,不TLE也很奇怪。有空我可能會去做這題吧。
就這樣,我的總分應該是70....好像不是很理想,如果我有把作業都拿來的話,應該是可以破百說....太可惜了。

2007年6月11日 星期一

C++陣列過大造成stack overflow

如果你有機會在 local 宣告一個夠大的陣列的話,應該會發現雖然編譯無誤,但是在程式甫執行就立刻惡性停止。這是因為區域變數,記憶體會被分配在 stack 區段,而這塊區域一般來說並不夠大,大到可以放巨大陣列,因此只要陣列太大,就會立刻 stack overflow。
解決這個問題的方法有三種,其中一種是把變數設為 global variables。global variables 不會被配置到 stack 區。然而我們知道,不加 const 的全域變數是非常不被鼓勵的寫法,這會使得程式的維護性降低。
第二個方法是在編譯器的選項裡調整 stack 區的大小,這我個人也不推薦。
而第三種方案是,在宣告時不要預先宣告好陣列,而是用 dynamic array 的方式,先宣告好 pointer,再手動分配一段記憶體給它,C++ 用 new,C 就用 malloc。
bool prime[20000000]; //這個會爆
bool* prime = new bool[20000000]; //這個不會
這樣就算設為 local variable 也不會 stack overflow。因為手動配置的區段會被分配在 heap,此區沒有如 stack 區段的大小限制。
最後請記得,自己手動分配出來的記憶體,請自己回收;回收完之後請再養成習慣,把空懸的 pointer 指回 NULL,這就是所謂的小三元(?)[?]
BTW,要對陣列做初始化,不要用 for,這樣速度很慢,C++ 的 <algorithm> 裡有個比較乾脆的函式,就是 fillfill_n,可以直接設定一塊容器的值。C 可用 <string.h> 的 memset。用法請自己問男人或是 Google。
至於 stack 或 heap 是什麼....請去問你們的組合語言或計算機組織的老師吧= =

2007年6月2日 星期六

狗屎運....

實在是沒想到會得獎....有塞到= =
這次題目比上次南程盃預選好多了,比較有鑑別度,上次真的是太誇張了,只有一題是中等,其他全部是難。[?]
這次共八題,涵蓋有演算法、數學、資料結構,三個願望一次滿足。(?)
我到三點半為止(大約是比賽的200分鐘左右)做出四題,不過接下來就再也沒做出來了....[?]
以下是介紹:

10471:

這題題目我當時沒看....Tree我也是非常苦手。
不過這題全世界有試過的人只有三百多個....

10527:(Accepted)

這題很煩....因為題目給的數字最大到1000位數,所以一定要用大數。
換句話說這題是考大數除法....對字串處理不熟的人很容易吃到WA。
最後要注意的是,除到最後還剩二位數以上的話,代表這個數字是不可能被分解了,這時的答案是無解。

10699:(Accepted)

很典型的題型....求有多少個不同的質因數....
這題也沒什麼難度,因為數字限制在1,000,000以下,所以不用建立質數表也可以在時限內跑完。
請記住兩個重點:找質數只需找到N的平方根即可,還有除了2和3以外,其他的質數都是6n+1或6n+5。

10701:

資料結構題。
因為題意好像有點不清,我沒有做這題。

10891:

這題應該要用到演算法吧。
光是要怎麼玩出最佳化玩法就要寫很久了....有想的價值,但是放棄。

10916:(Accepted)

這題乍看之下要用大數寫....其實不用....
首先,晶片的bit數的算法是X - 1940再除以10取整數。所以1960是4-bits,1980是16-bits....以此類推。
然後把它當2的指數就可以得到它最多是幾位數,再做一次2的次方就可以得到最大值。
所以題目的式子是:N! <= 2 ^ ( 2 ^ ( ( X - 1940 ) / 10 ) );求N的最大值。
直接算一定會爆,所以對兩邊取對數:log 1 + ... + log N <= 2 ^ ( ( X - 1940 ) / 10 ) * log 2
這樣兩邊的值都不會超過double,剩下的就是很簡單的迴圈了。
由於只是比大小,不用擔心準確度的問題。
不知道為啥很多人死在這題....
(PS:這題我好像只花了13分鐘....)

11044:(Accepted)

完全是送分題,有來就會對,所以沒什麼講的必要....

11127:

據學弟說他是用暴力法求的....我是一直在想有沒有算術上的解法....看來是沒有= =
這次WA一次[?],其他都是一擊必殺。
比較不利的一點是,因為我是空手到,所以任何的思考都是在小畫家上畫的....
請要比賽的人注意,就算不想帶參考資料也要記得帶紙筆= =
對了,贏我的人不但是學弟,而且他答對六題!
面目無光....