推 SHANGOYANYI:河內塔跟費伯納西數列應該都是經典 03/31 13:43
推 attomahawk:推樓上，小弟大一時被 河內塔 搞的團團轉。 03/31 13:45
推 attomahawk:資料結構 的 Binary Search 和 Maze(走迷宮)。 03/31 13:49
推 shiengchyi:再頭痛一點的 - 8皇后問題 03/31 14:06
→ shiengchyi:另外像是組合數學裡面的 排列組合計算 03/31 14:07
推 attomahawk:Knight Tour(騎士旅行)。 03/31 14:09
推 byby615:請問在這個問題裡 是要求每天都要買進或賣出嗎? 03/31 15:21
推 ledia:是指固定初始成本的最大獲利嗎? 03/31 15:47
推 ledia:看來是只能進場一次 03/31 15:53
→ purpose:對只能挑一天買、並挑另一天賣，該次買賣差價最大為答案 03/31 16:07
→ purpose:以上面的 double price[] 為例，答案是在第三天 48.29 時 03/31 16:09
→ purpose:買入，並在第六天 105.53 時賣出，此時單次交易利潤最大 03/31 16:10
推 Ebergies:是喔那為啥要 "不能在同一天同時進行購買與販賣" 03/31 20:10
→ Ebergies:同一天買賣一定不是最大穫利啊 03/31 20:11
→ yauhh:怎麼回事,這幾天是遞迴大爆發嗎? 03/31 20:21
推 attomahawk:小弟 猜測 原題目的 "不能在同一天又買又賣" 的意思為: 03/31 20:21
→ attomahawk:不能在同日 賣出 之前已經買的股票 ， 03/31 20:22
→ attomahawk:又 買進 當日價格 的 股票。 03/31 20:23
→ attomahawk:例如： 55.39 買進 ， 81.59 賣出 03/31 20:23
→ attomahawk: 81.59 買進 ， 105.53 賣出 。 03/31 20:24
→ attomahawk:這種操作 是 不被題目允許的。 03/31 20:24
推 Ebergies:問題在於上面的推文指出只能進場一次... lol 03/31 20:27
→ attomahawk:感謝E大提醒，那這樣我就不知道了。 @@" 03/31 20:29
推 Ebergies:簡單的想法是看兩次, 第一次記錄一路上的最小值 03/31 20:39
→ Ebergies:邊紀錄邊以現在看到的數字減掉已知最小的數字存另一陣列 03/31 20:39
→ Ebergies:之後在另一陣列找最大值為解 03/31 20:40
→ tropical72:感覺只要掃一次即可 03/31 20:41
→ purpose:回E大，那應該是我的錯，原本的題目沒抄下來，照印象打的 03/31 20:43
推 Ebergies:LOL 也是, 直接合併在一起比最大值就可以了 03/31 20:43
※ 編輯: purpose 來自: 124.8.139.40 (03/31 20:56)
推 sand1050:遞回解數獨算不算~ 04/01 00:25
→ loveme00835:我的想法是輸入砍到剩極大/極小值, 皆作排序, 極小搭 04/01 04:06
→ loveme00835: 最 04/01 04:07
→ loveme00835:最大, 次大, 第三大...等, 直到找到合法序對的為止, 04/01 04:08
→ loveme00835:再來是次小也作一次, 直到找出的利潤沒有進步空間為止 04/01 04:09
→ loveme00835:價格可以離散化再做排序O(n), 找序對最差O(n^2) 04/01 04:11
→ loveme00835:後來想到排序要考慮到鍵值的可能性, 所以應該O(nlogn) 04/01 04:14
→ loveme00835:不過再多想幾次還是會通的啦! 面試題目沒有兩小時考得 04/01 04:19
→ loveme00835:出來嗎? 04/01 04:19
推 aecho:股票可以允許知道未來的價格做排序嗎？ 04/01 06:36
推 aecho:看來是不能排序，不能後天買進今天要賣的股票~這個沒有放空 04/01 06:50
→ purpose:數獨的規則我不太清楚，但課本沒提過，應該算 04/01 09:23
→ purpose:面試，如果我第一次碰到，應該就是掛了。這題要解遞迴，我 04/01 09:24
→ purpose:們老師說是考古題，我也沒辦法拿分，我們老師倒是說他當場 04/01 09:24
→ purpose:就解出來...經驗老到加上本身強，解題就是快 04/01 09:25
推 e29895037ric:用遞迴算多階行列式的值 04/01 11:16
推 FOXSMALL:中文的敘述要加入，只能買和賣各一次 04/01 18:29
→ bobo0120:比較像是DP吧 04/02 07:27
> -------------------------------------------------------------------------- <
作者: yauhh (喲) 看板: C_and_CPP
標題: Re: [討論] 令人印象深刻的遞迴問題？
時間: Fri Apr 1 01:35:18 2011
※ 引述《purpose (purpose)》之銘言：
: 看到有人在板上找遞迴題目，說要拿來練習。
: 這讓我想到以前上課時，學校老師提過一個考古題，關於股票買賣的：
: 若有某公司的股價 double price[] = {55.39, 109.23, 48.29, 81.59,
: 81.58, 105.53, 94.45, 12.24};
: 其中 55.39 表示第一天的價格、109.29 為第二天的價格。
: 不能在同一天同時進行購買與販賣。
: 寫一個「遞迴函數」，用來求出獲利最大的買賣方式。
: 當初想很久都沒想到，看到公佈的答案後，又覺得確實合理，所以讓我印象深刻。
這個問題, 輸入的數字可以轉換為數差序列:
{55.39, 109.23, 48.29, 81.59, 81.58, 105.53, 94.45, 12.24}
=> 53.84 -60.94 33.3 -0.01 23.95 -11.08 -82.21
然後問題型式轉為要從以上數差序列中, 找出最大的子序列總和.
號稱 Max Segment Sum. (寫股票軟體的朋友們注意了!!)
所以像你提到的 Stackoverflow.com 最佳解法,以及我這樣子寫:
struct Suggest {
int i_l, i_h;
float running_sum, max_accumulating, min_point;
};
struct Suggest* suggest(float* arr, int len) {
struct Suggest* result;
result = (struct Suggest*) malloc(sizeof(struct Suggest));
if (len <= 1) {
result->i_l = 0;
result->i_h = 0;
result->running_sum = 0;
result->max_accumulating = -999999;
result->min_point = 999999;
} else {
float gap, old_sum;
result = suggest(arr+1, len-1);
result->i_l++;
result->i_h++;
gap = *(arr+1) - *arr;
old_sum = result->running_sum;
result->running_sum = result->running_sum + gap;
if (result->running_sum > result->max_accumulating) {
result->i_l = 0;
if (old_sum < result->min_point) {
result->i_h = 1;
result->min_point = old_sum;
}
result->max_accumulating = result->running_sum;
}
}
return result;
}
所做的動作不外乎二件事: 1. 每一步試著累加 segment 差值. 2. 每一步都判斷
這一次的累加是否會將差值總和拉到 max. (所以叫作 max --- segment --- sum,
真漂亮.)
我的作法是純粹累加差值,看哪個累計差值最高,就可以把左邊界推到最極限.
然後在左邊界可以往前推的前提下,看看右邊界可不可以往前推.
我的左邊界就是低點,右邊界就是高點,因為遞迴的關係,所以是先從陣列右邊開始算,
陣列計算方向跟 Stackoverflow.com 的網友用迴圈解的方向不一樣.
但是,不管是用遞迴或迴圈寫成這樣,有個壞處是: 我不知道程式是不是真的很對.
因為邏輯上的線索,我的線索只有從頭到尾差值累積總和最高點應該是下限了,並且在
下限界定的前提中,差值的累積和通過最低點應該就是上限.
這樣的解法是所謂很簡潔是沒錯,但是簡潔到不知所以然或不確定所以然,是我很不敢
領教了.
> -------------------------------------------------------------------------- <
作者: tropical72 (藍影) 看板: C_and_CPP
標題: Re: [討論] 令人印象深刻的遞迴問題？
時間: Fri Apr 1 17:53:00 2011
※ 引述《yauhh (喲)》之銘言：
: 我的作法是純粹累加差值,看哪個累計差值最高,就可以把左邊界推到最極限.
: 然後在左邊界可以往前推的前提下,看看右邊界可不可以往前推.
: 我的左邊界就是低點,右邊界就是高點,因為遞迴的關係,所以是先從陣列右邊開始算,
它「應」是對的，之前看過之「類似」題：
Q : 給定一整數數列，有正有負，ex: [3 2 8 9 -25 5 8 4 4 -3 5 3 -10]
要求「連續最大總合」之其合應為多少？若連續最大總合 <=0 則輸出 0
ex1: 3+2+8 = 13
ex2: 5+8+4 = 17
ex3: 5+8+4+...+3=26(max)
-----
sol:
(1) 一個一個慢慢掃
(2) 當 cur_sum < 0 時，將 cur_sum 歸 0，正值時累加
(3) 若 cur_sum > max_sum，取代
num 3 2 8 9 -25 5 8 4 4 -3 5 3 -10
cur_sum 3 5 13 22 0(-3) 5 13 17 21 18 23 26 16
max_sum 3 5 13 22 22 22 22 22 22 22 23 26 26
----
coding:
for(i=0; i!=sizeof(array)/ sizeof(int); ++i){
cur_sum+=array[i];
if(cur_sum<0) cur_sum=0;
if(cur_sum>max_sum) max_sum = cur_sum;
}
printf("%d\n", max_sum);
----
lemma1: 第一次看到原題時, 聯想到是這題，直覺是和 yauhh 相同做法。
lemma2: 這題有進階題, 有待討論 (也不難解) : 若為 cicle link 非 array？
lemma3: 這題在「教育部資訊軟體人才培育先導計畫」第二次競賽裡面似乎也有
http://algorithm.csie.ncku.edu.tw/ETPC/
lemma4: purpose 所提供之題目，「似乎」是將程式碼再紀錄
start_max_pos, end_max_pos，「加以變型」後可得，不知是否有意會錯。
lemma5: 吾人 power 不夠，實在想不透如何限定用 recursive 實做。
> -------------------------------------------------------------------------- <
作者: curist (好問題..) 看板: C_and_CPP
標題: Re: [討論] 令人印象深刻的遞迴問題？
時間: Fri Apr 1 22:56:59 2011
試解一下
#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 = 0;
int i = 0, j = 7;
while(i < j) {
if(prices[i] < min)
min = prices[i];
if(prices[j] > max)
max = prices[j];
++i;
--j;
}
printf("%lf\n", max - min);
return 0;
}
> -------------------------------------------------------------------------- <
作者: kevingwn (如雲如風的人生) 看板: C_and_CPP
標題: Re: [討論] 令人印象深刻的遞迴問題？
時間: Sat Apr 2 12:52:32 2011
咦...題目不是要求用遞迴嗎?
原po的作法看不太懂,貼出比較直觀的寫法(就是把迴圈轉換成遞迴orz)
void recursion(double* first,
double* last,
double* best_buy,
double* best_sell)
{
if (first != last)
{
double max_profit;
double buy_price;
recursion(first + 1, last, best_buy, best_sell);
max_profit = *best_sell - *best_buy;
buy_price = *first;
while (++first != last)
{
double sell_price = *first;
double pred_profit = sell_price - buy_price;
if (max_profit < pred_profit)
{
*best_buy = buy_price;
*best_sell = sell_price;
max_profit = pred_profit;
}
}
}
else
{
*best_buy = 0;
*best_sell = 0;
}
}
int main()
{
double price[] = {55.39, 109.23, 48.29, 81.59, 81.58, 105.53, 94.45, 12.24};
double best_buy, best_sell;
recursion(
price, price + sizeof(price) / sizeof(price[0]),
&best_buy, &best_sell);
printf("best buy:\t%f\nbest sell:\t%f\nmax profit:\t%f\n",
best_buy, best_sell, best_sell - best_buy);
return 0;
}
> -------------------------------------------------------------------------- <
作者: curist (好問題..) 看板: C_and_CPP
標題: Re: [討論] 令人印象深刻的遞迴問題？
時間: Mon Apr 4 20:17:06 2011
※ 引述《Ohwil ( )》之銘言：
: ※ 引述《yauhh (喲)》之銘言：
: 假設前面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;
}
> -------------------------------------------------------------------------- <
作者: bleed1979 (十三) 看板: C_and_CPP
標題: Re: [討論] 令人印象深刻的遞迴問題？
時間: Mon Apr 4 21:32:33 2011
我真是越來越糟糕了，拿掉 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;
: }
> -------------------------------------------------------------------------- <
作者: stimim (qqaa) 看板: C_and_CPP
標題: Re: [討論] 令人印象深刻的遞迴問題？
時間: Tue Apr 5 00:11:50 2011
: ========================================================================
: 如果，我是說如果，不考慮 performance。
: 左買右賣，每一個價錢只有買，賣，不做動作三種可能。
: 進出場可超過一次。
: 我選擇 dfs，因為 coding 簡單容易除錯。
: 程式碼：http://paste.plurk.com/show/414602/
: 如果考慮同一個價錢可賣掉之前的股份又買進目前的價位，
: 就變得複雜許多，自行研究吧。
先考慮一下我們要不要在同一先賣再買：
(a)如果在某一天買，代表在接下來的日子裡，至少有一天的價格會超過今天
（不然一定虧錢）
(b)如果在某一天賣，代表在接下來的日子裡，價格不會更高了
（不然過幾天賣賺更多）
可以看到兩者不會同時發生，因此在這個問題中我們不用考慮同一天買＋賣
那麼問題就簡單多了，要考慮的就是：在哪幾天賣？
由(b)可知，如果在第i天賣，則i滿足：
for all j > i, prices[j] <= prices[i] (有沒有 = 應該不影響最後結果)
程式碼在此： http://codepad.org/3XhHtMWx
決定要不要買是在第 12 ~ 14 行，剩下的是算賺多少還有輸出訊息。
如果有錯誤之處還請大家幫忙指正。
(如果還要考慮手中的資本、手續費可能會很好玩)