Re: [討論] 令人印象深刻的遞迴問題？
※ 引述《yauhh (喲)》之銘言：
: ※ 引述《purpose (purpose)》之銘言：
: : 看到有人在板上找遞迴題目，說要拿來練習。
: : 這讓我想到以前上課時，學校老師提過一個考古題，關於股票買賣的：
: : 若有某公司的股價 double price[] = {55.39, 109.23, 48.29, 81.59,
: : 81.58, 105.53, 94.45, 12.24};
: : 其中 55.39 表示第一天的價格、109.29 為第二天的價格。
: : 不能在同一天同時進行購買與販賣。
: : 寫一個「遞迴函數」，用來求出獲利最大的買賣方式。
: : 當初想很久都沒想到，看到公佈的答案後，又覺得確實合理，所以讓我印象深刻。
假設前面n個存在一個比較好的交易
第i個時間買si 第k個時間賣sk, 價差sk-si k>i
檢查第n+1個時間點是否可以賣
(不考慮買,因為你不知道會不會有n+2的時間點)
(如果可以賣,就把i,k的值換掉)
只要在前面n個多存一個最小值 min_n 就可以達到O(n)
應該就是遞迴的思考了吧？
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 223.139.161.188
→
04/04 00:24, , 1F
04/04 00:24, 1F
→
04/04 10:06, , 2F
04/04 10:06, 2F
→
04/04 11:12, , 3F
04/04 11:12, 3F
→
04/04 11:28, , 4F
04/04 11:28, 4F
→
04/04 11:29, , 5F
04/04 11:29, 5F
→
04/04 11:36, , 6F
04/04 11:36, 6F
→
04/04 11:37, , 7F
04/04 11:37, 7F
→
04/04 11:37, , 8F
04/04 11:37, 8F
討論串 (同標題文章)