UC知道求一道程序题的解答
来源：百度知道 编辑：UC知道 时间：2024/06/17 12:53:40
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 contain
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 contain
#include <stdio.h>
int main()
{
char a[101][51],*t;
int i,j,m,n,k,sum[101],b[101];
for (i=0;i <=49;i++)
{
sum[i]=0;
b[i]=0;
}
scanf("%d %d",&m,&n);
for (i=0;i <n;i++)
scanf("%s",a[i]);
for (k=0;k <n;k++)
for (i=0;i <m;i++)
for (j=i+1;j <m;j++)
if (a[k][i]>a[k][j]) sum[k]++;
for(i=0;i <n;i++)
{
b[i]=i;
}
for(i=0;i <n;i++)
for(j=i+1;j <n;j++)
{
if(sum[j] <sum[i])
{
k=sum[j];
sum[j]=sum[i];
sum[i]=k;
k=b[i];
b[i]=b[j];
b[j]=k;
}
}
printf("\n");
for (k=0;k <n;k+