Ruby实现的最优二叉查找树算法
技术  /  管理员 发布于 4年前   207
算法导论上的伪码改写而成,加上导论的课后练习第一题的解的构造函数。
复制代码 代码如下:
#encoding: utf-8
=begin
author: xu jin
date: Nov 11, 2012
Optimal Binary Search Tree
to find by using EditDistance algorithm
refer to <<introduction to algorithms>>
example output:
"k2 is the root of the tree."
"k1 is the left child of k2."
"d0 is the left child of k1."
"d1 is the right child of k1."
"k5 is the right child of k2."
"k4 is the left child of k5."
"k3 is the left child of k4."
"d2 is the left child of k3."
"d3 is the right child of k3."
"d4 is the right child of k4."
"d5 is the right child of k5."
The expected cost is 2.75.
=end
INFINTIY = 1 / 0.0
a = ['', 'k1', 'k2', 'k3', 'k4', 'k5']
p = [0, 0.15, 0.10, 0.05, 0.10, 0.20]
q = [0.05, 0.10, 0.05, 0.05, 0.05 ,0.10]
e = Array.new(a.size + 1){Array.new(a.size + 1)}
root = Array.new(a.size + 1){Array.new(a.size + 1)}
def optimalBST(p, q, n, e, root)
w = Array.new(p.size + 1){Array.new(p.size + 1)}
for i in (1..n + 1)
e[i][i - 1] = q[i - 1]
w[i][i - 1] = q[i - 1]
end
for l in (1..n)
for i in (1..n - l + 1)
j = i + l -1
e[i][j] = 1 / 0.0
w[i][j] = w[i][j - 1] + p[j] + q[j]
for r in (i..j)
t = e[i][r - 1] + e[r + 1][j] + w[i][j]
if t < e[i][j]
e[i][j] = t
root[i][j] = r
end
end
end
end
end
def printBST(root, i ,j, signal)
return if i > j
if signal == 0
p "k#{root[i][j]} is the root of the tree."
signal = 1
end
r = root[i][j]
#left child
if r - 1< i
p "d#{r - 1} is the left child of k#{r}."
else
p "k#{root[i][r - 1]} is the left child of k#{r}."
printBST(root, i, r - 1, 1 )
end
#right child
if r >= j
p "d#{r} is the right child of k#{r}."
else
p "k#{root[r + 1][j]} is the right child of k#{r}."
printBST(root, r + 1, j, 1)
end
end
optimalBST(p, q, p.size - 1, e, root)
printBST(root, 1, a.size-1, 0)
puts "\nThe expected cost is #{e[1][a.size-1]}."
原梓番博客 在
在Laravel框架中使用模型Model分表最简单的方法中评论 好久好久都没看友情链接申请了,今天刚看,已经添加。..博主 在
佛跳墙vpn软件不会用?上不了网?佛跳墙vpn常见问题以及解决办法中评论 @1111老铁这个不行了,可以看看近期评论的其他文章..1111 在
佛跳墙vpn软件不会用?上不了网?佛跳墙vpn常见问题以及解决办法中评论 网站不能打开,博主百忙中能否发个APP下载链接,佛跳墙或极光..路人 在
php中使用hyperf框架调用讯飞星火大模型实现国内版chatgpt功能示例中评论 教程很详细,如果加个前端chatgpt对话页面就完美了..博主 在
科学上网翻墙之v2rayN-Core客户端免费公益节点使用教程中评论 @ mashrdn 多切换几个节点测试,免费ssr是没那么稳..Copyright·© 2019 侯体宗版权所有· 粤ICP备20027696号