此算法是根据《算法导论》里面的介绍编写的。数据也是。代码运行后,结果数据正确。
以《算法导论》P213中未测试数据:
p[6]={-100,0.15,0.1,0.05,0.1,0.2};
q[6]={0.05,0.1,0.05,0.05,0.05,0.1};
运行结果:
《算法导论》中的结果p216:
代码如下:
#include <iostream>
void main()
{
float p[6]={-100,0.15,0.1,0.05,0.1,0.2};
float q[6]={0.05,0.1,0.05,0.05,0.05,0.1};
float e[7][6];
float w[7][6];
int root[6][6];
for(int i=1;i<7;i++)
e[i][i-1]=w[i][i-1]=q[i-1];//初始化d
for(int l=0;l<6;l++)//求间隔距离为L的序列子最优二叉树
{
for(int i=1;i<6-l;i++)//序列从i开始
{
int j=i+l;//到j结束
e[i][j]=1000;//初始化为-正无穷大
//遍历序列中的节点作为子树的根结点,并找到最小搜索代价放入e,同时把此根结点存放入root
w[i][j]=w[i][j-1]+q[j]+p[j];//这一个不太好理解。
//w的物理意义是这个序列的所有k点和d点的概率和。
//序列里面多了一个k点,同时,就要把这个Ki点和Di点加入到w里面。
for(int k=i;k<=j;k++)//计算以k为根结点的子二叉树的搜索代价
{
float tmp=e[i][k-1]+e[k+1][j]+w[i][j];
if(tmp<e[i][j])
{
e[i][j]=tmp;//如果搜索代价小于以前计算的,放入e(也就是说,e中一直存着目前最小的搜索代价)
root[i][j]=k;
}
}
}
}
printf("e:\n");
for(int i=1;i<7;i++){
for(int j=0;j<6;j++){
if(e[i][j]>10||e[i][j]<0){
printf(" ");
}
else{
printf("%1.2f,",e[i][j]);
}
}
printf("\n");
}
printf("w:\n");
for(int i=1;i<7;i++){
for(int j=0;j<6;j++){
if(w[i][j]>1||w[i][j]<0){
printf(" ");
}
else{
printf("%1.2f,",w[i][j]);
}
}
printf("\n");
}
printf("root:\n");
for(int i=1;i<6;i++){
for(int j=1;j<6;j++){
if(root[i][j]>10||root[i][j]<0){
printf(" ");
}
else{
printf("%d,",root[i][j]);
}
}
printf("\n");
}
}
- 大小: 15.5 KB
- 大小: 27.5 KB
分享到:
相关推荐
用C++实现的最优二叉查找树,简单,明了,是数据结构里经典必学算法,初学者适用
摘要视图订阅登录 | 注册195897次第4587名57篇33篇0篇117条0020算法笔记——【动态规划】最优二叉搜索树问题 liufeng_king的专
运用c语言,动态规划算法构造最优二叉查找树。
最优二叉查找树,包含习题15.5-1算法,为算法导论上的习题。
使用C++实现最优二叉查找树,对正在学习算法的同学应该挺有帮助的
最优二叉搜索树,计算机算法设计与分析的一个题目
关于最优二叉搜索树的动态规划算法描述
一个关于最优二叉搜索树的程序段 并且包含最后的生成结果的显示
运用c语言,贪心算法构造最优二叉查找树。
用动态规划的算法实现最优二叉检索树,使得在检索数据过程中花费的代价最小
凸包问题(包含蛮力算法和快速凸包算法两种解法)+最优二叉查找树,并且都利用javafx生成可视化界面,开箱即用,代码含注释,原理通俗易懂。
使用C#实现的动态规划算法 关键字序列:0.15,0.1,0.05,0.1,0.2 非关键字序列:0.05,0.1,0.05,0.05,0.05,0.1 以上的测试数据,输入数据可以得到结果
最优二叉搜索树的动态规划算法研究.txt
8.1 计算二项式系数 8.1 计算二项式系数 8.1 计算二项式系数 8.1 计算二项式系数 8.1 计算二项式系数 8.2 Warshall算法思想 8.2
第19章 动态规划 19.1 算法思想 19.2 应用 19.2.1 0/1背包问题 19.2.2 矩阵乘法链 19.2.3 所有顶点对之间的最短路径 19.2.4 带有负值的单源最短路径 19.2.5 网组的无交叉子集 19.3 参考及推荐读物 第20章 回溯法 ...
最优二叉查找树,为算法导论上的算法,时间复杂度O(nlgn),思考题15.5-
用分治法解决快速排序问题及用动态规划法解决最优二叉搜索树问题及用回溯法解决图的着色问题.pdf
经典原版教材——算法导论,MIT科尔曼版教材电子版