DNA

开发平台：
Java

DNASorting.java：源码内容
							import java.io.*;
public class DNASorting {
	/**Cataloguing a sequence of DNA strings 
	 * @param args the command line arguments
	 */
	
	public static void main(String[] args) throws IOException{
		//REQUIRES:Enter an integer M, then a blank line followed by M datasets
		//         The first line of each dataset contains two integers: 
		//         a positive integer n ( ) giving the length of the strings;
		//         and a positive integer m ( ) giving the number of strings. 
		//         These are followed by m lines, each containing a string of length n. 
		//EFFECTS: For each dataset, output the list of input strings, 
		//         arranged from ``most sorted'' to ``least sorted''. 
		//         If two or more strings are equally sorted, list them
		//         in the same order they are in the input file.
		 
		java.io.LineNumberReader r = new java.io.LineNumberReader(new java.io.InputStreamReader(System.in));	        	       
	        
	    String s;
	    char[] datasetEach;	        
	    int M;
	        
	    while ( (s = r.readLine()) != null){
	    	if (Integer.valueOf(s.trim()).intValue() == 0){
	    		System.exit(0);
	            return;
	        }
	            
	        M = Integer.valueOf(s.trim()).intValue();
	        for(int a = 0; a < M; M++){
	        String s1 = r.readLine();
	        String s2 = (r.readLine()).trim();
	           
	        String s3 = s2.substring(0,s2.length()-2);	           
	        String s4 = s2.substring(s2.length()-1,s2.length());
	           
	        int n = Integer.parseInt(s3);
	        int m = Integer.parseInt(s4);
	        datasetEach = new char[n + 1];
	        String [] dataset= new String [m]; 
	 
	        for (int i = 0; i < m; i++) {
	        	// Read in a dataset.
	        	dataset[i] = "0" +r.readLine(); 
	        	
	            for (int j = 0; j < n + 1 ; j++)
	            	datasetEach[j] = dataset[i].charAt(j);	                
	                
	            int counter = 0;
	        		
	            //calculate the inversionValue of each line 
	            for(int p = 1; p < n ;p++ ){
	        		for(int q = p + 1; q < n + 1; q++){
	        			counter += inversionValue(datasetEach[p], datasetEach[q]);
	        		} 
	        	}
	        	
	            //add the counter into each line of the dataset; 
	        	Object o =new Integer(counter);
	        	String s6 = o.toString();
	            dataset[i] = new String(s6 + dataset[i].substring(1));		                           				            
			}
	            
	        //sort each line of the dataset,arranged from ''most sorted'' to ''least sorted''
	        for(int i = 1; i < m; i++){
	        	for(int j = 0; j < m-1; j++){
	        		int e = Integer.parseInt(dataset[j].substring(0,dataset[j].length()-n));
	        		int f = Integer.parseInt(dataset[j + 1].substring(0,dataset[j + 1].length()-n));
	        		
	        		if(e > f){
	        			String g;
	        			g = dataset[j];
	        			dataset[j] = dataset[j + 1];
	        			dataset[j + 1] = g;
	        		}
	        	}
	        }
	            
	        //output the result
	        for(int i = 0; i < m; i++){
	            System.out.println(dataset[i].substring(dataset[i].length() - n,dataset[i].length()));
	        }
	   }
   }
}
	private static int inversionValue(char a, char b){
		//EFFECTS:calculate the inversionValue of two chars;
	if(a > b)
		return 1;
	else 
		return 0;
	}
	
}

						