[ create a new paste ] login | about

Link: http://codepad.org/NlcM35W1    [ raw code | output | fork | 1 comment ]

C++, pasted on Mar 31: 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

/* 
   第一天到最高價格日 -> 前段
   最低價格日到最後一天 -> 後段
   剩下部份 -> 中段
*/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void getMinMax(double *price, int head, int tail, int &mind, int &maxd) {
  mind = head;
  maxd = head;
  for (int i = head; i <= tail; i++) {
    if (price[i] > price[maxd]) {
      maxd = i;
    }
    if (price[i] < price[mind]) {
      mind = i;
    }
  }
}

void getDate(double* price, int head, int tail, double *record) {
  int maxd;	// 最高價格日 (取最早出現)
  int mind;	// 最低價格日 (取最早出現)
	
  getMinMax(price, head, tail, mind, maxd);
  if (maxd > mind) {
    if ( (price[maxd] - price[mind]) > record[0] ) {
      record[0] = price[maxd] - price[mind];
      record[1] = mind;
      record[2] = maxd;
    }
  } else {  // mind == maxd (不能切) OR mind > maxd (可能可以切)
    int old_mind = mind;
    int old_maxd = maxd;
		
    // 處理前段
    getMinMax(price, head, old_maxd, mind, maxd);
    if ( (price[maxd] - price[mind]) > record[0] ) {
      record[1] = mind;  record[2] = maxd;
      record[0] = price[maxd] - price[mind];
    }

    // 處理中段     
    if (old_mind - old_maxd >= 2) {
      getDate(price, old_maxd+1, old_mind-1, record);
    }

    // 處理後段
    getMinMax(price, old_mind, tail, mind, maxd);
    if ( (price[maxd] - price[mind]) > record[0] ) {			
      record[1] = mind;  record[2] = maxd;
      record[0] = price[maxd] - price[mind];
    }
  }
}


int main() {
  // double price[] = {40, 70, 25, 35, 26, 28, 27, 29, 28, 30, 65, 10, 20};
  // double price[] = {55.39, 109.23, 48.29, 81.59, 105.53, 94.45, 12.24};
  double price[] = {55.39, 109.23, 48.29, 81.59, 81.58, 105.53, 94.45, 12.24};
  // double price[15] = {874, 803, 165, 686, 941, 407, 896, 965, 967, 919, 768, 156, 916, 564, 773};  // case Random

  double record[3] = {0,0,0};	// record[0] = 利潤、record[1] = 買日、record[2] = 賣日
  getDate(price, 0, sizeof(price) / sizeof(double) - 1, record);

  printf("\n最佳買日：%d\t價格：%f\n", (int) record[1] + 1, *(price + (int) record[1]) );
  printf("最佳賣日：%d\t價格：%f\n", (int) record[2] + 1, *(price + (int) record[2]) );
  printf("\t\t利潤為：%f\n", record[0]);

  return 0;
}


Output: 
1
2
3
4


最佳買日：3	價格：48.290000
最佳賣日：6	價格：105.530000
		利潤為：57.240000


Create a new paste based on this one


Comments:
posted by fuha on Mar 31
int in = 0;
int out = 0;
double t_r = 0.0;
const double p[8] = {55.39, 109.23, 48.29, 81.59, 81.58, 105.53, 94.45, 12.24};

void rec_cal(int b, int e)
{
//std::cout << b << " : " << e << std::endl;
if (b >= e && e >= 0) {
double temp = p[b] - p[e];
//std::cout << b << " : " << e << " => "<< r << std::endl;
if (t_r < temp ) {
in = e;
out = b;
t_r = temp;
}

if (e == 0) {
rec_cal(b - 1, b - 2);
} else {
rec_cal(b, e - 1);
}
}
}

int main(void)
{
rec_cal(7, 7);

std::cout << in << " -> " << out << ", eran is " << t_r << std::endl;

return 0;
}
reply