二叉探索木-【動的計画】最適C++実現
45260 ワード
プログラムはVC++6.0の下でコンパイルして通過します
分類:アルゴリズム
1
#include
<
iostream
>
2
#include
<
fstream
>
3
#include
<
string
>
4
#include
<
limits
>
5
6
using
namespace
std;
7
8
const
string
INFILE
=
"
in.txt
"
;
//
“ ”
9
const
string
OUTFILE
=
"
out.txt
"
;
//
“ ”
10
const
int
N
=
7
;
//
11
const
double
MAX
=
numeric_limits
<
double
>
::max();
//
double
12
const
double
MAXMAX
=
numeric_limits
<
long
>
::max();
//
double
13
14
double
p[N
+
2
];
//
p[i] i
15
double
q[N
+
2
];
//
q[i] “ ”i
16
//
double e[(N+2)*(N+2)];
//
e， （i，j）
17
double
e[N
+
2
][N
+
2
];
18
//
double w[(N+2)*(N+2)];
//
w， （i，j） （ ） p、q
19
double
w[N
+
2
][N
+
2
];
20
//
int root[(N+2)*(N+2)];
//
root， root
21
int
root[N
+
2
][N
+
2
];
22
23
24
//
void optimalBst(double *p, double *q, int n)
25
void
optimalBst(
void
)
26
{
27
int
i,j,l,r;
//
i,j “ （i，j）”；l “ ”；r （ “ ”）
28
29
//
boundary case： j=i-1 ，“ （i，j）” “ i-1”*/
30
for
(i
=
1
; i
<=
N
+
1
;
++
i)
31
{
32
e[i][i
-
1
]
=
q[i
-
1
];
33
w[i][i
-
1
]
=
q[i
-
1
];
34
}
35
36
//
“ ” ， “ ”
37
for
(l
=
1
; l
<=
N ;
++
l)
//
l
38
{
39
for
(i
=
1
; i
<=
N
-
l
+
1
;
++
i)
//
l ，i 1 N-l+1
40
{
41
j
=
i
+
l
-
1
;
//
l，j i+l-1
42
e[i][j]
=
MAX;
43
w[i][j]
=
w[i][j
-
1
]
+
p[j]
+
q[j];
//
“ （i，j）” ， ，w[i,j]
44
45
//
i--j ， r “ ”
46
double
temp
=
MAX;
47
for
(r
=
i ; r
<=
j;
++
r)
48
{
49
temp
=
e[i][r
-
1
]
+
e[r
+
1
][j]
+
w[i][j];
50
if
(temp
<
e[i][j])
51
{
52
e[i][j]
=
temp;
53
root[i][j]
=
r;
54
}
55
}
56
}
57
}
58
59
60
}
61
62
int
main()
63
{
64
int
i,j;
65
ifstream fIn(INFILE.c_str());
//
“ ”
66
ofstream fOut(OUTFILE.c_str());
//
“ ”
67
68
//
69
i
=
1
;
70
while
(
!
fIn.eof())
71
{
72
if
(i
<=
N)
73
{
74
fIn
>>
p[i];
75
}
76
else
77
{
78
fIn
>>
q[i
-
N
-
1
];
79
}
80
++
i;
81
}
82
83
//
“ ” “ ”
84
//
optimalBst(p,q,N);
85
optimalBst();
86
87
//
88
for
(i
=
0
; i
<=
N
+
1
;
++
i)
89
{
90
for
(j
=
0
; j
<=
N
+
1
;
++
j)
91
{
92
fOut
<<
"
e[
"
<<
i
<<
"
,
"
<<
j
<<
"
] =
"
<<
e[i][j]
<<
endl;
93
}
94
}
95
fOut
<<
endl
<<
endl;
96
for
(i
=
0
; i
<=
N
+
1
;
++
i)
97
{
98
for
(j
=
0
; j
<=
N
+
1
;
++
j)
99
{
100
fOut
<<
"
w[
"
<<
i
<<
"
,
"
<<
j
<<
"
] =
"
<<
w[i][j]
<<
endl;
101
}
102
}
103
fOut
<<
endl
<<
endl;
104
for
(i
=
0
; i
<=
N
+
1
;
++
i)
105
{
106
for
(j
=
0
; j
<=
N
+
1
;
++
j)
107
{
108
fOut
<<
"
root[
"
<<
i
<<
"
,
"
<<
j
<<
"
] =
"
<<
root[i][j]
<<
endl;
109
}
110
}
111
112
cout
<<
"
、 ，
"
<<
OUTFILE
<<
"
！
"
<<
endl;
113
cout
<<
MAXMAX
<<
endl;
114
115
return
0
;
116
}
分類:アルゴリズム