目錄
7-1 直接插入排序
輸入格式:
輸出格式:
輸入樣例:
輸出樣例:
7-2 尋找大富翁
輸入格式:
輸出格式:
輸入樣例:
輸出樣例:
7-3 PAT排名匯總
輸入格式:
輸出格式:
輸入樣例:
輸出樣例:
7-4 點贊狂魔
輸入格式：
輸出格式：
輸入樣例：
輸出樣例：
7-5 鏈式基數排序
輸入樣例：
輸出樣例：
7-1 直接插入排序
分數 10
全屏瀏覽題目
切換布局
作者?黃龍軍
單位?紹興文理學院
給定一個整數序列，請按非遞減序輸出采用直接插入排序的各趟排序后的結果。
輸入格式:
測試數據有多組，處理到文件尾。每組測試數據第一行輸入一個整數n（1≤n≤100），第二行輸入n個整數。
輸出格式:
對于每組測試，輸出若干行，每行是一趟排序后的結果，每行的每兩個數據之間留一個空格。
輸入樣例:
4
8 7 2 1
輸出樣例:
7 8 2 1
2 7 8 1
1 2 7 8?
#include <stdio.h>
#define MaxSize 1000
struct SqList {int r[MaxSize + 1];int length;
};
void Read(struct SqList *L, int n) {L->length = n;for (int i = 1; i <= L->length; i++) {scanf("%d", &L->r[i]);}
}
void Print(struct SqList *L) {for (int i = 1; i <= L->length; i++) {if (i > 1) printf(" ");printf("%d", L->r[i]);}printf("\n");
}
void InsertSort(struct SqList *L) {for (int i = 2; i <= L->length; i++) {if (L->r[i] < L->r[i - 1]) {L->r[0] = L->r[i];int j;for (j = i - 1; L->r[0] < L->r[j]; j--)L->r[j + 1] = L->r[j];L->r[j + 1] = L->r[0];}Print(L);}
}
int main() {int n;while (scanf("%d", &n) != EOF) {struct SqList L;Read(&L, n);InsertSort(&L);}return 0;
}
?
7-2 尋找大富翁
分數 25
全屏瀏覽題目
切換布局
作者?陳越
單位?浙江大學
胡潤研究院的調查顯示，截至2017年底，中國個人資產超過1億元的高凈值人群達15萬人。假設給出N個人的個人資產值，請快速找出資產排前M位的大富翁。
輸入格式:
輸入首先給出兩個正整數N（≤106）和M（≤10），其中N為總人數，M為需要找出的大富翁數；接下來一行給出N個人的個人資產值，以百萬元為單位，為不超過長整型范圍的整數。數字間以空格分隔。
輸出格式:
在一行內按非遞增順序輸出資產排前M位的大富翁的個人資產值。數字間以空格分隔，但結尾不得有多余空格。
輸入樣例:
8 3
8 12 7 3 20 9 5 18
輸出樣例:
20 18 12#include<stdio.h>
int main(){int n,m;int a[1000000];scanf("%d %d",&n,&m);for(int i=0;i<n;i++){scanf("%d",&a[i]);}int flag=0;int t;for(int p=n-1;p>=0;p--){flag=0;for(int i=0;i<p;i++){if(a[i]>a[i+1]){t=a[i];a[i]=a[i+1];a[i+1]=t;flag=1;}}if(flag==0) break;}if(m>n){for(int i=n-1;i>=1;i--){printf("%d ",a[i]);}printf("%d",a[0]);}else{for(int i=n-1;i>n-m;i--){printf("%d ",a[i]);}printf("%d",a[n-m]);}
}7-3 PAT排名匯總
分數 25
全屏瀏覽題目
切換布局
作者?陳越
單位?浙江大學
計算機程序設計能力考試（Programming Ability Test，簡稱PAT）旨在通過統一組織的在線考試及自動評測方法客觀地評判考生的算法設計與程序設計實現能力，科學的評價計算機程序設計人才，為企業選拔人才提供參考標準（網址http://www.patest.cn）。
每次考試會在若干個不同的考點同時舉行，每個考點用局域網，產生本考點的成績。考試結束后，各個考點的成績將即刻匯總成一張總的排名表。
現在就請你寫一個程序自動歸并各個考點的成績并生成總排名表。
輸入格式:
輸入的第一行給出一個正整數N（≤100），代表考點總數。隨后給出N個考點的成績，格式為：首先一行給出正整數K（≤300），代表該考點的考生總數；隨后K行，每行給出1個考生的信息，包括考號（由13位整數字組成）和得分（為[0,100]區間內的整數），中間用空格分隔。
輸出格式:
首先在第一行里輸出考生總數。隨后輸出匯總的排名表，每個考生的信息占一行，順序為：考號、最終排名、考點編號、在該考點的排名。其中考點按輸入給出的順序從1到N編號。考生的輸出須按最終排名的非遞減順序輸出，獲得相同分數的考生應有相同名次，并按考號的遞增順序輸出。
輸入樣例:
2
5
1234567890001 95
1234567890005 100
1234567890003 95
1234567890002 77
1234567890004 85
4
1234567890013 65
1234567890011 25
1234567890014 100
1234567890012 85
輸出樣例:
9
1234567890005 1 1 1
1234567890014 1 2 1
1234567890001 3 1 2
1234567890003 3 1 2
1234567890004 5 1 4
1234567890012 5 2 2
1234567890002 7 1 5
1234567890013 8 2 3
1234567890011 9 2 4?
#include <stdio.h>
struct stu
{char id[14]; //考號int score; //分數int kc; //考場
};
struct stu a[30000];
int bigger(const char *s1,const char *s2)
{for(int i=0;i<13;i++)if(s1[i] > s2[i])return 1;else if(s1[i] < s2[i])return 0;return 1;
}
void qsort(int l,int r)
{if(l >= r)return ;int i = l;int j = r;struct stu t = a[l];while(i != j){while(i < j && (a[j].score < t.score || a[j].score == t.score && bigger(a[j].id,t.id)))j--;while(i < j && (a[i].score > t.score || a[i].score == t.score && bigger(t.id,a[i].id)))i++;if(i < j){struct stu s = a[i];a[i] = a[j];a[j] = s;}}a[l] = a[i];a[i] = t;qsort(l,i-1);qsort(i+1,r);return ;
}
void Copy(int *b2,int *b1,int n)
{for(int i=1;i<=n;i++)b2[i] = b1[i];
}
int main()
{int n,j,i,top = 0;scanf("%d",&n);for(i=1;i<=n;i++){int k;scanf("%d",&k);for(j=0;j<k;j++){char id[14];int score;scanf("%s %d",id,&score);a[top].score = score;a[top].kc = i;strcpy(a[top].id,id);top++;}}qsort(0,top-1);int levall = 1,b1[n+1],b2[n+1],score = a[0].score;for(i=1;i<=n;i++)b1[i] = 1,b2[i] = 1;printf("%d\n",top);printf("%s %d %d %d\n",a[0].id,1,a[0].kc,1);int llevall = 1; //上一個總排名levall = 2; //總排名Copy(b2,b1,n);b1[a[0].kc]++; for(i=1;i<top;i++){if(a[i].score == a[i-1].score){printf("%s %d %d %d\n",a[i].id,llevall,a[i].kc,b2[a[i].kc]);levall++;b1[a[i].kc]++;}else{printf("%s %d %d %d\n",a[i].id,levall,a[i].kc,b1[a[i].kc]);llevall = levall;levall++;Copy(b2,b1,n);b1[a[i].kc]++; //考場的排名 }}return 0;
}
?
7-4 點贊狂魔
分數 25
全屏瀏覽題目
切換布局
作者?陳越
單位?浙江大學
微博上有個“點贊”功能，你可以為你喜歡的博文點個贊表示支持。每篇博文都有一些刻畫其特性的標簽，而你點贊的博文的類型，也間接刻畫了你的特性。然而有這么一種人，他們會通過給自己看到的一切內容點贊來狂刷存在感，這種人就被稱為“點贊狂魔”。他們點贊的標簽非常分散，無法體現出明顯的特性。本題就要求你寫個程序，通過統計每個人點贊的不同標簽的數量，找出前3名點贊狂魔。
輸入格式：
輸入在第一行給出一個正整數N（≤100），是待統計的用戶數。隨后N行，每行列出一位用戶的點贊標簽。格式為“Name?K?F1??FK?”，其中Name是不超過8個英文小寫字母的非空用戶名，1≤K≤1000，Fi?（i=1,?,K）是特性標簽的編號，我們將所有特性標簽從 1 到?107?編號。數字間以空格分隔。
輸出格式：
統計每個人點贊的不同標簽的數量，找出數量最大的前3名，在一行中順序輸出他們的用戶名,其間以1個空格分隔,且行末不得有多余空格。如果有并列，則輸出標簽出現次數平均值最小的那個，題目保證這樣的用戶沒有并列。若不足3人，則用-補齊缺失，例如mike jenny -就表示只有2人。
輸入樣例：
5
bob 11 101 102 103 104 105 106 107 108 108 107 107
peter 8 1 2 3 4 3 2 5 1
chris 12 1 2 3 4 5 6 7 8 9 1 2 3
john 10 8 7 6 5 4 3 2 1 7 5
jack 9 6 7 8 9 10 11 12 13 14
輸出樣例：
jack chris john#include<stdio.h>
typedef struct
{char name[20];int sum; //不同標簽總數int num; //點贊總數
}User;
int fact[100000000];
int main()
{int n,k;scanf("%d",&n);User users[100];int facter[100][1001];int i,j;for(i=0;i<n;i++){users[i].sum=0;scanf("%s",users[i].name);scanf("%d",&users[i].num);for(j=0;j<users[i].num;j++){scanf("%d",&facter[i][j]);fact[facter[i][j]]++;if(fact[facter[i][j]]==1)users[i].sum++;}for(j=0;j<users[i].num;j++) //重新歸0fact[facter[i][j]]=0;}//進行排序(這邊建議使用選擇排序)int max;for(i=0;i<n-1;i++){max=i;for(j=i+1;j<n;j++){if(users[max].sum<users[j].sum)max=j;else if(users[max].sum==users[j].sum&&users[max].num>users[j].num)max=j;}User t=users[i];users[i]=users[max];users[max]=t;}if(n<3){for(i=0;i<n-1;i++)printf("%s ",users[i].name);printf("%s",users[n-1].name);for(i=0;i<3-n;i++)printf(" -");}else{printf("%s %s %s",users[0].name,users[1].name,users[2].name);}return 0;
}7-5 鏈式基數排序
分數 15
全屏瀏覽題目
切換布局
作者?王東
單位?貴州師范學院
實現鏈式基數排序，待排序關鍵字n滿足1≤n≤1000，最大關鍵字數位≤5。
輸入樣例：
第一行輸入待排序個數n（1≤n≤1000）,再輸入n個數(n的數位≤5)。
10
278 109 63 930 589 184 505 269 8 83
輸出樣例：
輸出每趟分配-收集后鏈表中的關鍵字，趟數為序列中最大值的數位（如樣例中930的數位為3），每行結尾有空格。
930 63 83 184 505 278 8 109 589 269
505 8 109 930 63 269 278 83 184 589
8 63 83 109 184 269 278 505 589 930 #include<stdio.h>
struct tong{int a[1000];int sum;//sum指的是存入桶中的數據個數
};
typedef struct tong tong;
int ad[1000];
int findmax(int n){int max=0;int t;int weishu=0;for(int i=0;i<n;i++){weishu=0;t=ad[i];while(t!=0){t=t/10;weishu++;}if(weishu>max)max=weishu;}return max;
}
int main(){int n;int t;tong ts[10];for(int i=0;i<10;i++)ts[i].sum=0;scanf("%d",&n);for(int i=0;i<n;i++)scanf("%d",&ad[i]);//接下來我們要找出最大位數int wei=findmax(n);for(int i=0;i<wei;i++){for(int j=0;j<n;j++){t=ad[j];t=t/pow(10,i);t=t%10;ts[t].a[ts[t].sum++]=ad[j];}//接下來取出桶中數據更新ad數組int n1=0;for(int j=0;j<10;j++){ //10個桶for(int k=0;k<ts[j].sum;k++){ad[n1++]=ts[j].a[k];}}//打印for(int j=0;j<n;j++){printf("%d ",ad[j]);}printf("\n");//進行桶的歸0for(int j=0;j<10;j++){//數組沒必要更新，反正會覆蓋ts[j].sum=0;}}
}?
 屏切換)
-自動化用例編寫思路 (使用pytest編寫一個測試腳本))
