Re: [討論] 令人印象深刻的遞迴問題?
我真是越來越糟糕了,拿掉 for 迴圈會快許多。
執行結果一樣。
程式碼:http://paste.plurk.com/show/414616/
========================================================================
如果,我是說如果,不考慮 performance。
左買右賣,每一個價錢只有買,賣,不做動作三種可能。
進出場可超過一次。
我選擇 dfs,因為 coding 簡單容易除錯。
程式碼:http://paste.plurk.com/show/414602/
執行結果:
158.97
55.39 buy
109.23 sell
48.29 buy
81.59 buy
81.58 buy
105.53 sell
94.45 pass
12.24 pass
如果考慮同一個價錢可賣掉之前的股份又買進目前的價位,
就變得複雜許多,自行研究吧。
※ 引述《curist (好問題..)》之銘言:
: ※ 引述《Ohwil ( )》之銘言:
: : 假設前面n個存在一個比較好的交易
: : 第i個時間買si 第k個時間賣sk, 價差sk-si k>i
: : 檢查第n+1個時間點是否可以賣
: : (不考慮買,因為你不知道會不會有n+2的時間點)
: : (如果可以賣,就把i,k的值換掉)
: : 只要在前面n個多存一個最小值 min_n 就可以達到O(n)
: : 應該就是遞迴的思考了吧?
: 哇..再來獻醜一次,這次用Ohwil大大的演算法,應該寫對了吧?
: #include <stdio.h>
: #include <stdlib.h>
: int main()
: {
: double prices[] = {55.39, 109.23, 48.29, 81.59,
: 81.58, 105.53, 94.45, 12.24};
: double min = 9999, max_diff = 0;
: int i;
: for(i = 0; i < 8; i++) {
: if(prices[i] < min) {
: min = prices[i];
: }
: if((prices[i] - min) > max_diff) {
: max_diff = prices[i] - min;
: }
: }
: printf("%lf\n", max_diff);
: return 0;
: }
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.43.118.223
→
04/04 21:37, , 1F
04/04 21:37, 1F
→
04/04 21:38, , 2F
04/04 21:38, 2F
※ 編輯: bleed1979 來自: 114.43.118.223 (04/04 21:45)
→
04/04 21:52, , 3F
04/04 21:52, 3F
→
04/04 21:53, , 4F
04/04 21:53, 4F
推
04/04 22:36, , 5F
04/04 22:36, 5F
推
04/05 00:16, , 6F
04/05 00:16, 6F
→
04/05 00:17, , 7F
04/05 00:17, 7F
→
04/05 00:30, , 8F
04/05 00:30, 8F
→
04/05 00:57, , 9F
04/05 00:57, 9F
→
04/05 02:41, , 10F
04/05 02:41, 10F
討論串 (同標題文章)