09 第十周--程序设计与算法（一）测验

054:成绩排序

总时间限制: 1000ms 内存限制: 65536kB

描述

给出班里某门课程的成绩单，请你按成绩从高到低对成绩单排序输出，如果有相同分数则名字字典序小的在前。

输入

第一行为n (0 < n < 20)，表示班里的学生数目；

接下来的n行，每行为每个学生的名字和他的成绩, 中间用单个空格隔开。名字只包含字母且长度不超过20，成绩为一个不大于100的非负整数。

输出

把成绩单按分数从高到低的顺序进行排序并输出，每行包含名字和分数两项，之间有一个空格。

样例输入

4

Kitty 80

Hanmeimei 90

Joey 92

Tim 28

样例输出

Joey 92

Hanmeimei 90

Kitty 80

Tim 28

代码

#include<stdio.h> 
#include<string.h>
#define Max 21
typedef struct Student{
	char name[21];
	unsigned int score;
}STU;
STU s[Max];
int n;

//输入学生个数和学生信息
void input() {
	int i;
	scanf("%d",&n);
	for(i=0;i<n;i++){
		scanf("%s",&s[i].name);
		scanf("%d",&s[i].score);
	}
}
//输出学生信息
void output() {
	int i;
	for(i=0;i<n;i++){
		printf("%s",s[i].name);
		printf(" %d",s[i].score);
		printf("\n");
	}
}
//成绩排序
void stu_sort() {
	STU temp;//构建辅助空间 
	int i,j;
	for(i=0;i<n-1;i++){//选择排序 
		for(j=i+1;j<n;j++){
			if(s[i].score<s[j].score){//后一个成绩比前一个成绩高，则交换 
				temp=s[i];
				s[i]=s[j];
				s[j]=temp;
			}
			else if(s[i].score==s[j].score){//成绩相等，按字典排序 
				int flag;
				flag=strcmp(s[i].name,s[j].name) ;//比较名字大小 
				if(flag>0) {//后面一个名字比前一个小，则交换 
					temp=s[i];
					s[i]=s[j];
					s[j]=temp;
				}
				else //后一个名字比前一个大，则不交换
					continue;
			}
		}
	}
}
int main()
{
	input();
	stu_sort();
	output();
	return 0;	
}

055:分数线划定

总时间限制: 1000ms 内存限制: 65536kB

描述

世博会志愿者的选拔工作正在 A 市如火如荼的进行。为了选拔最合适的人才，A市对所有报名的选手进行了笔试，笔试分数达到面试分数线的选手方可进入面试。面试分数线根据计划录取人数的150%划定，即如果计划录取m名志愿者，则面试分数线为排名第m*150%（向下取整）名的选手的分数，而最终进入面试的选手为笔试成绩不低于面试分数线的所有选手。

现在就请你编写程序划定面试分数线，并输出所有进入面试的选手的报名号和笔试成绩。

输入

第一行，两个整数n，m（5 ≤ n ≤ 5000，3 ≤ m ≤ n），中间用一个空格隔开，其中n 表示报名参加笔试的选手总数，m 表示计划录取的志愿者人数。输入数据保证m*150%向下取整后小于等于n。

第二行到第 n+1 行，每行包括两个整数，中间用一个空格隔开，分别是选手的报名号k（1000 ≤ k ≤ 9999）和该选手的笔试成绩s（1 ≤ s ≤ 100）。数据保证选手的报名号各不相同。

输出

第一行，有两个整数，用一个空格隔开，第一个整数表示面试分数线；第二个整数为进入面试的选手的实际人数。

从第二行开始，每行包含两个整数，中间用一个空格隔开，分别表示进入面试的选手的报名号和笔试成绩，按照笔试成绩从高到低输出，如果成绩相同，则按报名号由小到大的顺序输出。

样例输入

6 3

1000 90

3239 88

2390 95

7231 84

1005 95

1001 88

样例输出

88 5

1005 95

2390 95

1000 90

1001 88

3239 88

提示

样例说明：m150% = 3150% = 4.5，向下取整后为4。保证4个人进入面试的分数线为88，但因为88有重分，所以所有成绩大于等于88的选手都可以进入面试，故最终有5个人进入面试。

代码

#include<stdio.h>
typedef struct volunteer{
	int id;
	int score;
}VU;
VU s[5000];
int n,m,t;
float num;
int lowest_score;
//输入报名选手信息 
void InPut(){
	int i;
	scanf("%d%d",&n,&m);
	num=m*1.5;
	for(i=0;i<n;i++){
		scanf("%d%d",&s[i].id,&s[i].score);
	}	
}

//输出进入面试的志愿者信息 
void OutPut(){
	int i;
	int k=0;
	t=(int)num;
	for(i=t;i<n;i++){//判断有无相同最低分 
		if(s[i].score==s[t-1].score){
			k++;//进入面试的人+1 
		}
	}
	lowest_score=s[t-1].score;
	printf("%d %d\n",lowest_score,t+k);
	for(i=0;i<t+k;i++){
		printf("%d %d\n",s[i].id,s[i].score);
	}
}

//按分数排序
void Volunteer_Sort() {//选择排序 
	VU temp;//构建辅助空间
	int i,j;
	for(i=0;i<n-1;i++) {
		for(j=i+1;j<n;j++){
			if(s[i].score<s[j].score){
				temp=s[i];
				s[i]=s[j];
				s[j]=temp;//注意点 
			}
			else if(s[i].score==s[j].score){
				if(s[i].id>s[j].id){//序号小的放前面 
					temp=s[i];
					s[i]=s[j];
					s[j]=temp;//
				}
				else
					continue;
			}
		}
	}
}

int main(){
	InPut();
	Volunteer_Sort();
	OutPut();
	return 0;
}

056:病人排队

总时间限制: 1000ms 内存限制: 65536kB

描述

病人登记看病，编写一个程序，将登记的病人按照以下原则排出看病的先后顺序：

老年人（年龄 >= 60岁）比非老年人优先看病。
老年人按年龄从大到小的顺序看病，年龄相同的按登记的先后顺序排序。
非老年人按登记的先后顺序看病。

输入

第1行，输入一个小于100的正整数，表示病人的个数；

后面按照病人登记的先后顺序，每行输入一个病人的信息，包括：一个长度小于10的字符串表示病人的ID（每个病人的ID各不相同且只含数字和字母），一个整数表示病人的年龄，中间用单个空格隔开。

输出

按排好的看病顺序输出病人的ID，每行一个。

样例输入

5

021075 40

004003 15

010158 67

021033 75

102012 30

样例输出

021033

010158

021075

004003

102012

代码

#include<stdio.h> 
#define IntMax 101
//结构体 
typedef struct Patient{
	char id[11];
	int age;
}PT;
PT s[IntMax];
PT dest[IntMax];
int n;
int m=0;

//输入病人信息 
void InPut(){
	int i;
	scanf("%d",&n);
	for(i=0;i<n;i++){//输入id和年龄 
		scanf("%s",&s[i].id);
		scanf("%d",&s[i].age) ;
	}
}

//输出病人ID
void OutPut() {
	int i;
	for(i=0;i<m;i++){//按序输出老年人就诊名单 
		printf("%s\n",dest[i].id);
	}
}

//排序
void Pt_Sort() {	//选择排序 
	int i,j;

	PT temp;//构建辅助空间 
	for(i=0;i<n;i++){
		if(s[i].age>=60){//老年人比非老年人优先看病 
			dest[m]=s[i];
			m++;
		}	
	}	
	for(i=0;i<m-1;i++){ //老年人按照年龄从大到小顺序 
		for(j=i+1;j<m;j++){
			if(dest[i].age<dest[j].age){
				temp=dest[i];
				dest[i]=dest[j];
				dest[j]=temp;
			}
			else 
				continue; 
		}
	}
	for(i=0;i<n;i++){
		if(s[i].age<60){
			dest[m]=s[i];
			m++;
		}	
	}
		
}

int main(){
	InPut();
	Pt_Sort();
	OutPut();
	return 0;
}

057:mysort

总时间限制: 1000ms 内存限制: 65536kB

描述

程序填空题，自己编写排序函数 mysort，使得其能够对任意类型的数组排序

#include <iostream>
using namespace std;
struct A {
	int nouse1;
	int nouse2;
	int n;
};
// 在此处补充你的代码
int MyCompare1( const void * e1,const void * e2) 
{
	int * p1 = (int * ) e1;
	int * p2 = (int * ) e2;
	return * p1 - * p2;
}
int MyCompare2( const void * e1,const void * e2) 
{
	int * p1 = (int * ) e1;
	int * p2 = (int * ) e2;
	if( (* p1 %10) - (* p2 % 10))
		return (* p1 %10) - (* p2 % 10);
	else
		return * p1 - * p2;
}
int MyCompare3( const void * e1,const void * e2) 
{
	A * p1 = (A*) e1;
	A * p2 = (A*) e2;
	return p1->n - p2->n;
}
int a[20];
A b[20];
int main ()
{	
	int n;
	while(cin >> n) {
		for(int i = 0;i < n; ++i) {
			cin >> a[i];
			b[i].n = a[i];
		}
		mysort(a,n,sizeof(int),MyCompare1);
		for(int i = 0;i < n; ++i) 
			cout << a[i] << "," ;
		cout << endl;
		mysort(a,n,sizeof(int),MyCompare2);
		for(int i = 0;i < n; ++i) 
			cout << a[i] << "," ;
		cout << endl;
		mysort(b,n,sizeof(A),MyCompare3);
		for(int i = 0;i < n; ++i) 
			cout << b[i].n << "," ;
		cout << endl;
	}
	return 0;
}

输入

多组数据。每组数据以整数 n开头(n<10)，然后是n个整数

输出

对每组数据，输出三行。

第一行是整数从小倒大排序的结果

第二行是按个位数从小到大排序的结果(如果个位数相同，小的排在前面)

第三行还是整数从小倒大排序的结果

样例输入

5 21 3 76 48 445

6 73 29 45 8737 2 1

样例输出

3,21,48,76,445,

21,3,445,76,48,

3,21,48,76,445,

1,2,29,45,73,8737,

1,2,73,45,8737,29,

1,2,29,45,73,8737,

代码

void mysort(void* a,int n,int width,int(*f)(const void* e1,const void* e2))
{
    for(int i=n-1;i>=0;--i)
        for(int j=0;j<i;++j)
        {
            char* aj=(char*)a+j*width;
            char* aj1=(char*)a+(j+1)*width;
            if(f(aj,aj1)>0)
            {
                for(int k=0;k<width;k++)
                {
                    char temp=aj[k];
                    aj[k]=aj1[k];
                    aj1[k]=temp;
                }
            }
        }
}

058:从字符串中取数

总时间限制: 1000ms 内存限制: 65536kB

描述

编写GetDoubleFromString函数，该函数可以不断从字符串中取出正浮点数或整数，无数可取，则返回值小于0

#include <iostream>
#include <iomanip>
using namespace std;
double GetDoubleFromString(char * str)
{
// 在此处补充你的代码
}

int main()
{
	char line[300];
	while(cin.getline(line,280)) {
		double n;
		n = GetDoubleFromString(line);
		while( n > 0) {
			cout << fixed << setprecision(6) << n << endl;
			n = GetDoubleFromString(NULL);
		}
	}
	return 0;
}

输入

多组数据，每组数据一行

输出

针对每组数据，将其中的数输出来。每行一个数，保留小数点后面6位。输入数据中只会有正数，不用考虑负号。两个数之间有至少一个非数字非小数点的字符。

样例输入

please 121a1 stand 0.7 9.2 1010.3983 0.00001 black stand what 1324.3

12.34 45 78ab78.34

样例输出

121.000000

1.000000

0.700000

9.200000

1010.398300

0.000010

1324.300000

12.340000

45.000000

78.000000

78.340000

代码

double GetDoubleFromString(char * str)
{
 static char *p;
      if(str){
          p=str;}//把首地址p
      double num=0;
      while(*p&&!(*p>='0'&&*p<='9'))
      {
          ++p;
      }
      if(*p==0)
      {
          return -1;
      }
      while(*p>='0'&&*p<='9')
      {
          num=num*10+*p-'0';//没有pow的一种字符串转数字的方式
          ++p;
      }
      if(*p=='.')
      {
          ++p;
          double i=10;
          while(*p>='0'&&*p<='9')
          {
              num+=(*p-'0')/i;//字符转小数
              ++p;
              i=i*10;
          }
      }
      return num;

}

=0;
      while(*p&&!(*p>='0'&&*p<='9'))
      {
          ++p;
      }
      if(*p==0)
      {
          return -1;
      }
      while(*p>='0'&&*p<='9')
      {
          num=num*10+*p-'0';//没有pow的一种字符串转数字的方式
          ++p;
      }
      if(*p=='.')
      {
          ++p;
          double i=10;
          while(*p>='0'&&*p<='9')
          {
              num+=(*p-'0')/i;//字符转小数
              ++p;
              i=i*10;
          }
      }
      return num;

}

09 第十周--程序设计与算法（一）测验

054:成绩排序

055:分数线划定

056:病人排队

057:mysort

058:从字符串中取数

继续阅读

一文看懂字符串的加减乘除

极大似然法(ML)与最大期望法(EM)

C++ 第十五周报告1--《冒泡法排序》

测试理论面试题

C++实现简单顺序表

笔试面试题目：滑动窗口(二)

软件测试面试题整理

数据结构与算法（27）——排序（二）

Dijkstra--简易版（最短路径）

C经典书籍笔记——C陷阱与缺陷②(语法陷阱之优先级)一、错误案列二、优先级规律

GitHub连夜封杀！这份阿里 10W 字内部 Java 字面试手册到底有多强？

线性表之顺序表的实现

软件测试工程师跳槽：收到面试电话后，我会做的事。

C++判断素数、求最大公约数代码判断一个数是否为素数求两个数的最大公约数

SequoiaDB巨杉数据库C++驱动概述

hdu7108哈希