Re: [討論] 令人印象深刻的遞迴問題？
※ 引述《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 的網友用迴圈解的方向不一樣.
但是,不管是用遞迴或迴圈寫成這樣,有個壞處是: 我不知道程式是不是真的很對.
因為邏輯上的線索,我的線索只有從頭到尾差值累積總和最高點應該是下限了,並且在
下限界定的前提中,差值的累積和通過最低點應該就是上限.
這樣的解法是所謂很簡潔是沒錯,但是簡潔到不知所以然或不確定所以然,是我很不敢
領教了.
--
/yau
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.160.114.217
→
04/01 09:26, , 1F
04/01 09:26, 1F
→
04/01 11:12, , 2F
04/01 11:12, 2F
→
04/01 13:48, , 3F
04/01 13:48, 3F
討論串 (同標題文章)