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: ["b", "a", "c", "a", "a", "b", "d"] and ["a", "c", "a", "c", "a", "a", "b"] #The Longest-Commom-Subsequence is: a c a a b chars = ("a".."e").to_a x, y = [], [] 1.upto(rand(5) + 5) { |i| x << chars[rand(chars.size-1)] } 1.upto(rand(5) + 5) { |i| y << chars[rand(chars.size-1)] } printf("The random character arrays are: %s and %sn", x, y) c = Array.new(x.size + 1){Array.new(y.size + 1)} b = Array.new(x.size + 1){Array.new(y.size + 1)} def LCS_length(x, y ,c ,b) m, n = x.size, y.size (0..m).each{|i| c[i][0] = 0} (0..n).each{|j| c[0][j] = 0} for i in (1..m) do for j in(1..n) do if(x[i - 1] == y [j - 1]) c[i][j] = c[i - 1][j - 1] + 1; b[i][j] = 0 else if(c[i - 1][j] >= c[i][j - 1]) c[i][j] = c[i - 1][j] b[i][j] = 1 else c[i][j] = c[i][j - 1] b[i][j] = 2 end end end end end def Print_LCS(x, b, i, j) return if(i == 0 || j == 0) if(b[i][j] == 0) Print_LCS(x, b, i-1, j-1) printf("%c ", x[i - 1]) elsif(b[i][j] == 1) Print_LCS(x, b, i-1, j) else Print_LCS(x, b, i, j-1) end end LCS_length(x, y, c ,b) print "The Longest-Commom-Subsequence is: " Print_LCS(x, b, x.size, y.size)
Ruby实现的合并排序算法
算法课的作业,利用分治法,合并排序。#encoding:utf-8#author:xujin,4100213#date:Oct27,2012#MergeSort#tosortanarraybyusingMergeSortalgorithm#exampleoutput:#Theoriginalarrayis:[4,32,84
Ruby实现的矩阵连乘算法
动态规划解决矩阵连乘问题,随机产生矩阵序列,输出形如((A1(A2A3))(A4A5))的结果。代码:#encoding:utf-8=beginauthor:xujin,4100213date:Oct28,2012MatrixChaintofindanoptimumo
Ruby实现的各种排序算法
时间复杂度:Θ(n^2)Bubblesortdefbubble_sort(a)(a.size-2).downto(0)do|i|(0..i).eachdo|j|a[j],a[j+1]=a[j+1],a[j]ifa[j]a[j+1]endendreturnaendSelectionsortdefselection_sort(a)b=[]a.size.timesdo|i|mi
标签:算法,矩阵,序列,动态,复杂度