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

看板C_and_CPP作者purpose (purpose)時間13年前 (2011/03/31 13:18)推噓18(18推 0噓 29→)

留言47則, 15人參與討論串1/9 (看更多)

看到有人在板上找遞迴題目，說要拿來練習。這讓我想到以前上課時，學校老師提過一個考古題，關於股票買賣的：若有某公司的股價 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

03/31 13:43, , 1^F

03/31 13:43, 1^F

推

attomahawk

03/31 13:45, , 2^F

03/31 13:45, 2^F

推

attomahawk

03/31 13:49, , 3^F

03/31 13:49, 3^F