📄 text10-6.htm
字号:
<html>
<head>
<title>Untitled Document</title>
<meta http-equiv="Content-Type" content="text/html; charset=gb2312">
</head>
<body bgcolor="#FFFFFF" link="#0000FF" vlink="#3399FF" alink="#FF0066">
<div id="Layer1" style="position:absolute; width:711px; height:21px; z-index:1; top: 10px; background-color: #CCCCCC; layer-background-color: #CCCCCC; border: 1px none #000000; left: 26px"><b>|</b><font face="宋体" size="2"><a href="../text1/text1-0.htm">第一章</a></font><b>|</b><font face="宋体" size="2"><a href="../text2/text2-0.htm">第二章</a></font><b>|</b><font face="宋体" size="2"><a href="../text3/text3-0.htm">第三章</a></font><b>|</b><font face="宋体" size="2"><a href="../text4/text4-0.htm">第四章</a></font><b>|</b><font face="宋体" size="2"><a href="../text5/text5-0.htm">第五章</a></font><b>|</b><font face="宋体" size="2"><a href="../text6/text6-0.htm">第六章</a></font><b>|</b><font face="宋体" size="2"><a href="../text7/text7-0.htm">第七章</a></font><b>|</b><font face="宋体" size="2"><a href="../text8/text8-0.htm">第八章</a></font><b>|</b><font face="宋体" size="2"><a href="../text9/text9-0.htm">第九章</a></font><b>|</b><font face="宋体" size="2">第十章</font><b>|</b><font size="2" face="宋体"><a href="../textA/textA-0.htm">算法分析</a><b><font color="#000000">|</font></b>
</font></div>
<pre align="left">
<b><font face="Arial, Helvetica, sans-serif" size="4" color="#FF0000">D.E.Knuth algorithm </font><font face="Arial, Helvetica, sans-serif" size="4" color="#000000"> O(<img src="image/n2.gif" width="21" height="20" align="middle"> )
find the optimal l by limiting the search to the range
<i> ri,j-1 <= l <= ri+1,j</i>
<font color="#FF0000">Function to find an optimal binary search tree</font>
#define MAX_SIZE 200 <i><font size="3" color="#CC0099">/* max # of ids plus 1 */</font></i>
#define MAX_CHAR 30 <i><font size="3" color="#CC0099">/* max characters/id */</font></i>
<i><font size="3" color="#CC0099">/* set of identifiers */</font></i>
char words [MAX_SIZE][MAX_CHAR], *ptr = words[0];
int q[MAX_SIZE];
int p[MAX_SIZE];
int cost[MAX_SIZE][MAX_SIZE];
int root[MAX_SIZE][MAX_SIZE];
int weight[MAX_SIZE][MAX_SIZE];
int n; <i><font size="3" color="#CC0099">/* number of identifiers */</font></i>
void <font color="#FF0000">obst</font>( int p [ ] , int q [ ] , int cost [ ][MAX_SIZE] ,
int root [ ][MAX_SIZE] , int weight [ ][MAX_SIZE] , int n )
{
<i><font size="3" color="#CC0099"> /* given n distinct identifiers a[1] , ... , a[n] and probabilities
p[1] , ... , p[n] , and q[0] , ... , q[n] compute the cost c[i][j] of the optimal
binary search tree for a[i]...a[j] , 1 <= i <= j <= n.Also compute the weight
and root of the tree */</font></i>
int i , j , k , m , min , minpos ;
<font size="3" color="#CC0099"><i> /* initialize 0 and 1 node trees */
</i><font size="4" color="#000000"> for ( i = 0 ; i < n ; i++ ){</font></font>
weight[i][i] = q[i] ;
root[i][i] = 0 ;
cost[i][i] = 0 ;
cost[i][i+1] = weight[i][i+1] = q[i]+q[i+1]+p[i+1] ;
root[i][i+1] = i+1 ;
}
weight[n][n] = q[n] ;
root[n][n] = 0 ;
cost[n][n] = 0 ;
<i><font size="3" color="#CC0099"> /* compute remaining diagonals */</font></i>
for ( m = 2 ; m <= n ; m++ )
for ( i = 0 ; i <= n-m ; i++ ){
j = i+m ;
weight[i][j] = weight[i][j-1]+p[j]+q[j] ;
k = knuth_min( cost , root , i , j ) ;
<i><font size="3" color="#CC0099"> /* knuth_min returns a value , k , in the range root[i][j-1] to root[i+1][j]
, that minimizes cost[i][k-1]+cost[k][j] */ </font></i>
cost[i][j] = weight[i][j]+cost[i][k-1] +cost[k][j] ;
root[i][j] = k ;
}
}
</font></b></pre>
<table width="731" cellspacing="0" cellpadding="0">
<tr>
<td width="327"> </td>
<td width="271"><a href="../index.htm"><img width="60" height="25" usemap="#MapMap4" border="0" src="../../images/home.gif"></a><a href="../index.htm"><map name="MapMap4"><area shape="rect" coords="42,-34,88,-15" href="text0.htm"><area shape="rect" coords="4,4,55,23" href="text10-index.htm"></map></a></td>
<td width="131"><font face="楷体_GB2312" size="2"><b><a href="text10-5.htm">上一页</a>
<a href="text10-7.htm">下一页</a> </b></font></td>
</tr>
</table>
</body>
</html>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -