POJ1007 DNA Sorting

发布时间:2016-12-11 19:56:54 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"POJ1007 DNA Sorting",主要涉及到POJ1007 DNA Sorting方面的内容,对于POJ1007 DNA Sorting感兴趣的同学可以参考一下。

POJ上的一道题目: 题目大意: 序列“未排序程度”的一个计算方式是元素乱序的元素对个数。例如:在单词序列“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   今天被这道题目坑了一天,唉,说多了全是泪,但还是要说的,免得广大程序猿同志跟我一样,其实这道题目不是很难,我设计的程序也没有错误,只是POJ网站不支持某些库函数而已,所以,在做这些题目的时候,不要轻易使用类似 fflush() 之类的函数,今天我一整天检查不出bug就是因为这个fflush()。   虽然简单,还是大概说一下思路吧:   1、纯粹使用数组来实现比较麻烦,当然也是可以实现的,我的第一个程序就是用数组实现的,选取的数据结构为: typedef struct { int DNAnum; char str[52]; }NodeDNA;2、计算每个字符串的逆序数,根据题意来计算即可; int DNAcount(char* destination, int len) { /* 统计每个字符串的DNA值 */ int iterX = 0; int iterY = 0; int cnt = 0; for(iterX = 0; iterX < len - 1; iterX++) { if(destination[iterX] == 'A') { continue; } for(iterY = iterX + 1; iterY < len; iterY++) { if(destination[iterX] > destination[iterY]) { cnt++; } } } return cnt; }字符串里面假设有字母 'A' ,是可以直接跳过的,因为字母 'A' 不影响逆序数,所以,程序才加入了if语言来判断;   3、接下来就是对逆序数排序了,可以采用直接货冒泡排序,快速排序,这两种排序我都试过,没有超出时间要求,不过快速排序不用自己写,直接调用qsort()函数即可;下面贴出完整代码 #include <stdio.h> #include <stdlib.h> typedef struct { int DNAnum; char str[52]; }NodeDNA; int DNAcount(char* destination, int len) { /* 统计每个字符串的DNA值 */ int iterX = 0; int iterY = 0; int cnt = 0; for(iterX = 0; iterX < len - 1; iterX++) { if(destination[iterX] == 'A') { continue; } for(iterY = iterX + 1; iterY < len; iterY++) { if(destination[iterX] > destination[iterY]) { cnt++; } } } return cnt; } int cmp(const void* a,const void* b) { NodeDNA* x=(NodeDNA*)a; NodeDNA* y=(NodeDNA*)b; return (x -> DNAnum) - (y -> DNAnum); } int main(void) { NodeDNA NoDNA[101]; int col = 0; int row = 0; int iter = 0; //scanf("%d%d", &col, &row); //fflush(stdin); while( scanf("%d%d", &col, &row) != EOF ) { getchar(); for(iter = 0; iter < row; iter++) { gets(NoDNA[iter].str); NoDNA[iter].DNAnum = DNAcount(NoDNA[iter].str, col); } qsort(NoDNA, row, sizeof(NodeDNA),cmp); for(iter = 0; iter < row; iter++) { puts(NoDNA[iter].str); } } return 0; }另外,需要说明的一点是,计算逆序数的还有一个复杂度为O(n)的算法; int InversionNumber(char* s,int len) { int ans=0; //s逆序数 int A, C, G , i; //各个字母出现次数 A = C = G = 0; for( i = len-1;i >= 0;i--) { switch(s[i]) { case 'A':A++;break; //A是最小的,无逆序数 case 'C': { C++; ans+=A; //当前C后面出现A的次数就是这个C的逆序数 break; } case 'G': { G++; ans+=A; ans+=C; break; } case 'T': { ans+=A; ans+=C; ans+=G; break; } } } return ans; } 注:本博客与博客园上的博客为同一博客主:http://www.cnblogs.com/bestDavid/

上一篇:Git快速上手命令
下一篇:海外省电应用市场:本土化为先锋,高技术为基础

相关文章

相关评论