Openjudge-计算概论(A)-DNA排序

描述:

给出一系列基因序列,由A,C,G,T四种字符组成。对于每一个序列,定义其逆序对如下: 
序列中任意一对字符X和Y,若Y在X的右边(不一定相邻)且Y < X,则称X和Y为一个逆序对。 
例如GAC这个序列,其中GC,GA都是逆序对。 

一个序列的逆序对越多,则认为其"无序度"越高。你的任务是将基因按照无序度从小到大的顺序排序,如果存在无序度相同的序列,则按照原始输入顺序输出。

输入首先是基因序列的长度n(0 < n <= 50)和基因序列的个数m ( 0 < m <= 100).
然后依次是这m个基因序列.输出输出排序后的m个基因序列。

样例输入

10 6
AACATGAAGG
TTTTGGCCAA
TTTGGCCAAA
GATCAGATTT
CCCGGGGGGA
ATCGATGCAT

样例输出

CCCGGGGGGA
AACATGAAGG
GATCAGATTT
ATCGATGCAT
TTTTGGCCAA
TTTGGCCAAA
思路:用结构体,统计每个字符串的逆序对个数,排序,输出即可。
代码如下(本代码来自我的老师:http://www.cnblogs.com/huashanqingzhu/p/3575491.html):
 1 #include<stdio.h>
 2 struct DNA
 3 {
 4     char a[50];//一个基因序列 
 5     int num;//本基因序列的逆序对个数 
 6 };
 7 int niXuDui(struct DNA d,int len);//统计DNA序列变量d的逆序对个数 
 8 int main()
 9 {
10     struct DNA  d[100],t;
11     int n,m,i,j,flag;
12     scanf("%d%d",&n,&m);
13     for(i=0;i<m;i++)
14     {
15         scanf("%s",d[i].a);
16         d[i].num=niXuDui(d[i],n);
17     }   
18     for(i=1;i<m;i++)
19     {
20         flag=1;
21         for(j=0;j<m-i;j++) 
22         {
23             if(d[j].num>d[j+1].num)//选择排序 
24             {
25                 flag=0;
26                 t=d[j];
27                 d[j]=d[j+1];
28                 d[j+1]=t;
29             }
30         }
31         if(flag) break; //if(flag==1) break;
32     }
33     for(i=0;i<m;i++)
34     {
35         printf("%s\n",d[i].a);
36     }
37     return 0;
38 }
39 int niXuDui(struct DNA d,int len)//统计DNA序列变量d的逆序对个数 
40 {
41     int ans=0,i,j;
42     for(i=0;i<len;i++)//从前到尾慢慢扫 
43     {
44         for(j=i+1;j<len;j++)//两重循环,不多 
45         {
46             if(d.a[j]<d.a[i]) ans++;
47         }
48     }
49     return ans;
50 }

 

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。