脚本之家,脚本语言编程技术及教程分享平台!
分类导航

Python|VBS|Ruby|Lua|perl|VBA|Golang|PowerShell|Erlang|autoit|Dos|bat|

服务器之家 - 脚本之家 - Ruby - Ruby实现的最优二叉查找树算法

Ruby实现的最优二叉查找树算法

2020-04-30 11:13脚本之家 Ruby

这篇文章主要介绍了Ruby实现的最优二叉查找树算法,本文直接给出实现代码,需要的朋友可以参考下

算法导论上的伪码改写而成,加上导论的课后练习第一题的解的构造函数。

复制代码 代码如下:


#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]}."

 

 

延伸 · 阅读

精彩推荐
  • RubyRuby迭代器的7种技巧分享

    Ruby迭代器的7种技巧分享

    这篇文章主要介绍了Ruby迭代器的7种技巧分享,Ruby中的迭代器非常人性化,本文既是讲解了7个技巧也是讲解了7种迭代器,需要的朋友可以参考下 ...

    脚本之家4782020-04-20
  • RubyRuby环境下安装使用bundler来管理多版本的gem

    Ruby环境下安装使用bundler来管理多版本的gem

    这篇文章主要介绍了Ruby环境下安装使用bundler来管理多版本的gem的方法,举了Ruby On Rails中的应用实例来进行演示,需要的朋友可以参考下 ...

    日拱一卒4332020-05-10
  • Ruby简要说明Ruby中的迭代器

    简要说明Ruby中的迭代器

    这篇文章主要介绍了Ruby中的迭代器,迭代器的概念在动态语言的编程中十分重要,文章中介绍了Ruby中的each迭代器和collect迭代器,需要的朋友可以参考下 ...

    goldensun2772020-04-25
  • RubyCentOS中配置Ruby on Rails环境

    CentOS中配置Ruby on Rails环境

    经过一个上午的折腾,终于把ROR环境在CentOS中搞定,绕了很多弯路,把文章写下来总结一下 ...

    可乐加糖4762020-04-12
  • RubyRuby设计模式编程中使用Builder建造者模式的实例

    Ruby设计模式编程中使用Builder建造者模式的实例

    这篇文章主要介绍了Ruby设计模式编程中使用Builder建造者模式的实例,建造者模式将一个复杂对象的构造与它的表示分离,使同样的构建过程可以创建不同的表...

    范孝鹏2192020-05-07
  • RubyRuby简洁学习笔记(一):字符串、数字、类和对象

    Ruby简洁学习笔记(一):字符串、数字、类和对象

    这篇文章主要介绍了Ruby简洁学习笔记(一):字符串、数字、类和对象,本文是学习笔记第一篇,需要的朋友可以参考下 ...

    脚本之家2472020-04-20
  • RubyRuby进行文件信息输出实例代码

    Ruby进行文件信息输出实例代码

    Ruby进行文件信息输出实例代码,数据是随机的,所以每次的记录都会不同。 ...

    ruby教程网2962020-04-10
  • Ruby剖析 Ruby 访问控制

    剖析 Ruby 访问控制

    前面,我们说 Ruby 没有函数,只有方法.而且实际上有不止一种方法.这一节我们介绍 访问控制 (accesscontrols). 想想当我们在最高层而不是在一个类的定义里定义...

    ruby教程网3572020-04-08