算法导论上的伪码改写而成,加上导论的课后练习第一题的解的构造函数。
复制代码 代码如下:
#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]}."
免责声明:本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除!
P70系列延期,华为新旗舰将在下月发布
3月20日消息,近期博主@数码闲聊站 透露,原定三月份发布的华为新旗舰P70系列延期发布,预计4月份上市。
而博主@定焦数码 爆料,华为的P70系列在定位上已经超过了Mate60,成为了重要的旗舰系列之一。它肩负着重返影像领域顶尖的使命。那么这次P70会带来哪些令人惊艳的创新呢?
根据目前爆料的消息来看,华为P70系列将推出三个版本,其中P70和P70 Pro采用了三角形的摄像头模组设计,而P70 Art则采用了与上一代P60 Art相似的不规则形状设计。这样的外观是否好看见仁见智,但辨识度绝对拉满。
更新日志
- 《阿瑞亚之旅》评测:更适合佛系玩家体质的跑团
- 黑神话悟空浮屠界紫门怎么开 浮屠界紫门打开方法介绍
- 黑神话悟空龟泪怎么获得 黑神话悟空龟泪获得方法介绍
- 黑神话悟空怎么获得还魂丹 黑神话悟空还魂丹获取方法一览
- HiFi顶级人声天碟《试音齐秦》wav
- 张敬轩.2012-WhyNot(EP)【环球】【WAV+CUE】
- 张小英1988-情愁[新加坡复黑版][WAV+CUE]
- 游民金币礼品补货啦 Steam充值卡等你兑换!
- 《暗喻幻想:ReFantazio》M站均分94分 近年最好的RPG游戏之一
- 今年第一项诺贝尔奖揭幕 生理学或医学奖揭晓
- 《梁静茹 华语乐坛情歌天后 爱久见人心》[WAV/分轨][360MB]
- 《田震 绝版珍藏 依然在飞》[WAV+CUE][600MB]
- 《60首经典金曲 4CD》[WAV/分轨][1.4GB]
- 赵传.1988-我很丑,可是我很温柔【滚石】【WAV+CUE】
- 遗忘曲线.2024-遗忘曲线(EP)【LuuvLabel】【FLAC分轨】