本文主要是介绍C++-PTA 求解按“最多排序”到“最小排序”的顺序排列问题。,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
文章目录
- 一、题目
- 二、算法思路
- 三、代码
一、题目
二、算法思路
这道题目光从题目看起来很复杂,实际上我们可以使用函数将一个问题分解成两个问题来解决。
题目要求的是先对每一行的字符串求解对应的度量值
,然后将字符串按度量值从小到大的顺序进行排序
。
第一个问题就是如何求解度量值,比较容易发现规律的是
DAABEC
度量值为5这个例子。
计算度量值的方法如下:
字母D
:从D之后有四个字母AABC都小于D
,所以这个字母的度量值为4
字母A
:因为A是26个字母中最小的,所以从字母A之后的字符没有更小的了,其度量值为0
字母A
:度量值为0
字母B
:字母B仅大于A,而从该字母之后没有A了,所以度量值为0
字母E
:E大于C,所以度量值为1
字母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 求解按“最多排序”到“最小排序”的顺序排列问题。的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!