Re: [新聞] 超狂數學教授活用演算法 高鐵分段買票竟較便宜消失

看板Gossiping作者時間6年前 (2017/08/15 18:38), 6年前編輯推噓211(214推 3噓 21→)
留言238則, 224人參與, 最新討論串11/12 (看更多)
大家好， 我是這篇文章的作者，今天我的Line跟FB都費這則新聞洗板了… 身為鄉民這麼久，第一次在八卦版發言， Unimath是陳宏賓教授發起的網路期刊，旨在刊登一些科普文章， 告訴大眾數學、科學在生活中處處都是， 而且學校學的數學，常常都能應用到生活上。 期刊中有不少教授寫了很多不錯的文章，有興趣的人可以看看。 回到主題，高鐵拆票是去年寫的文章，蘋果記者應該是最近看到，所以想寫篇專欄吧！ 我目前在歐洲，昨天才跟蘋果的記者通電話，沒想到今天就刊出來了。 拆票有可能變便宜，我想很多人很早就知道了， 如鄉民講的，只要利用加法，還有比較大小，就可以知道了， 沒錯，會這樣想的話，表示已經可以把數學用到生活中了。 但更進一步想， 1.有時拆票又會變貴，到底為什麼？是不是高鐵的Bug？ 2.又怎麼拆會最便宜？ 不管答不答的出來，會這樣想的人，就是有著數學思維，Unimath的目的就達到了。 那本篇文章重點就是幫大家回答這兩個問題： 原文：https://goo.gl/yQi9GE 1. 因為「誤差是會累加的」，高鐵票的計算方式是四捨五入到十元，有誤差，所以分越多段的誤差就會越大。 2. 但怎麼拆才會「最佳」，這就要靠電腦的幫忙了。(演算法用在哪？後面會講) 而記者把重點放錯了，都著重在省20元，去售票機買不會影響別人，之類的。 而且下的標題還很聳動！ (這當然不能怪記者，因為不聳動的標題，沒人要點進去看！但至少重點要放對啊…) 大致上是這樣！其實還蠻高興大家對這個主題有興趣的， 若有什麼好的科普主題或文章，歡迎投稿Unimath，跟大家一起分享。 - 師大數學系 郭君逸 下面是一些比較boring的部份，順便回答一些鄉民的問題，沒興趣的話可以直接跳過！ 1. 演算法用在哪？不是只要加法就可以了嗎？ 會這樣問的人，應該是沒碰過程式。 知道怎麼拆票的話，當然是直接把每一段票價加起來即可。只用到加法。 但問題就是不知道怎麼拆，有時拆了還會變貴。 一個簡單的想法就是，A到F中間有B,C,D,E站的話，每個站要分不分，總共2^4種切法都去試， 這樣就是一種演算法，但這樣的暴力法，效率很差(指數時間)， 當中間的站點一多(例如算台鐵的分票)，電腦也算不完。 那要怎麼省時間呢？我觀察到了中間有很多重複計算的部份，例如： 計算A到F站的話，在試切C點時，也會把AC與CF的最佳解都算過了，後來就不用再重複算。 所以我就採取空間換取時間的方法(Dynamic Programming)把算過的存起來，就不用再重算， 這樣的演算法就會快很多，即時算台鐵的所有站的分票，也是按個Enter馬上就算完了。 整個演算法雖然是我自己想的，後來還是查了一下書， 發現在演算法書中，最短路徑一章就有很多類似的東西， 然後我的演算法跟Dijkstra無迴圈的版本很像。 (其實還是有點不同，只是原理相同， 有興趣的同學可以自己寫程式列出所有站點之間的分票方式，比較能體會其奧妙。程式其實很短。) 2. 誤差疊加，很重要，求學時老師每次講，台下的我聽了都沒感覺， 明明多項式計算就代進去就好，為什麼還要改成巢狀計算； 矩陣就直接乘就好，為什麼還要對角化、Jordan Form…… 然後就會在台下說，學這個到底要幹嘛，多此一舉， 後來等到自己遇到麻煩了，才知道自己當時的無知。 3. 時間成本很重要，誰會省這20元。 這當然是這樣，現在比較忙，時間都不夠用，我自己每次坐高鐵都坐直達的，誰想每站在那裡換位置！ 省錢只是文章的手段，讓讀者願意點進來看，但重點不在此，不要再被記者拉著走了。 4. 數學教授整天算一些沒用的東西。 其實有沒有用每個人都不同， 否則籃球員為什麼要一直把球丟到籃框裡？ 畫家為何要畫畫？不就照起來，再用一些濾鏡就好了？ 這都是他們的工作、成果、興趣。 自然會有欣賞的人，自然也都有它的價值在。 5. 只要會加減乘除就可以活的好好的，為什麼要學這麼多？ 這老生常談了。這就讓大家幫忙回答吧！ 連加減都不會，也是可以活的好好的。 上了幾次新聞後，發現，其實水果算是新聞媒體裡還不錯的，他們會主動去採訪、訪問、找新聞， 然後很多媒體都是看到水果發布的新聞後，自己再改寫後再發布。 之前辦魔術方塊比賽，也沒發布新聞稿，水果記者前一天就會來訪問，比賽當天新聞就會出來， 其他家的記者看到新聞才來採訪，比賽都快比完了… 至於新聞內容有時會斷章取義，或是技術方面有寫錯，這是人人皆知的， 因為大家都是站在自己熟悉的專業在看新聞，但記者卻是要寫所有領域的東西， 錯誤是難免。(當然有些離普的，都被網友整理出來。) 不過，在大家關注的主題上， 有瑕疵的新聞，反而點擊率會更高，這是無庸置疑的。 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 83.216.94.104 ※ 文章網址: https://www.ptt.cc/bbs/Gossiping/M.1502793483.A.BE3.html
→
08/15 18:38, , 1F
沒空
08/15 18:38, 1F
→
08/15 18:38, , 2F
沒空
08/15 18:38, 2F
推
08/15 18:38, , 3F
太早
08/15 18:38, 3F
推
08/15 18:39, , 4F
可惜你現在po只會被洗掉
08/15 18:39, 4F
噓
08/15 18:39, , 5F
無聊
08/15 18:39, 5F
推
08/15 18:39, , 6F
專業 可是沒空
08/15 18:39, 6F
→
08/15 18:39, , 7F
沒空
08/15 18:39, 7F
推
08/15 18:39, , 8F
我頭好痛 停電你在算數學 = =
08/15 18:39, 8F
推
08/15 18:40, , 9F
可惜
08/15 18:40, 9F
推
08/15 18:40, , 10F
幫你推推 但你po錯時間了
08/15 18:40, 10F
推
08/15 18:40, , 11F
沒空
08/15 18:40, 11F
推
08/15 18:41, , 12F
台灣停電中
08/15 18:41, 12F
推
08/15 18:42, , 13F
專業推
08/15 18:42, 13F
推
08/15 18:42, , 14F
您有電嗎?
08/15 18:42, 14F
推
08/15 18:43, , 15F
時候不對
08/15 18:43, 15F
推
08/15 18:44, , 16F
怎樣從台北到高雄最省錢？
08/15 18:44, 16F
推
08/15 18:44, , 17F
推老師！魔術方塊台灣第一人！
08/15 18:44, 17F
推
08/15 18:44, , 18F
幫推一下
08/15 18:44, 18F
推
08/15 18:44, , 19F
難得好文..
08/15 18:44, 19F
推
08/15 18:45, , 20F
推
08/15 18:45, 20F
推
08/15 18:45, , 21F
沒空的估計沒學過algo
08/15 18:45, 21F
推
08/15 18:45, , 22F
推
08/15 18:45, 22F
推
08/15 18:46, , 23F
推
08/15 18:46, 23F
推
08/15 18:46, , 24F
推
08/15 18:46, 24F
推
08/15 18:46, , 25F
推
08/15 18:46, 25F
推
08/15 18:47, , 26F
沒空
08/15 18:47, 26F
推
08/15 18:47, , 27F
好文
08/15 18:47, 27F
推
08/15 18:47, , 28F
這時候發認真文不會覺得很幹嗎？
08/15 18:47, 28F
推
08/15 18:47, , 29F
推 郭大
08/15 18:47, 29F
推
08/15 18:49, , 30F
推
08/15 18:49, 30F
推
08/15 18:49, , 31F
幫你推拉
08/15 18:49, 31F
推
08/15 18:49, , 32F
推
08/15 18:49, 32F
→
08/15 18:49, , 33F
...
08/15 18:49, 33F
推
08/15 18:50, , 34F
讚
08/15 18:50, 34F
推
08/15 18:50, , 35F
推教授!!
08/15 18:50, 35F
推
08/15 18:51, , 36F
專業
08/15 18:51, 36F
推
08/15 18:51, , 37F
推一下
08/15 18:51, 37F
推
08/15 18:51, , 38F
推認真文
08/15 18:51, 38F
推
08/15 18:51, , 39F
推 噓記者
08/15 18:51, 39F
還有 160 則推文
推
08/16 02:26, , 200F
推
08/16 02:26, 200F
推
08/16 02:33, , 201F
推 曾經上過教授的課 好棒的課
08/16 02:33, 201F
推
08/16 03:53, , 202F
推！
08/16 03:53, 202F
推
08/16 04:57, , 203F
推
08/16 04:57, 203F
推
08/16 06:20, , 204F
我還不推個郭大啊！
08/16 06:20, 204F
推
08/16 07:59, , 205F
之前和水果的高層談過 水果除了聳動外 其實採訪是最認真的
08/16 07:59, 205F
→
08/16 07:59, , 206F
規矩也比其他大報嚴謹多
08/16 07:59, 206F
推
08/16 08:01, , 207F
寫的不錯啊!!
08/16 08:01, 207F
推
08/16 08:31, , 208F
推籃球例子 讓我笑了!!!
08/16 08:31, 208F
推
08/16 09:35, , 209F
推
08/16 09:35, 209F
推
08/16 09:39, , 210F
雖然我滿不認同那種只是為了引起興趣而無實益的教學
08/16 09:39, 210F
→
08/16 09:40, , 211F
那些就是從小到大的8成以上的教育歷程，對未來工作通常無用
08/16 09:40, 211F
→
08/16 09:41, , 212F
教學是可以以實益為出發點，這樣學生會更有動力學
08/16 09:41, 212F
→
08/16 09:42, , 213F
認同你的水果報確實是比較有良心的報
08/16 09:42, 213F
→
08/16 09:43, , 214F
就是因為記者要跨領域採訪，所才制度上才賦予採訪證的權力
08/16 09:43, 214F
→
08/16 09:44, , 215F
讓記者以優於平常人的權力進入核心區域採訪，這是合理的
08/16 09:44, 215F
→
08/16 09:46, , 216F
學理上叫社會第四權，結果現在卻常被濫用或甚至怠於行使
08/16 09:46, 216F
→
08/16 09:47, , 217F
反正改寫蘋果的報導就好，何必辛苦直接採訪，真是亂源...
08/16 09:47, 217F
推
08/16 09:53, , 218F
教授確實整天都算一些沒用的啊...上過課的都知道
08/16 09:53, 218F
→
08/16 09:55, , 219F
因為教授大多拿書本上的例子來routine教學，很無趣
08/16 09:55, 219F
→
08/16 09:57, , 220F
真正好玩又有實益的是接國科會計畫，且戰且學又有錢領
08/16 09:57, 220F
推
08/16 09:57, , 221F
推一下學長ＸＤ
08/16 09:57, 221F
→
08/16 09:58, , 222F
當給學生一個可預見的未來，原文書再來幾本都啃得甘之如飴
08/16 09:58, 222F
推
08/16 11:38, , 223F
推推
08/16 11:38, 223F
推
08/16 13:27, , 224F
推
08/16 13:27, 224F
推
08/16 13:39, , 225F
噓那個推啥沒空的人= =
08/16 13:39, 225F
推
08/16 13:53, , 226F
優文推推 雖然數學讓人頭痛 但師大君逸必須推
08/16 13:53, 226F
推
08/16 15:00, , 227F
郭大 推一個
08/16 15:00, 227F
推
08/16 19:22, , 228F
郭教授必推！！！
08/16 19:22, 228F
推
08/16 19:56, , 229F
郭大!
08/16 19:56, 229F
推
08/16 20:27, , 230F
08/16 20:27, 230F
推
08/16 22:45, , 231F
朝聖推
08/16 22:45, 231F
推
08/17 08:34, , 232F
推
08/17 08:34, 232F
推
08/17 22:33, , 233F
哦哦
08/17 22:33, 233F
推
08/18 05:50, , 234F
推！
08/18 05:50, 234F
推
08/18 06:07, , 235F
推
08/18 06:07, 235F
推
08/18 06:09, , 236F
推師大Davidguo!!
08/18 06:09, 236F
※ 編輯: DavidGuo (180.214.185.208), 08/19/2017 02:06:45
推
08/26 17:51, , 237F
數學系給推
08/26 17:51, 237F
推
11/10 10:21, , 238F
推 自己寫過才知道感動處
11/10 10:21, 238F
‣ 更多 DavidGuo 的文章
文章代碼(AID): #1PaiyBlZ (Gossiping)
討論串 (同標題文章)
完整討論串 (本文為第 11 之 12 篇)：
排序： 最舊先 | 最新先 | 留言數
在新視窗開啟完整討論串 (共12篇)
‣ 更多 DavidGuo 的文章
文章代碼(AID): #1PaiyBlZ (Gossiping)