值得玩味的程式作業

昨日，有人在 MSN 敲我，請我幫助她解一題程式作業，她說班上沒人會寫，只好向外求助。該作業是從某間大學（忘記是哪一所了）資工系的某堂課所出的，個人覺得題目出的很好且很有趣，值得細細品味。 :-)

題目大致如下：
  • 寫出一個多項式相乘的程式
  • 使用串列的方法
  • 可自定任意多項式
  • 舉例：(2X+3Y+4Z)(XY2+X2Y+Z2) = 2XY3+2X2Y2+2Z2X+3XY3+3X2Y2+3Z2Y+4XY2Z+4X2YZ+4Z3
    ＜註＞未知數後的數值代表『指數』，如：X2 代表 X 的平方
對一般學生來說，這作業的困難點是會用到多種技巧，該程式將運用到串列的基本結構、字串解析的技巧以及指標的應用，最重要的需要充分的邏輯思考，以細心慢慢刻出這支小程式。不但如此，該程式寫出來後，還有很多最佳化的改進空間和擴充性，能讓人想改了又改，欲罷不能呀！

筆者在這邊提供一份自己的解答，供有興趣的人參考：
http://people.linux.org.tw/~fred/homework/mathor.c

後記
比起機械，資工系的作業好有趣！早知道當初填志願就填它了！（摔杯子）

留言

  1. 匿名2009年6月3日 晚上10:36

    謝謝你幫了大忙 =...=
    不然這麼一顆必修就掛蛋了
    不過跟你說歐.. 其實是資管系的

    回覆刪除
  2. 匿名2009年6月14日 下午2:04

    這是我出的作業。
    很多人參考您的程式，
    結果當然是零分計算。

    回覆刪除
  3. Fred Chien2009年6月15日 凌晨1:38

    沒料到出題者本人會大駕光臨。 :-)

    至於零分計算，是因為程式有錯嗎？

    回覆刪除
  4. 匿名2009年6月15日 清晨5:43

    題目有寫，COPY別人的程式，以零分計算。

    回覆刪除
  5. 小朱弟2012年6月1日 下午5:24

    妳可千萬別填，當你碰到最根本的程式（比如組合語言、ASSEMBLER、COMPILER、COMPILER COMPILER）或是碰到計算機組織、邏輯設計之類的，你會想放棄一切

    回覆刪除
    回覆
    1. Fred Chien2012年6月2日 晚上11:43

      你說的我應該都算熟悉，但我還是覺得很有趣 :-P

      刪除

張貼留言

這個網誌中的熱門文章

有趣的邏輯問題：是誰在說謊

開心的是期中考接近尾聲，而且今天也是我的生日，更開心的是老天爺待我很好，放我一天假沒給我排考。今天，在網路上逛啊逛，看到了一些判斷說謊的邏輯問題，雖然之前就曾看過，但不管再看多少遍都還是覺得很有趣。也想到好幾天沒寫東西了，就貼上來讓大伙一同分享吧！準備好接受考驗了嗎？ Ready? Go! 第一題： A 說B 在說謊，B 說 C 在說謊，C 說 A、B 都在說謊。請問到底誰在說謊？ 第二題： 現在審問四名竊賊嫌疑犯。已知當中有一名是竊賊，還知道這四個人不是誠實就是說謊，請根據他們回答問題的結果中，判斷誰是竊賊。 甲說：『乙沒有偷，是丁偷的。』 乙說：『我沒有偷，是丙偷的。』 丙說：『甲沒有偷，是乙偷的。』 丁說：『我沒有偷。』 解答：一：只有 B 說真話。二：乙是竊賊。
繼續閱讀

Web 技術中的 Session 是什麼？

圖片
很久沒更新了，自從十二月底退伍之後，一直忙著將書完稿給出版社，沒空坐下來好好在 Blog 上寫點東西。沒辦法，在當兵時閒不下來，就答應了出版社的邀約開始寫 Node.js 的書，因此欠下了書的債。還好，如預期的寫完了，預計這一兩個月應該就會上市，還請各界多多捧場！ 會寫這篇文章的原故，是因為在 Facebook 的社群上，有人問起了關於 Session 和 Cookie 相關性的問題。其實，社群的人都很好，有許多熱心的網友願意幫助別人。不過，為了幫忙回答問題，大家七嘴八舌的東說一句西說一句，甚至引起莫明的論戰，實在不是一個好的現象。況且，使用不同語言、有不同技術背景的人，都各自用自己的角度去描述和解說，讓原本就已經不懂的人更有如瞎子摸象，見不到全貌，搞更糊塗了。對發問的人來說，也不知該聽誰的好。 說來湊巧，筆者剛好在剛截稿的 Node.js 書籍中，對 Session 概念也有許多著墨。所以之前稍微在網路上查過，發現鮮少有人提出對 Session 技術的完整說明，而多半是討論 ASP、.Net、Java、PHP 等語言或框架中如何使用 Session，以及一些延伸的特性，以致很多人對 Session 的概念相當片面。因此這次的事件後，一些網友也建議我把在 Facebook 上回應的完整內容，在 Blog 發表記錄下來，讓更多人對 Session 有個比較完整且正確的認識。 本文目標 在 Web 的世界裡，Session 已經是被廣泛使用的一種技術，大多數的 Web 開發者，肯定都能運用自如。在現今的各類 Web 應用程式的開發框架和工具中，Session 也已經被包裝成容易使用的模式，所以本文也就不再多討論 Session 怎麼去使用，而是著重在 Session 的原理和實現上。要知道，無論是使用哪一種語言，這 Session 概念上都是通用的，沒有什麼不一樣。 Session 是什麼？ Session 之所以會存在，是因為 HTTP 為 stateless 的設計，Server 和 Client 不會一直保持連線狀態，也不會有雙方狀態的即時更新，所以，Server 並不知道 Client 的狀態（像是是否已經登入）。因此，後來的網站開發者，採用 Session 這樣的設計來解決這問題。有趣的是，Se
繼續閱讀

淺談 USB 通訊架構之定義（一）

圖片
USB(Universal Serial Bus) 的應用範疇以及價值已經不需要再多做說明，其身影從 HID(Human Interface Device)、隨身碟（USB Stick、Flash drive、Pen drive）到各種類比式或非連續訊號接收器（如： Webcam、Microphone、DVB Receiver），更進一步可以講到各種通訊裝置或外接設備，甚至是取代和模擬舊式通訊傳輸線（Serial Port）。USB 所有的 Spec 和相關資訊 ，可參考 http://www.usb.org/ 。 USB 整體運作模式 一般來說 USB 的通訊結構有如 Server/Client，以 PC 上的情形為例，位於主機上的 USB 裝置稱為『USB Host』，我們可以在上面外接上數個裝置（與 USB Host 相連的裝置通常被稱為 USB Device 或 USB Client）。 底層上，『Host 負責主導整個 USB 結構的通訊』，它會輪詢所有的 USB Deivce 以檢查是否有裝置需要傳送資料，所有 USB Device 都必需要等待 Host 的命令，唯有 Host 同意時，USB Device 才可以開始傳送資料。 Host 的行為通常是由 USB Host Controller 在做控制，其控制器是一組控制晶片，而對於現代 PC ，USB Host Controller 的晶片通常都被 Layout 在主機板上，以 PCI Bus 的形式存在供作業系統控制，我們可以使用 lspci 看到它的存在： 00:1a.0 USB Controller: Intel Corporation 82801I (ICH9 Family) USB UHCI Controller #4 (rev 03) 00:1a.1 USB Controller: Intel Corporation 82801I (ICH9 Family) USB UHCI Controller #5 (rev 03) 00:1a.2 USB Controller: Intel Corporation 82801I (ICH9 Family) USB UHCI Controller #6 (rev 03) 00:1a.7 USB Controller: Intel Corporati
繼續閱讀

淺談 USB 通訊架構之定義（二）

圖片
之前『 淺談 USB 通訊架構之定義（一） 』已經提過 USB 大致上的概念和一些特性，以及如何從 Linux 上去嘗試驗證 USB Device 上的 Information，但還尚未談及 USB Device 是如何與 USB Host 做溝通。而且，初始化的過程也很重要，該過程會讓一個 USB Device 描述自己的『模式(Configuration)』和『介面(Interface)』以及更多配置上的關鍵訊息。雖然這些初始化過程和定義繁雜，但是拜 OS 優良的包裝所賜，一般驅動程式都可以假設已知或是透過簡單的 API 去取得這些資訊以進行開發，因為大多數初始化動作會自動由 OS Kernel 和 Firmware 所完成。 簡單的 USB Device 初始化流程 插上 USB 裝置 Host 請 裝置 報告 『 裝置 描述資訊 (Device Descriptors )』 （此過程又稱為 Enumeration ） 由 Device Descriptors 得知 『 模式的數量 (bNumConfigurations) 』 Host 請 裝置 回報 『 模式的描述資訊( Configuration Descriptors) 』 由 Configuration Descriptors 得知 『 介面的數量( bNumInterfaces ) 』 Host 請 裝置 回報 『 介面 的描述資訊( Interface Descriptors) 』 由 Interface Descriptors 得知 『 端點的數量( bNumEndpoints ) 』 Host 請 裝置 回報 『 端點 的描述資訊( Endpoint Descriptors) 』 由 Endpoint Descriptors 得知 『 該端點的 資料傳輸模式( bmAttributes ) 』等訊息 等待驅動程式進行後續處理 整個 USB Device 的描述結構可以圖表示： 當然，若不是 USB Device 設計者或是 USB Host Controller 晶片的 Firmware/Driver 開發人員，可以不用知道這麼多過程細節，因為無論是 Linux 還是其他作業系統，它們都會將這些最低階的過程包裝起來，等著驅動程式去使用，而 Linux Kernel 上負責此任務的就被稱為
繼續閱讀

Reverse SSH Tunnel 反向打洞實錄

近來經手了幾個案子，其目標都是設計一台做特定用途的系統，但往往這台機器都會被鎖在防火牆後面，甚至不會連上網際網路，是完全封閉的環境。每當接近結案，將系統交到客戶手中以做最後的壓力測試時，便是痛苦的開始。怎麼說呢？因為當面對最後的大量測試，各種大大小小的臭蟲(Bugs)就會原形畢露，一一浮上臺面。而每次問題發生，便要千里迢迢趕到客戶那了解情況、解決問題。如果問題不大倒還好，一旦問題嚴重，被客戶關到三更半夜也是常有的事，更誇張的還必須每天都去報到。所以，為避免車程來回的時間和人力浪費，是否有可以遠端連線做處理呢？便思考起這問題。 雖然這些機器通常都不會有真實 IP，客戶也不會為了我們特別請 MIS 去開啟 NAT 或防火牆，但還好 SSH 提供了反向(Reverse)的機制讓我們可以連進去。其做法就是讓在客戶那的系統，透過 SSH 先連回我們自家有真實 IP 的主機，然後建立反向的通道即可。如此，我們便可從自家的主機，從 SSH 連回放在客戶那的系統。 實際的操作步驟： # 首先，在客戶那理的機器下指令連回我們自己的 Server，並設定自己 Server 上的 12345 port 會對應到幾器上的 SSH port ssh -NfR 12345:localhost:22 fred@myhost.com # 然後在 myhost 的機器上連自己的 12345 port，就可以連回在客戶那的機器 ssh localhost -p 12345 後記 可以將建立 Reverse SSH tunnel 的命令設定在開機後執行，並且透過設定 ssh config 讓斷線時自動重連，如此就可以確保 SSH 連線不會中斷。此外，若是客戶端那的機器是處於完全無法對外連線的環境，則可以考慮使用 3G 網卡，並將網卡暫時借放於客戶那，然後等結案後再取回，雖然 3G 通訊月租不便宜，但和經常來回的通勤費和時間花費相比，可滑算多了。
繼續閱讀