[教學] Programming 9: "The Blacksheep Story Part III"

題目網址

題目大意：

求出最常共同序列(Longest Common Sequence)

CATCACGCACGCGCCGTTAAGCAACAGATACCAGATGTCGTTTTGGTTAGTGGATTTAGCAGTATGCCTAACAGGACGCAAAACGGAGGGCTATCCGGCGAGGGTCAGCGGGACCCTATACGACCCTCGGAATGTCTTTGTTTACGCACTAAATGAAGTC
ATCGATACTTGGTGATACGTGCCTACGGCACTTCACGCTAGTCACGACTCCCTCTATGCCCCCACCGTATATATCCAGCCAGTCGTGATTAGAGTAATCAGTGGGCTGTACTGTGATGCATACCACTCCCTCACCACGCACCGAGGGCTTTGACGAGGATTTGATTCGCTATGAGAGTTGCGCCCTTTTGCCAAGATTACCACGCTTACTCACGGCCGGCCGACGATGAAATGCACGCGCGGGGGCTCAGCGAGCTGCAAACAGATGTACTATTAAGGCATGATTAAAGATGTAATATAA

解法：

短的可以用畫的...
長的還是讓程式跑吧XD

以下程式以 Ruby 執行

1.遞迴(很慢...)

# Author      : mashimaro
# Last Modify : 2008/01/02

def lcs(str1,str2)
 if(str1.length == 0 || str2.length == 0)
  ''
 else
  if(str1[-1..-1] == str2[-1..-1])
   lcs(str1[0..-2],str2[0..-2]) + str1[-1..-1]
  else
   a=lcs(str1[0..-2],str2)
   b=lcs(str1,str2[0..-2])
   if(a.length>=b.length)
    a
   else
    b
   end
  end
 end
end

str2='ATCACGAATTGGGCAATAATGCTACTTGAGACGTTTGAGCCCTCCGTCGGGCGCCTGTGGATGCCGGATTGGCATCCCGCAACAGAACGCTCTTAGTCCCCGCCTTCGGAGAATATGCCAAGTCGTAAGAGGCGGACGTGCATCACGCACGCGCCGTTAAGCAACAGATACCAGATGTCGTTTTGGTTAGTGGATTTAGCAGTATGCCTAACAGGACGCAAAACGGAGGGCTATCCGGCGAGGGTCAGCGGGACCCTATACGACCCTCGGAATGTCTTTGTTTACGCACTAAATGAAGTC'
str1='ATCGATACTTGGTGATACGTGCCTACGGCACTTCACGCTAGTCACGACTCCCTCTATGCCCCCACCGTATATATCCAGCCAGTCGTGATTAGAGTAATCAGTGGGCTGTACTGTGATGCATACCACTCCCTCACCACGCACCGAGGGCTTTGACGAGGATTTGATTCGCTATGAGAGTTGCGCCCTTTTGCCAAGATTACCACGCTTACTCACGGCCGGCCGACGATGAAATGCACGCGCGGGGGCTCAGCGAGCTGCAAACAGATGTACTATTAAGGCATGATTAAAGATGTAATATAA'
str1=gets
str1.sub!("\n",'')
str2=gets
str2.sub!("\n",'')
puts lcs(str1, str2)

2.展開

# Author      : mashimaro
# Last Modify : 2008/01/02

str2='ATCACGAATTGGGCAATAATGCTACTTGAGACGTTTGAGCCCTCCGTCGGGCGCCTGTGGATGCCGGATTGGCATCCCGCAACAGAACGCTCTTAGTCCCCGCCTTCGGAGAATATGCCAAGTCGTAAGAGGCGGACGTGCATCACGCACGCGCCGTTAAGCAACAGATACCAGATGTCGTTTTGGTTAGTGGATTTAGCAGTATGCCTAACAGGACGCAAAACGGAGGGCTATCCGGCGAGGGTCAGCGGGACCCTATACGACCCTCGGAATGTCTTTGTTTACGCACTAAATGAAGTC'
str1='ATCGATACTTGGTGATACGTGCCTACGGCACTTCACGCTAGTCACGACTCCCTCTATGCCCCCACCGTATATATCCAGCCAGTCGTGATTAGAGTAATCAGTGGGCTGTACTGTGATGCATACCACTCCCTCACCACGCACCGAGGGCTTTGACGAGGATTTGATTCGCTATGAGAGTTGCGCCCTTTTGCCAAGATTACCACGCTTACTCACGGCCGGCCGACGATGAAATGCACGCGCGGGGGCTCAGCGAGCTGCAAACAGATGTACTATTAAGGCATGATTAAAGATGTAATATAA'
#str1='AAC'
#str2='ACAA'
#str1='CATGGCATG'
#str2='ATCATTCAT'
str1=gets
str1.sub!("\n",'')
str2=gets
str2.sub!("\n",'')

#puts str1,str2;

arr = Array.new(str2.length){Array.new(str1.length, 0)};

#arr = Array.new(2,Array.new(3, 1));#不能用Orz

x = 0;
str2.split(//).each { |s2|

 y = 0;

 #puts "\n"+s2;

 str1.split(//).each { |s1|

  #print s1;

  if(s1 == s2)

   if(x > 0 && y > 0)
    arr[x][y] = arr[x - 1][y - 1] + 1;
   else
    arr[x][y] = 1;
   end

   (x + 1).upto(str2.length-1) { |tmp_x|
    break if(arr[x][y] <= arr[tmp_x][y]);
    arr[tmp_x][y] = arr[x][y];
   }


   (y + 1).upto(str1.length-1) { |tmp_y|
    break if(arr[x][y] <= arr[x][tmp_y]);
    arr[x][tmp_y] = arr[x][y];
   }

   (y + 1).upto(str1.length-1) { |tmp_y|

    break if(x + 1 >= str2.length || arr[x][y] <= arr[x + 1][tmp_y]);

    (x + 1).upto(str2.length-1) { |tmp_x|

     break if(arr[x][y] <= arr[tmp_x][tmp_y]);

     arr[tmp_x][tmp_y] = arr[x][y];
    }
   }

  end

  y = y + 1;
 }
 x = x + 1;
}

  print ' ';
  str1.split(//).each { |c|
   print '  ' + c;
  }
  puts '';

  0.upto(str2.length-1) { |a|
   print str2[a..a];
   0.upto(str1.length-1) { |b|
    print ' ' * (3 - arr[a][b].to_s.length) + arr[a][b].to_s;
   }
   puts '';
  }

x = str2.length - 1;
y = str1.length - 1;

path = '';

puts 'arr[x][y] = ' + arr[x][y].to_s;
while(1)
 while(y > 0 && arr[x][y-1] == arr[x][y])
  y = y - 1;
 end
 while(x > 0 && arr[x-1][y] == arr[x][y])
  x = x - 1;
 end
 path = str1[y..y] + path;

 break if(arr[x][y] == 1);

 x = x - 1;
 y = y - 1;
end

puts path;

消息來源