環(huán)狀序列（紫書例題3-6）
問(wèn)題描述：
長(zhǎng)度為n的環(huán)狀串有n種表示法捂人，分別為某個(gè)位置開始順時(shí)針得到扒接。CGAGTCAGCT,GAGTCAGCTC,AGTCAGCTCG等。在這些表示法中，字典序最小的稱為“最小表示”疾嗅。輸入一個(gè)長(zhǎng)度為n(n<=100)的環(huán)狀DNA串（只包含A镣隶、C绷耍、G奇钞、T這4種字符）的一種表示法，你的任務(wù)是輸出該環(huán)狀串的最小表示熬尺。例如摸屠，CTCC的最小表示是CCCT,CGAGTCAGCT的最小表示為AGCTCGAGTC。
樣例輸入：
2
CGAGTCAGCT
CTCC
樣例輸出：
AGCTCGAGTC
CCCT
分析：
一開始理解這道題的時(shí)候很吃力粱哼，看了好久都不知道它想要干嘛季二，后面才知道原來(lái)是在一串成環(huán)的 DNA像字典排序一樣找出其中最小的表示，也就是要按照字母排列尋找正確的起點(diǎn)揭措。
難點(diǎn)：
1.當(dāng)找到的起點(diǎn)并非是輸入的DNA序列的第一個(gè)字母戒傻，怎么讓“斷掉“”的重新“續(xù)上”：
（起點(diǎn)s+增值i）%輸入DNA的長(zhǎng)度
2.當(dāng)符合/不符合時(shí)，應(yīng)怎么遞增繼續(xù)判斷/切換起點(diǎn)：
符合時(shí)蜂筹，記錄當(dāng)前i的值作為起點(diǎn)，用此起點(diǎn)繼續(xù)跟該點(diǎn)以后做起點(diǎn)的序列作比較芦倒；不符合時(shí)艺挪，直接跳過(guò)；直到到達(dá)該DNA的結(jié)尾兵扬。
判斷以不同起點(diǎn)的序列的字典序麻裳，從起點(diǎn)開始比較，當(dāng)增加相同單位處的字母不同時(shí)器钟，字母小的序列就小津坑，相同時(shí)繼續(xù)判斷兩序列的下一個(gè)位置字母的大小關(guān)系，直到回到原起點(diǎn)傲霸。
代碼如下：
#include<iostream>
#include<string>
using namespace std;
int comp(string s,int s1,int s2){
int num=s.size();
for(int i=0;i<num;i++){
if(s[(s1+i)%num]!=s[(s2+i)%num])
return s[(s1+i)%num]>s[(s2+i)%num];
}
return 0;
}
int main(){
int n;
string dna;
cin>>n;
while(n--){
cin>>dna;
int start=0,num=dna.size();
for(int i=1;i<num;i++){
if(comp(dna,start,i))start=i;
}
for(int i=0;i<num;i++){
cout<<dna[(start+i)%num];
}
cout<<endl;
}
}
相似的疆瑰，還有：
DNA序列（紫書習(xí)題3-7）
題目描述：
輸入m個(gè)長(zhǎng)度均為n的DNA序列，求一個(gè)DNA序列昙啄，到所有序列的總Hamming距離盡量小穆役。兩個(gè)等長(zhǎng)字符串的Hamming距離等于字符不同的位置個(gè)數(shù)，例如梳凛，ACGT和GCGA的Hamming距離為2（左數(shù)第1,4字符不同）耿币。
輸入整數(shù)m和n(4<=m<=50,4<=n<=1000),以及m個(gè)長(zhǎng)度為n的DNA序列（只是包含字母A,C,G,T），輸出到m個(gè)序列的Hamming距離和最小的DNA序列和對(duì)應(yīng)的距離韧拒。如有多解淹接，要求為字典序最小的解十性。例如，對(duì)于下面5個(gè)DNA序列塑悼，最優(yōu)解為TAAGATAC劲适。
分析：
在上面那題對(duì)字典序有了了解以后，理解這道題就很簡(jiǎn)單了拢肆。所謂Hamming距離和最小意思就是跟所給出的所有序列的字符不同的位置個(gè)數(shù)總和最小减响，直接尋找在所有序列相同位置中出現(xiàn)次數(shù)最多的字符就可以找出這個(gè)序列了。又由于規(guī)定了多個(gè)解的時(shí)候郭怪，題目要求字典序最小支示，因此判斷時(shí)可以用if-else結(jié)構(gòu)按照字典順序進(jìn)行判斷。
代碼如下：
#include<iostream>
#include<string>
using namespace std;
int main(){
int m,n,max,a,c,g,t;
string dna;
cin>>m>>n;
char str[m][n];
for(int i=0;i<m;++i){
cin>>str[i];
}
for(int i=0;i<n;++i){
a=c=t=g=0;
for(int j=0;j<m;++j){
if(str[j][i]=='A')a++;
else if(str[j][i]=='C')c++;
else if(str[j][i]=='G')g++;
else t++;
}
max=a;
if(c>max)max=c;
if(g>max)max=g;
if(t>max)max=t;
if(max==a)dna+='A';
else if(max==c)dna+='C';
else if(max==g)dna+='G';
else if(max==t)dna+='T';
}
cout<<"\n"<<dna<<endl;
}
