C++-PTA 求解按“最多排序”到“最小排序”的顺序排列问题。

本文主要是介绍C++-PTA 求解按“最多排序”到“最小排序”的顺序排列问题。，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、题目

二、算法思路

这道题目光从题目看起来很复杂，实际上我们可以使用函数将一个问题分解成两个问题来解决。
题目要求的是先对每一行的字符串求解对应的度量值，然后将字符串按度量值从小到大的顺序进行排序。

第一个问题就是如何求解度量值，比较容易发现规律的是DAABEC度量值为5这个例子。
计算度量值的方法如下：

1. 字母D：从D之后有四个字母AABC都小于D，所以这个字母的度量值为4
2. 字母A：因为A是26个字母中最小的，所以从字母A之后的字符没有更小的了，其度量值为0
3. 字母A：度量值为0
4. 字母B：字母B仅大于A，而从该字母之后没有A了，所以度量值为0
5. 字母E：E大于C，所以度量值为1
6. 字母C：由于C位于末尾，右侧没有更小的了，度量值为0
   最后就是将步骤1-6每个字母的度量值进行相加，所以DAABEC的度量值就为5了

然后就是设计一个结构体，存储DNA序列和对应的度量值。
如果你不清楚结构体的知识，可以到C 结构体 | 菜鸟教程中查看，定义结构体的方法不止下面一种。

struct letter
{string dna;//DNA序列int len=0;//度量值
};

因为DNA序列不止一个，所以在定义的时候就需要定义成结构体数组。

letter xulie[102];//结构体数组

先创建一个函数，用于计算一个字符串的度量值并返回度量值。
字母a-z对应的ASCII码是65-90，而字母A-Z对应的ASCII码是97-122。
我们对字符进行int类型转换就可以直接转换成对应的ascii码了。

int check_len(string dna,int n)//计算字符串对应的度量值
{int len = 0;int i,j;for(i=0;i<n;i++)//遍历整个字符串{for(j=i;j<n;j++)//遍历从i之后的字符串{if((int)dna[i]>(int)dna[j])//若ascii越大，即字母较大时{len++;}}}return len;
}

对每一个dna序列计算度量值

for(i=1;i<=m;i++)//计算度量值xulie[i].len = check_len(xulie[i].dna,n);

判断完所有dna序列的度量值后，就可以进行冒泡递增排序。
排序完毕后就可以按顺序输出所有的dna序列了。

for(i=1;i<=m;i++)//根据度量值进行递增排序{for(j=1;j<m;j++)//字符串数组尾部不需要排序{if(xulie[j].len>xulie[j+1].len)//当前的度量值大于后者时{//dna序列替换string tmp_dna = xulie[j].dna;xulie[j].dna = xulie[j+1].dna;xulie[j+1].dna = tmp_dna;//度量值替换int tmp = xulie[j].len;xulie[j].len = xulie[j+1].len;xulie[j+1].len = tmp;}}}

三、代码

//作者：小狐狸
#include<iostream>
using namespace std;
struct letter
{string dna;//DNA序列int len=0;//度量值
};
int check_len(string dna,int n)//计算字符串对应的度量值
{int len = 0;int i,j;for(i=0;i<n;i++)//遍历整个字符串{for(j=i;j<n;j++)//遍历从i之后的字符串{if((int)dna[i]>(int)dna[j])//若ascii越大，即字母较大时{len++;}}}return len;
}
int main()
{int n;//字符串长度int m;//字符串个数int i,j;cin>>n>>m;letter xulie[102];//结构体数组for(i=1;i<=m;i++)//输入cin>>xulie[i].dna;for(i=1;i<=m;i++)//计算度量值xulie[i].len = check_len(xulie[i].dna,n);for(i=1;i<=m;i++)//根据度量值进行递增排序{for(j=1;j<m;j++)//字符串数组尾部不需要排序{if(xulie[j].len>xulie[j+1].len)//当前的度量值大于后者时{//dna序列替换string tmp_dna = xulie[j].dna;xulie[j].dna = xulie[j+1].dna;xulie[j+1].dna = tmp_dna;//度量值替换int tmp = xulie[j].len;xulie[j].len = xulie[j+1].len;xulie[j+1].len = tmp;}}}for(i=1;i<=m;i++)//输出cout<<xulie[i].dna<<endl;return 0;
}

这篇关于C++-PTA 求解按“最多排序”到“最小排序”的顺序排列问题。的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---