博客

环状序列。

长度为n的环状串有n种表示法，分别为某个位置开始顺时针得到。在这些表示法中，字典序最小的称为“最小表示”。 输入一个长度为n(n<=100)的环状DNA串（只包含A、C、G、T这4种字符）的一种表示法，你的任务是输出该环状串的最小表示。例如，CTCC的最小表示是CCCT,CGAGTCAGCT的最小表示为AGCTCGAGTC。


这道题的难点在于怎么循环的比较环状串的大小，做完这道题的意义在于掌握用%运算符来比较循环的字符值比较，有点类似于数据结构中的循环队列。

答案代码

#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
#define maxn 105
int less1(const char *s,int p,int q){//计算环状串的最小表示
    int len=strlen(s);
    for(int i=0;i<len;i++){
        if(s[(p+i)%len]!=s[(q+i)%len]){
            return s[(p+i)%len]<s[(q+i)%len];//从p开始的序列最小表示<从q开始的序列表示返回1，用%符号可以将整个序列进行比较（即比较到字符末尾又会回到字符开头进行比较），从0循环到len又保证了字符串长度一定
        }
    }
    return 0;
}
int main()
{
    int T;
    char s[maxn];
    while(T--){
        scanf("%s",s);
        int len=strlen(s);
        int ans=0;
        for(int i=0;i<len;i++){
            if(less1(s,i,ans)){ans=i;}
        }
        for(int i=0;i<len;i++){
            putchar(s[(i+ans)%len]);//与上文%的用法一样
        }
        putchar('\n');
    }

}

`