|
日歷
統計
- 隨筆 - 30
- 文章 - 0
- 評論 - 51
- 引用 - 0
導航
常用鏈接
留言簿(4)
隨筆分類
隨筆檔案
ACM
搜索
最新評論
閱讀排行榜
評論排行榜
|
昨天晚上寫完了 這道題，早上過來提交。 主要用到了插入排序算法，并且參看了桶排序算法，如果大家有什么好的想法，希望能夠共享一下，嘿嘿！我的代碼有哪里寫的不好，也請大家指教！
1 #include <stdlib.h>
2#include <stdio.h>
3typedef struct dNANumber
4   {
5 char ch[100];
6 int count;
7 }DNANumber;
8
9void Sort(DNANumber *arr, int rows)
10{
11 int i, j;
12 DNANumber temp;
13 for(i = 1; i < rows; i++)
14  {
15 temp = arr[i];
16 for(j = i-1; j >= 0; j--)
17 {
18 if(arr[j].count > temp.count)
19 arr[j+1] = arr[j];
20 else
21 break;
22 }
23 arr[j+1] = temp;
24 }
25 return;
26}
27
28int Index(char ch)
29{
30 switch(ch)
31 {
32 case 'A':
33 return 0;
34 case 'C':
35 return 1;
36 case 'G':
37 return 2;
38 case 'T':
39 return 3;
40 }
41}
42
43void CountNumber(DNANumber *dna, int length)
44{
45 int count = 0;
46 int letter[4] = {0,0,0,0};
47 int i, j;
48 int temp;
49
50 for(i = 0; i < length; i++)
51 {
52 letter[Index(dna->ch[i])]++;
53 }
54
55 for(i = length-1; i >= 0; i--)
56 {
57 temp = Index(dna->ch[i]);
58 for(j = temp+1; j < 4; j++)
59 {
60 count += letter[j];
61 }
62 letter[temp]--;
63 }
64 dna->count = count;
65 return;
66}
67int main(int argc, char* argv[])
68{
69 int length = 0, rows = 0;
70 int i;
71 DNANumber dnaArray[10000];
72 //DNANumber *dna;
73
74 scanf("%d %d", &length, &rows);
75 for(i = 0; i < rows; i++)
76 {
77 dnaArray[i].count=0;
78 scanf("%s", dnaArray[i].ch);
79 CountNumber(&dnaArray[i], length);
80 }
81
82 Sort(dnaArray, rows);
83
84 for(i = 0; i < rows; i++)
85 {
86 printf("%s\n", dnaArray[i].ch);
87 }
88 return 0;
89}
90
91
92
評論:
-
# re: acm1007探討
Posted @ 2009-01-01 11:40
首先謝謝你的代碼。
你的代碼讓我找出了我的錯誤，呵呵
我的代碼如下：
/*整體思想很簡單，用chag函數求得每個串的逆序數返回。而主函數接收并保存。然后根據逆序數排序輸出即可*/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int chag(char *p,int n)
{
int i,j,sum=0;
for(i=0;i<n-1;i++)
for(j=i+1;j<n;j++)
if(*(p+i)>*(p+j))
sum++;
return sum;
}
int main(void)
{
int n,m,i,j,t,sav[100];
char pre[101][51],cop[51];
scanf("%d %d",&n,&m);
for(i=0;i<m;i++)
{
scanf("%s",pre[i]);
sav[i]=chag(pre[i],n);
}
for(i=0;i<m-1;i++)
for(j=i+1;j<m;j++)
if(sav[i]>sav[j])
{
t=sav[i];
sav[i]=sav[j];
sav[j]=t;
strcpy(cop,pre[i]);
strcpy(pre[i],pre[j]);
strcpy(pre[j],cop);
}
for(i=0;i<m;i++)
printf("%s\n",pre[i]);
system("PAUSE");
return 0;
}
回復 更多評論
|