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

赞 (0)

相关推荐

  • Ruby实现二分搜索(二分查找)算法的简单示例

    Ruby实现二分搜索(二分查找)算法的简单示例

    在计算机科学中,二分搜索(英语:binary search),也称折半搜索(英语:half-interval search).对数搜索(英语:logarithmic search),是一种在有序数组中查找某一特定元素的搜索算法.搜索过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜索过程结束:如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较.如果在某一步骤数组为空,则代表找不到.这种搜索算法每一次比较都使搜索范围缩小一半

  • Ruby实现的矩阵连乘算法

    动态规划解决矩阵连乘问题,随机产生矩阵序列,输出形如((A1(A2A3))(A4A5))的结果. 代码: #encoding: utf-8 =begin author: xu jin, 4100213 date: Oct 28, 2012 MatrixChain to find an optimum order by using MatrixChain algorithm example output: The given array is:[30, 35, 15, 5, 10, 20, 25]

  • Ruby实现的3种快速排序算法

    刚学Ruby,正巧算法老师鼓励用不熟悉的语言来写算法,我就用Ruby吧~~ 话说Ruby可真是超厉害,好多凭直觉的方法都可以用.....无限膜拜中.... 期间我遇到了invalid multibyte char (US-ASCII)的错误,解决办法是在开头加一个#encoding:utf-8 这个错误在stackoverflow上有人问到过,某人给出的回答是 Write # encoding: utf-8 on top of that file. That changes the defaul

  • Ruby实现的图片滤镜算法代码

    Ruby实现的图片滤镜算法代码

    原图 一.灰度算法 彩色照片每一个像素的颜色值由红.绿.蓝三种值混合而成,红绿蓝的取值分别由很多种,于是像素的颜色值也可以有很多种颜色值,这就是彩色图片的原理,而灰度照片则只有256种颜色,一般的处理方法是将图片颜色值的RGB三个通道值设为一样,这样图片的显示效果就会是灰色. 灰度处理一般有三种算法: 最大值法:即新的颜色值R＝G＝B＝Max(R,G,B),这种方法处理后的图片看起来亮度值偏高. 平均值法:即新的颜色值R＝G＝B＝(R+G+B)/3,这样处理的图片十分柔和 加权平均值法:即新的颜

  • 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实现的插入排序和冒泡排序算法

    1.插入排序 复制代码 代码如下: seq = [3,4,9,0,2,5,9,7,1] 1.upto(seq.length-1) do |i|  if seq[i] < seq[i-1]    tmp = seq[i]    j = i-1    while(j>=0 && tmp<seq[j]) do      seq[j+1] = seq[j]      j=j-1    end    seq[j+1]=tmp  endend seq.each {|num| puts

  • 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实现的最优二叉查找树算法

    算法导论上的伪码改写而成,加上导论的课后练习第一题的解的构造函数. 复制代码 代码如下: #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 r

  • Swift中排序算法的简单取舍详解

    前言 对于iOS开发者来说, 算法的实现过程其实并不怎么关心, 因为只需要调用高级接口就可以得到系统最优的算法, 但了解轮子背后的原理才能更好的取舍, 不是么?下面话不多说了,来一起看看详细的介绍吧. 选择排序 我们以[9, 8, 7, 6, 5]举例. [9, 8, 7, 6, 5] 第一次扫描, 扫描每一个数, 如比第一个数小则交换, 直到找到最小的数, 将其交换至下标0. [8, 9, 7, 6, 5] [7, 9, 8, 6, 5] [6, 9, 8, 7, 5] [5, 9, 8, 7

  • python最长回文串算法

    给定一个字符串,要求在这个字符串中找到符合回文性质的最长子串.所谓回文性是指诸如 "aba","ababa","abba"这类的字符串,当然单个字符以及两个相邻相同字符也满足回文性质. 看到这个问题,最先想到的解决方法自然是暴力枚举,通过枚举字符串所有字串的起点,逐一判断满足回文性的子串,记录长度并更新最长长度.显然这种算法的时间复杂度是很高的,最坏情况可以达到O(N*N).所以呢,这里提出一个优化的方案,通过枚举字符串子串的中心而不是起点,向两

  • Spring Boot接口限流的常用算法及特点

    Spring Boot接口限流的常用算法及特点

    前言 在一个高并发系统中对流量的把控是非常重要的,当巨大的流量直接请求到我们的服务器上没多久就可能造成接口不可用,不处理的话甚至会造成整个应用不可用. 那么何为限流呢?顾名思义,限流就是限制流量,就像你宽带包了1个G的流量,用完了就没了.通过限流,我们可以很好地控制系统的qps,从而达到保护系统的目的.本篇文章将会介绍一下常用的限流算法以及他们各自的特点. 算法介绍 计数器法 计数器法是限流算法里最简单也是最容易实现的一种算法.比如我们规定,对于A接口来说,我们1分钟的访问次数不能超过100个.

  • 深入理解JVM垃圾回收算法

    深入理解JVM垃圾回收算法

    目录 一.垃圾标记阶段 1.1.引用计数法 (java没有采用) 1.2.可达性分析算法 二.对象的finalization机制 2.1.对象是否"死亡" 三.使用(MAT与JProfiler)工具分析GCRoots 3.1.获取dump文件 3.2.GC Roots分析 四.垃圾清除阶段 4.1.标记-清除算法 4.2.复制算法 4.3.标记-压缩(整理,Mark-Compact)算法 4.4.以上三种垃圾回收算法对比 4.5.分代收集算法 4.6.增量收集算法 4.7.分区算法G1

  • Python机器学习入门(五)算法审查

    Python机器学习入门(五)算法审查

    目录 1.审查分类算法 1.1线性算法审查 1.1.1逻辑回归 1.1.2线性判别分析 1.2非线性算法审查 1.2.1K近邻算法 1.2.2贝叶斯分类器 1.2.4支持向量机 2.审查回归算法 2.1线性算法审查 2.1.1线性回归算法 2.1.2岭回归算法 2.1.3套索回归算法 2.1.4弹性网络回归算法 2.2非线性算法审查 2.2.1K近邻算法 2.2.2分类与回归树 2.2.3支持向量机 3.算法比较 总结 程序测试是展现BUG存在的有效方式,但令人绝望的是它不足以展现其缺位. --

  • java贪心算法初学感悟图解及示例分享

    java贪心算法初学感悟图解及示例分享

    算法简介 1)贪心算法是指在对问题进行求解时,在每一步选择中都采取最好或者最优(即最有利)的选择,从而希望能够导致是最好或者最优的算法 2)贪心算法所得到的结果不一定是最优的结果(有时候会是最优解),但是都是相对近似(接近)最优解的结果. 应用场景 --> 集合覆盖 public class GreedyAlgorithm { public static void main(String[] args) { // 创建广播电台,放入到Map HashMap<String, HashSet<

随机推荐