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

[kevingwn (如雲如風的人生)]

咦...題目不是要求用遞迴嗎?

原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;
}

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 123.204.92.148
推 purpose:您好，關於我貼的遞迴作法，在此補充程式碼的文字說明：
→ purpose:http://ppt.cc/lh_-
→ kevingwn:所以是divide&conquer囉?我頭腦簡單就直接用暴力法了XDDD
推 purpose:這個遞迴做法是思路比較特別，也是別人給答案我才知道的
→ purpose:遞迴多多少少都有分而治之，把問題縮小的理念在
→ kevingwn:補充一下,將recursion(first + 1, last, best_buy...改成
→ kevingwn:double *next = first + 1;
→ kevingwn:for (; next != last; ++next)
→ kevingwn:  if (*next < *first)
→ kevingwn:    break;
→ kevingwn:recursion(next, last, best_buy, best_sell);
→ kevingwn:可以減少不必要的遞迴,除非遇到worst case否則可以快一點