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

时间: 2024-12-24 20:25:40

Ruby实现的最优二叉查找树算法_ruby专题的相关文章

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 <> example output: "

深入理解Ruby中的代码块block特性_ruby专题

block是什么? 在Ruby中,block并不罕见.官方对block的定义是"一段被包裹着的代码".当然,我觉得这样的解释不会让你变的更明白. 对block的一种更简单的描述是"一个block就是一段存储在一个变量中的代码,它和其他的对象一样,可以被随时的运行" 然后,咱们通过看一些代码,之后再把这些代码重构成Ruby中的block形式.通过代码来实际的感受,更加直观. 比如,对两个数做加法? puts 5 + 6 # => 11 嗯,这样写是可以的.但是,

Ruby实现的最长公共子序列算法_ruby专题

最长公共子序列,LCS,动态规划实现. #encoding: utf-8 #author: xu jin, 4100213 #date: Nov 01, 2012 #Longest-Commom-Subsequence #to find a longest commom subsequence of two given character arrays by using LCS algorithm #example output: #The random character arrays are

Ruby实现的合并排序算法_ruby专题

算法课的作业,利用分治法,合并排序. #encoding: utf-8 #author: xu jin, 4100213 #date: Oct 27, 2012 #MergeSort #to sort an array by using MergeSort algorithm #example output: #The original array is:[4, 32, 84, 58, 49, 40, 75, 29, 82, 21, 70, 37, 70] #The sorted array i

Ruby实现的各种排序算法_ruby专题

时间复杂度:Θ(n^2) Bubble sort 复制代码 代码如下: def bubble_sort(a)    (a.size-2).downto(0) do |i|      (0..i).each do |j|        a[j], a[j+1] = a[j+1], a[j] if a[j] > a[j+1]      end    end    return a  end Selection sort 复制代码 代码如下: def selection_sort(a)    b =

浅析Ruby中的Profiling工具的用法_ruby专题

内置的profiler实现的很简单,在ruby2.2中只有150行代码,大家可以看看它的实现profile.rb .内置的profiler使用起来非常的方便,只需要加上-rprofile参数即可.例如: 执行: ruby -rprofile test.rb 输出结果为: 通过打印出的结果能够很明显的看出耗时的方法.内置的profiler很简单,只能打印出这样的结果,没有 其他输出格式的选项,下面介绍的其他几种都有丰富的格式输出.ruby-prof repo: https://github.com

Ruby编程中的命名风格指南_ruby专题

用英语命名标识符.    # bad - identifier using non-ascii characters заплата = 1_000 # bad - identifier is a Bulgarian word, written with Latin letters (instead of Cyrillic) zaplata = 1_000 # good salary = 1_000     使用snake_case的形式给变量和方法命名.     # bad :'some sy

Ruby的运算符和语句优先级介绍_ruby专题

Ruby 是一种表达能力很强的语言,这得意于它异常丰富的运算符和语法糖,虽然 Ruby 一直把最小惊讶原则作为它的哲学之一,但还是常常看到让人惊讶不已,难于理解的代码,这可能是因为对它运算符和语句优先级理解不透导致,今天就和大家聊一聊 Ruby 运算符和语句的优先级. 先看一句简单的代码,猜一猜它的输出是什么. 复制代码 代码如下:   puts {}.class 很多人一定以为结果是 Hash,但实事上结果是空,不信可以在 irb 里试一试. 再看一段代码. 复制代码 代码如下: puts "

进一步深入Ruby中的类与对象概念_ruby专题

Ruby是纯面向对象的语言,所有项目似乎要Ruby中为一个对象.Ruby中的每个值是一个对象,即使是最原始的东西:字符串,数字甚至true和false.即使是一个类本身是一个对象,它是Class类的一个实例.本章将通过所有功能涉及到Ruby的面向对象. 类是用来指定对象的形式,它结合了数据表示和方法操纵这些数据,转换成一个整齐的包.在一个类的数据和方法,被称为类的成员.Ruby类的定义: 定义一个类,定义的数据类型的草图. 这实际上并不定义任何数据,但它定义的类名字的意思什么,即是什么类的对象将