junjie 通过本文主要向大家介绍了南瓜子ruby,ruby,ruby碧玺,ruby woo口红,mac ruby woo口红等相关知识,希望对您有所帮助,也希望大家支持linkedu.com www.linkedu.com
最长公共子序列，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 %s\n", 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)
</div> </div>