[討論] 令人印象深刻的遞迴問題？

[purpose (purpose)]

看到有人在板上找遞迴題目，說要拿來練習。

這讓我想到以前上課時，學校老師提過一個考古題，關於股票買賣的：

        若有某公司的股價 double price[] = {55.39, 109.23, 48.29, 81.59,
                                           81.58, 105.53, 94.45, 12.24};

        其中 55.39 表示第一天的價格、109.29 為第二天的價格。
        不能在同一天同時進行購買與販賣。

        寫一個「遞迴函數」，用來求出獲利最大的買賣方式。

當初想很久都沒想到，看到公佈的答案後，又覺得確實合理，所以讓我印象深刻。

不知道大家有沒有碰過什麼遞迴問題，也讓你印象深刻的，不妨交流一下吧。

########

就算不論遞迴，這個股票問題本身很單純，敘述沒有幾行，但是卻有很多種解法。
其中，最優雅的解法是用非遞迴寫的。其背後需要的是，全面的分析並且整合。

像這麼有意思的問題，總覺得應該很有名，不會就叫考古題吧？
不知道有沒有專門的稱呼呢？

謝謝回答


在 stackoverflow.com 有看到外國人討論這個問題，說是面試的題目。
然後底下的網友在猜是不是知名公司 Bloomberg (彭博) 的面試。網址在：

http://stackoverflow.com/questions/1663545/find-buy-sell-prices-in-array-of-
stock-values-to-maximize-positive-difference

上面太長了， 短網址在：http://tinyurl.com/yguddsv

該網址裡面有問題的解答，包含最佳解，還不想看解答，要自己想看看的，先別點進去！


股票問題，我之前寫的非遞迴版本，不是最佳解，也不是最爛的解法：
http://codepad.org/kfSdX64d


股票買賣的遞迴解：

        作答提示 (先想過，再看提示吧)：

                http://ppt.cc/lVKy

        參考答案 (不想猜了，可以看這)：

                http://codepad.org/NlcM35W1


03/31 PM 08:50 修文補充

題目沒有描述清楚，跟版友道歉，以下轉貼外國人敘述的題目說明

Given a single array of real values, each of which represents the stock value
of a company after an arbitrary period of time, find the best buy price and
its corresponding best sell price (buy low, sell high).

To illustrate with an example, let's take the stock ticker of Company Z:

55.39 109.23 48.29 81.59 105.53 94.45 12.24

Important to note is the fact that the array is "sorted" temporally - i.e. as
time passes, values are appended to the right end of the array. Thus, our buy
value will be (has to be) to the left of our sell value.

(in the above example, the ideal solution is to buy at 48.29 and sell at
105.53)

也謝謝大家提供遞迴問題

另外詢問有沒有教科書上沒提過，但是在你們工作、做專案的時候碰到，
讓你寫完這個遞迴後印象深刻的？小弟想長長見識，謝謝



--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 124.8.139.40
推 SHANGOYANYI:河內塔跟費伯納西數列應該都是經典
推 attomahawk:推樓上，小弟大一時被 河內塔 搞的團團轉。
推 attomahawk:資料結構 的 Binary Search 和 Maze(走迷宮)。
推 shiengchyi:再頭痛一點的 - 8皇后問題
→ shiengchyi:另外像是組合數學裡面的 排列組合計算
推 attomahawk:Knight Tour(騎士旅行)。
推 byby615:請問在這個問題裡 是要求每天都要買進或賣出嗎?
推 ledia:是指固定初始成本的最大獲利嗎?
推 ledia:看來是只能進場一次
→ purpose:對只能挑一天買、並挑另一天賣，該次買賣差價最大為答案
→ purpose:以上面的 double price[] 為例，答案是在第三天 48.29 時
→ purpose:買入，並在第六天 105.53 時賣出，此時單次交易利潤最大
推 Ebergies:是喔那為啥要 "不能在同一天同時進行購買與販賣"
→ Ebergies:同一天買賣一定不是最大穫利啊
→ yauhh:怎麼回事,這幾天是遞迴大爆發嗎?
推 attomahawk:小弟 猜測 原題目的 "不能在同一天又買又賣" 的意思為:
→ attomahawk:不能在同日 賣出 之前已經買的股票 ，
→ attomahawk:又 買進 當日價格 的 股票。
→ attomahawk:例如： 55.39 買進 ， 81.59 賣出
→ attomahawk:       81.59 買進 ， 105.53 賣出 。
→ attomahawk:這種操作 是 不被題目允許的。
推 Ebergies:問題在於上面的推文指出只能進場一次... lol
→ attomahawk:感謝E大提醒，那這樣我就不知道了。 @@"
推 Ebergies:簡單的想法是看兩次, 第一次記錄一路上的最小值
→ Ebergies:邊紀錄邊以現在看到的數字減掉已知最小的數字存另一陣列
→ Ebergies:之後在另一陣列找最大值為解
→ tropical72:感覺只要掃一次即可
→ purpose:回E大，那應該是我的錯，原本的題目沒抄下來，照印象打的
推 Ebergies:LOL 也是, 直接合併在一起比最大值就可以了
※ 編輯: purpose         來自: 124.8.139.40         (03/31 20:56)
推 sand1050:遞回解數獨算不算~
→ loveme00835:我的想法是輸入砍到剩極大/極小值, 皆作排序, 極小搭
→ loveme00835:                                           最
→ loveme00835:最大, 次大, 第三大...等, 直到找到合法序對的為止,
→ loveme00835:再來是次小也作一次, 直到找出的利潤沒有進步空間為止
→ loveme00835:價格可以離散化再做排序O(n), 找序對最差O(n^2)
→ loveme00835:後來想到排序要考慮到鍵值的可能性, 所以應該O(nlogn)
→ loveme00835:不過再多想幾次還是會通的啦! 面試題目沒有兩小時考得
→ loveme00835:出來嗎?
推 aecho:股票可以允許知道未來的價格做排序嗎？
推 aecho:看來是不能排序，不能後天買進今天要賣的股票~這個沒有放空
→ purpose:數獨的規則我不太清楚，但課本沒提過，應該算
→ purpose:面試，如果我第一次碰到，應該就是掛了。這題要解遞迴，我
→ purpose:們老師說是考古題，我也沒辦法拿分，我們老師倒是說他當場
→ purpose:就解出來...經驗老到加上本身強，解題就是快
推 e29895037ric:用遞迴算多階行列式的值
推 FOXSMALL:中文的敘述要加入，只能買和賣各一次
→ bobo0120:比較像是DP吧