程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> DNA Sorting(DNA排序)

DNA Sorting(DNA排序)

編輯:C++入門知識

Description

One measure of ``unsortedness'' in a sequence is the number of pairs of entries that are out of order with respect to each other. For instance, in the letter sequence ``DAABEC'', this measure is 5, since D is greater than four letters to its right and E is greater than one letter to its right. This measure is called the number of inversions in the sequence. The sequence ``AACEDGG'' has only one inversion (E and D)---it is nearly sorted---while the sequence ``ZWQM'' has 6 inversions (it is as unsorted as can be---exactly the reverse of sorted).

You are responsible for cataloguing a sequence of DNA strings (sequences containing only the four letters A, C, G, and T). However, you want to catalog them, not in alphabetical order, but rather in order of ``sortedness'', from ``most sorted'' to ``least sorted''. All the strings are of the same length.

Input

The first line contains two integers: a positive integer n (0 < n <= 50) giving the length of the strings; and a positive integer m (0 < m <= 100) giving the number of strings. These are followed by m lines, each containing a string of length n.
Output

Output the list of input strings, arranged from ``most sorted'' to ``least sorted''. Since two strings can be equally sorted, then output them according to the orginal order.
Sample Input

10 6
AACATGAAGG
TTTTGGCCAA
TTTGGCCAAA
GATCAGATTT
CCCGGGGGGA
ATCGATGCATSample Output

CCCGGGGGGA
AACATGAAGG
GATCAGATTT
ATCGATGCAT
TTTTGGCCAA
TTTGGCCAAASource

East Central North America 1998


[cpp]
#include <iostream>  
#define INF 0xffffff        //定義最大地址  
 
using namespace std; 
 
char str[200][200];     //二維數組寫入字符串每一個字符的值  
int num[200];           //逆序數的值  
 
int main() 

    int m,n; 
    memset(num,0,sizeof(num)); 
    cin>>n; 
    cin>>m; 
 
    num[0] = INF;       //初始化num[0]為最大地址,方便後來的選擇排序法輸出字符串數組  
    for (int i=1;i<=m;i++) 
    { 
        cin>>str[i]; 
         
        //求出逆序數  
        for (int j=0;j<n;j++) 
        { 
            for (int k=j+1;k<n;k++) 
            { 
                if (str[i][j] > str[i][k]) 
                { 
                    num[i]++; 
                } 
            } 
        } 
 
    } 
 
    int p=0; 
 
    //選擇排序法,輸出字符串數組  
    for (int i=1;i<=m;i++) 
    { 
        for (int j=1;j<=m;j++) 
        { 
            if (num[j] < num[p]) 
            { 
                p = j; 
            } 
        } 
        cout<<str[p]<<endl; 
        num[p] = INF;       //將當前num[p]置為最大地址,方便下一個循環的比較  
 
    } 
 
    system("pause"); 
    return 0; 
     

#include <iostream>
#define INF 0xffffff  //定義最大地址

using namespace std;

char str[200][200];  //二維數組寫入字符串每一個字符的值
int num[200];   //逆序數的值

int main()
{
 int m,n;
 memset(num,0,sizeof(num));
 cin>>n;
 cin>>m;

 num[0] = INF;  //初始化num[0]為最大地址,方便後來的選擇排序法輸出字符串數組
 for (int i=1;i<=m;i++)
 {
  cin>>str[i];
  
  //求出逆序數
  for (int j=0;j<n;j++)
  {
   for (int k=j+1;k<n;k++)
   {
    if (str[i][j] > str[i][k])
    {
     num[i]++;
    }
   }
  }

 }

 int p=0;

 //選擇排序法,輸出字符串數組
 for (int i=1;i<=m;i++)
 {
  for (int j=1;j<=m;j++)
  {
   if (num[j] < num[p])
   {
    p = j;
   }
  }
  cout<<str[p]<<endl;
  num[p] = INF;  //將當前num[p]置為最大地址,方便下一個循環的比較

 }

 system("pause");
 return 0;
 
}

 
 


 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved