作者makiyolove (暴力熊)
看板Programming
標題[問題] dna序列密度
時間Mon May 18 11:20:58 2009
在網路上看到的題目
DNA序列是由A、T、C、G組成一串字串序列
舉例:agGCTGCAatGACAGTTGGG
然後找出大於使用者輸入長度L
包含C、G密度最高的序列串
此題解應輸出gGCTGC (假設L=5)
我只有想到用暴力法
列出每一種組合 計算密度 比較大小 再輸出
應該有更快的方法可以用?
懇請板友指教
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 192.192.199.49
1F：推 march20:DP 66.75.255.220 05/18 15:35
2F：推 march20:先求出 A1~Ai 的CG 個數合, 然後對所有 66.75.255.220 05/18 15:38
3F：推 march20:max (S_i - S_(i-L+1)) for L<i<n 66.75.255.220 05/18 15:40
4F：推 march20:啊, 直接回文 66.75.255.220 05/18 15:46
5F：推 wa120:李家同Algorithms的書 多的是這種解題～ 140.133.13.134 05/18 18:32
6F：→ wa120:沒記錯的話是LCS problem 140.133.13.134 05/18 18:32
7F：推 sorryChen:對阿 不是趙老師和呂學一老師論文嗎 128.125.87.33 05/19 11:34