poj 1007
发布日期:2021-10-23 19:22:38 浏览次数:2 分类:技术文章

本文共 3171 字,大约阅读时间需要 10 分钟。

DNA Sorting
Time Limit: 1000MS   Memory Limit: 10000K
Total Submissions: 73258   Accepted: 29242

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 6AACATGAAGGTTTTGGCCAATTTGGCCAAAGATCAGATTTCCCGGGGGGAATCGATGCAT

Sample Output

CCCGGGGGGAAACATGAAGGGATCAGATTTATCGATGCATTTTTGGCCAATTTGGCCAAA 解题报告: 该题属于常规题,首先读取所有输入存入数组中,按照度量指标计算出sort的值,然后利用快速排序算法按照sort值排序. 注意点: 1.读入一个字符串用scanf("%s", a);避免循环读取每一个字符,如scanf("%c", a[i]); 2.快排的partition中,注意第43行和46行,是++l,不是l++; 代码如下:
1 #include 
2 #include
3 4 typedef struct dna{ 5 char dna_str[51]; 6 int sort_count; 7 }dna_t; 8 9 dna_t *dna[100];10 int m, n;11 12 void count(dna_t *node){13 int c = 0;14 for(int i = 0; i < n; ++i){15 for(int j = i + 1; j < n; ++j){16 if(node->dna_str[i] > node->dna_str[j])17 ++c;18 }19 }20 node->sort_count = c;21 }22 23 void input(){24 scanf("%d%d", &n, &m);25 for(int i = 0; i < m; ++i){26 dna[i] = (dna_t*)malloc(sizeof(dna_t));27 scanf("%s", &dna[i]->dna_str);28 count(dna[i]);29 }30 }31 32 void swap(dna_t **a, dna_t **b){33 dna_t *temp = *a;34 *a = *b;35 *b = temp;36 }37 38 int partition(int p, int q){39 int s = dna[q]->sort_count;40 int l = p - 1;41 for(int i = p; i < q; ++i){42 if(dna[i]->sort_count <= s){43 swap(&dna[i], &dna[++l]);44 }45 }46 swap(&dna[q], &dna[++l]);47 return l;48 }49 50 void sort(int p, int q){51 if(p < q){52 int m = partition(p, q);53 sort(p, m - 1);54 sort(m + 1, q);55 }56 }57 58 void output(){59 for(int i = 0; i < m; ++i){60 printf("%s\n", dna[i]->dna_str);61 }62 }63 64 int main(int argc, char const *argv[])65 {66 input();67 sort(0, m - 1);68 output();69 return 0;70 }

 

 

转载于:https://www.cnblogs.com/salious/archive/2013/05/27/3102090.html

转载地址:https://blog.csdn.net/weixin_30624825/article/details/98914968 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:python不使用系统库中的排序方法判断一个数组是否是有序数组
下一篇:SpringMVC的工作流程-005

发表评论

最新留言

做的很好,不错不错
[***.243.131.199]2024年03月11日 01时57分56秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

python mod,mod_python的安装 2019-04-21
python分析彩票数据,这波太炸了!Python脚本可视化居然可以这么玩 2019-04-21
简单的mysql重置root密码,重置mysql的root密码最简单的方法 2019-04-21
用matlab仿真mmc环流抑制器,一种基于准PR控制原理的MMC阀组环流抑制方法 2019-04-21
oracle 排序的分析函数,Oracle SQL:使用分析排序函数 2019-04-21
oracle direct for hdfs xi下载,ORACLE连接HDFS有个专项的解决方案 2019-04-21
java 403怎么抛出_java – 如何在Spring MVC中返回403禁止? 2019-04-21
java jsch工具类_Java工具集-JSch连接远程服务器工具类 2019-04-21
cmd背景变红1003无标题_怎样修改cmd中文字的大小、颜色和背景颜色呢 原来是这样的... 2019-04-21
php rand() 重复,php – mt_rand()给我总是相同的数字 2019-04-21
php taglib.php,thinkphp5 taglib自定义标签教程 2019-04-21
java常用包类 array,Java中的StringBuffer和数组Arrays以及常用类型的包装类 2019-04-21
ctf常见php,CTF中常见的PHP伪协议 2019-04-21
php语言冒泡法,PHP 冒泡排序法 2019-04-21
php如何数组去重复,PHP如何去除数组重复元素? 2019-04-21
java转换ab的值,查看新闻/公告--[整理]Java将AB1234形式的16进制字符串转换为10进制数值,考虑字节序的影响.... 2019-04-21
ui php h5,画出自己的UI组件的详情 2019-04-21
linux服务文件编写,linux编写systemd下服务脚本 2019-04-21
hdfs linux 目录是否存在,Linux中判断hdfs文件是否存在 2019-04-21
linux学习需要什么基础,学linux需要什么基础? 2019-04-21