浙江大学MOOC数据结构-陈越、何钦铭 编程练习题(第十讲)

tech2023-02-24  108

浙江大学MOOC数据结构-陈越、何钦铭 编程练习题(第十讲)

编程说明 编程环境:平台运行 编程语言:C or C++

第一题代码

//桶排序 #include <stdio.h> #include <stdlib.h> int main() { int A[51]={0}; int N, Tmp; scanf("%d",&N); for(int i=0;i<N;i++) { scanf("%d",&Tmp); A[Tmp]++; } for(int i=0;i<51;i++) { if(A[i]) printf("%d:%d\n",i,A[i]); } return 0; }

第二题代码

/* 思路:对每一个用户建立结构体,结构体应该存在用户id、分数数组、总分数、满分数量、是否满足输出条件 读取数据后初始化结构体的内容,并进一步挖掘出满分数量、总分数、输出条件 运用sort进行降序排列,其中调用了Comp比较函数 最后依据条件进行输出即可 */ #include <stdio.h> #include <stdlib.h> #include <algorithm> //#include <windows.h> #include "iostream" using namespace std; int N, K, M;//用户数量、问题总数量、提交总数量 int perfect_score[6];//题目的满分 struct Node { int user_id;//用户id int score[6] = { -2, -2, -2, -2, -2, -2 };//每个题目对应分数 int total_score = 0;//总分数 int perfect_num = 0;//满分题目数量 bool print_flag = false;//是否输出 } stu[10001]; void Inf_Get(void);//信息提取 int Cmp(const Node stu1, const Node stu2); int main() { scanf("%d %d %d", &N, &K, &M); for (int i = 1; i <= K; i++) { scanf("%d", &perfect_score[i]); } while (M--) { int stuId, proId, score; scanf("%d %d %d", &stuId, &proId, &score); stu[stuId].user_id = stuId; if(score > stu[stuId].score[proId]) stu[stuId].score[proId] = score; } Inf_Get(); sort(stu + 1, stu + 1 + N, Cmp); int rank = 1; int n = 0; int tmp = stu[1].total_score; for (int i = 1; i <= N; i++) { if (stu[i].print_flag)//每个人的情况打印 { if (stu[i].total_score == tmp)//如果当前人总分数与上一个人总分数相同 { n++; } else { tmp = stu[i].total_score; rank = rank + n; n = 1; } printf("%d %05d %d", rank, stu[i].user_id, stu[i].total_score); for (int k = 1; k <= K; k++) { if (stu[i].score[k] >= 0) printf(" %d", stu[i].score[k]); else printf(" -"); } printf("\n"); } } //system("pause"); return 0; } void Inf_Get(void) { for (int i = 1; i <= N; i++)//用户 { for (int j = 1; j <= K; j++)//用户题目分数 { if (stu[i].score[j] >= 0) { stu[i].print_flag = true;//有一个正数分数,则可以进行输出 stu[i].total_score += stu[i].score[j];//正数分数进行累加 } //感觉这个点挺重要的,放在语句段的哪个位置很重要 if (stu[i].score[j] == -1) stu[i].score[j] = 0; if (stu[i].score[j] == perfect_score[j])//分数比对,与满分比对一致,则满分数目自增 stu[i].perfect_num++; } } } int Cmp(const Node stu1, const Node stu2) { if (stu1.total_score == stu2.total_score)//先看总分数 { if (stu1.perfect_num == stu2.perfect_num)//再看满分数量 { return stu1.user_id < stu2.user_id;//再看学号 } else { return stu1.perfect_num > stu2.perfect_num; } } else { return stu1.total_score > stu2.total_score; } }

第三题代码

/* 表排序 建立T[]数组,T[i]中存放着应该存放在A[i]位置元素的下标 */ #include <stdlib.h> #include <stdio.h> int A[100000]; int T[100000]; int N; int flag; int Cnt=0;//交换次数 int main() { scanf("%d", &N); for(int i=0; i<N; i++) { scanf("%d",&A[i]); T[A[i]]=i; } for(int i=0; i<N; i++) { if(i!=A[i])//非单元素环 { flag=0;//环是否有零元素的标志位 while(i!=A[i]) { if(A[i]==0) { flag=1; } A[i]=i; i=T[i]; Cnt++; } if(flag)//环有零元素则-1 Cnt--; else//环没有零元素则+1 Cnt++; } } printf("%d", Cnt); return 0; }
最新回复(0)