206
poj 1007 DNA Sorting【逆序對】
終於可以說：沒有那麼水了（雖然還是很水）。。。。。。
關於逆序數的題目，開始用塑料的冒泡排序一直WA，後來自己寫一個，終於過了，要求是穩定的！！！！！！！
AC的代碼：
#include <stdio.h>
#include <string.h>
char DNA[105][55]; //輸入原DNA序列
int visit[105];
int Inversion(int nTh,int len)
{
int i,j,count=0;
for(i=0;i<len;i++)
for(j=i;j<len;j++)
if(DNA[nTh][i]>DNA[nTh][j])
count++;
return count;
}
int main()
{
//1A，2B, 3C, 4D, 5E, 6F, 7G, 8H, 9I, 10J, 11K, 12L, 13M, 14N, 15O, 16P, 17Q, 18R, 19S, 20T, 21U, 22V, 23W, 24X, 25Y, 26Z
int inverNum[102]; //對應每個數列的逆序數
int n;
int m;
scanf("%d%d",&n,&m);
int i,j;
for(i=0;i<m;i++)
{
scanf("%s",DNA[i]);
inverNum[i]=Inversion(i,n); //傳入排位第i個的DNA序列，和序列長度
//test OK
//printf("逆序數為：%d\n",inverNum[i]);
}
//每次都找到inverNum最小的序列打印，一定是穩定的
int min;
int pos;
for(i=0;i<m;i++)
{
min=1000; //開始放min為一個很大的數
for(j=0;j<m;j++)
if(visit[j]==0 && min>inverNum[j])
{
min=inverNum[j];
pos=j;
}
visit[pos]=1; //標記被訪問過了
printf("%s\n",DNA[pos]);
}
return 0;
}
WA 2次的代碼：
#include <stdio.h>
#include <string.h>
char DNA[105][55]; //輸入原DNA序列
int Inversion(int nTh,int len)
{
int i,j,count=0;
for(i=0;i<len;i++)
for(j=i;j<len;j++)
if(DNA[nTh][i]>DNA[nTh][j])
count++;
return count;
}
int main()
{
//1A，2B, 3C, 4D, 5E, 6F, 7G, 8H, 9I, 10J, 11K, 12L, 13M, 14N, 15O, 16P, 17Q, 18R, 19S, 20T, 21U, 22V, 23W, 24X, 25Y, 26Z
int inverNum[102]; //對應每個數列的逆序數
int n;
int m;
scanf("%d%d",&n,&m);
int i,j;
for(i=0;i<m;i++)
{
scanf("%s",DNA[i]);
inverNum[i]=Inversion(i,n); //傳入排位第i個的DNA序列，和序列長度
//test OK
//printf("逆序數為：%d\n",inverNum[i]);
}
//直接用冒泡排序（穩定的）
char tmpN,temp[55];
for(i=0;i<m;i++)
for(j=i;j<m;j++)
if(inverNum[i]>=inverNum[j])
{
//交換逆序數
tmpN=inverNum[j];
inverNum[j]=inverNum[i];
inverNum[i]=tmpN;
//交換DNA序列
strcpy(temp,DNA[j]);
strcpy(DNA[j],DNA[i]);
strcpy(DNA[i],temp);
}
for(i=0;i<m;i++)
printf("%s\n",DNA[i]);
return 0;
}
中文題目：
題目大意：
序列“未排序程度”的一個計算方式是元素亂序的元素對個數。例如：在單詞序列“DAABEC'”中，因為D大於右邊四個單詞，E大於C，所以計算結果為5。這種計算方法稱為序列的逆序數。序列“AACEDGG”逆序數為1（E與D）——近似排序，而序列``ZWQM'' 逆序數為6（它是已排序序列的反序）。
你的任務是分類DNA字符串（隻有ACGT四個字符）。但是你分類它們的方法不是字典序，而是逆序數，排序程度從好到差。所有字符串長度相同。
輸入：
第一行包含兩個數：一個正整數n（0<n<=50）表示字符串長度，一個正整數m（0<m<=100）表示字符串個數。接下來m行，每行一個長度為n的字符串。
輸出：
輸出輸入字符串列表，按排序程度從好到差。如果逆序數相同，就原來順序輸出。
樣例輸入：
10 6
AACATGAAGG
TTTTGGCCAA
TTTGGCCAAA
GATCAGATTT
CCCGGGGGGA
ATCGATGCAT
樣例輸出:
CCCGGGGGGA
AACATGAAGG
GATCAGATTT
ATCGATGCAT
TTTTGGCCAA
TTTGGCCAAA
大致題意：
輸入m個長度為n的DNA序列，把他們按照逆序數從小到大穩定排序輸出。
PS:“穩定排序”就是當序列中出現A1==A2時，排序前後A1與A2的相對位置不發生改變。
最後更新：2017-04-03 14:53:41