2018/04/14

驚覺演算法真的很重要

我現在正在中興大學修資訊第二專長,這學期修 Algorithms (演算法) 這門課,每個星期的作業量好多,而且幾乎都是數學證明,讓我這數學不好的人感到這門課實在有點難熬。

前幾天跟資工所畢業,現在在業界當工程師的好友 CSC 聊天,我說老師們很需要一個自動排座位的軟體,因為排座位實在很費工夫。

CSC:『咦?不是有很多人用 Excel 寫好這類的程式了嗎?我這邊就有一些啊。』

『那個是用亂數排的,根本不合用。在教室中,有些學生彼此不對頭,不能把他們放在附近;有些又感情太好,放在一起一定講話講個沒完。所以亂數排的座位表完全不能用。』

CSC:『要不然,你可以先把一些不能坐在一起的組合條件寫好,存在一個檔案裡。然後用暴力法,先把全班的可能座位都跑出來,存在一個檔案裡,然後再用先前存好的條件來篩選,祇要找到跟篩選條件相同的,那組座位表就不能用,直接放棄,換下一組,這樣應該很簡單。』

30 秒不到,csc 又傳來訊息:『等等,剛剛的方法不可行!!你們一班有 30 人吧?那用暴力法跑所有的可能性會把硬碟塞爆!因為有 2.65 x 10^32 種組合。』

『嗯,而且就算一秒產生 100 萬種組合,跑個幾兆年也跑不完所有組合!從宇宙誕生到現在也不過才幾億年!!』

CSC:『要不然,你們應該會依照身高來排座位吧?矮的坐前面,高的坐後面這樣?如果依照身高分為高、中、矮三群,這三群分別用暴力法跑所有可能,這樣是有 10! x 3 種可能,每秒鐘可以產生 100 萬種組合的話, 10 秒就結束了。』

討論到這裡,我驚覺演算法 (數學) 真的很重要啊,祇不過是把學生分為三群去做排列組合這麼小的一個改變,就讓一個問題從不可能解決變成在短短的幾秒內可以完成。不過我目前這門課修的不是很好,還有努力空間,加油!!

沒有留言:

張貼留言