Re: [問題] 資工系預習方向

[keke0421 (zrae)]

我們從一個問題開始吧 :)

某國家發行了 a_1,...a_k種不同面額的鈔票

其中a_1 < ....< a_k

問如何將n元 兌換成a1,....,ak 且數量最少?

ex: 假設有 1,4,6元的面額鈔票 將8元兌換成 2個4元的鈔票 是最少的 所以答案是2

但很多人直覺反應會從最大的面額開始換 -> 6,1,1


這是演算法中dynamic programming問題之一


給一個問題 如何用 最快的時間 最少的空間 求出答案 一直都是最根本的問題

很多台清交資工系 都沒辦法做到這點 但這卻是業界需要的人


最快的時間 反應人在使用一項產品時 不喜歡等待

最少的空間 反應在 在行動裝置 並不像桌電擁有 超大的記憶體空間


一堆公司面試的白板題 根本也不限定語言 只是要看你有沒有辦法寫出符合上面

條件的程式碼而已


這就是 【資料結構和演算法】 也就是你應該花最多時間去加強的

練好了 不管寫 mobile / web / iot / embedded / ... 都是受用無窮

除此之外 數學也是非常重要 所以如果你要讀數學 先從 【離散數學】 開始


後面 當然還有 作業系統 和 計算機組織 ...更深入的topic

但現階段 就搞好三科[資料結構] , [演算法] , [離散數學] 就夠了

書 隨便GOOGLE都有人推薦


程式語言只是工具 等你精通一套語言 其他轉換都很快

學一堆語言 工具 框架 卻連一些基本的問題 都用很糟的時間和空間複雜度去解

這種人在業界也不少就是了


小小意見 參考







--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 118.168.22.89
※ 文章網址: https://www.ptt.cc/bbs/SENIORHIGH/M.1457311196.A.9F8.html
※ 編輯: keke0421 (118.168.22.89), 03/07/2016 08:42:45
→ hsnuonly    : 我覺得不要一開始就假設每個人都要做資結演算法
→ hsnuonly    : 很重要 但不是全部 沒有興趣的人更多
→ hsnuonly    : 新手會喜歡那種用套件很容易兜出來 漂漂亮亮的東西
→ hsnuonly    : 一直看command line 很多人會寫不下去
推 youtuuube000: 你舉的例子是greedy吧？
推 wlsh5701    : 這是greedy解吧
推 peter506g   : 他大概是說正解DP 然後舉例中的是greedy這樣吧
推 apocalypses : 同意樓上
推 yqkqknct    : 要講DP用背包問題就好啦XD
→ qwe50120    : 那個硬幣不是背包喔 我看不像greedy
推 tokiya10847 : 硬幣不能greedy解，感覺就是暴力法然後DP
推 petingo     : 突然想到一篇靠北工程師的推薦書單 最後一本是“活
→ petingo     : 著“
推 promiseone  : 不推一下人家以為我看不懂
推 yungjungcghs: 硬幣是用dp吧！背包才是greedy