Java教程

头歌 | 数据结构与算法课程设计-算法与竞赛(第1章) - 入门指南

本文主要是介绍头歌 | 数据结构与算法课程设计-算法与竞赛(第1章) - 入门指南,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

算法在计算机领域有着十分重要的地位,不仅具有深远的理论意义,而且解决了许多实际的问题,提高了程序执行效率。由此催生了一系列以算法为核心的竞赛,意在丰富和创造运用计算机解决实际问题的能力。随着各类算法竞赛的快速发展,规模也逐步扩大,受到了全世界范围内各高校、互联网公司和相关单位的认可和重视。

目前比较火热和主流的算法竞赛有ACM国际大学生程序设计竞赛(ACM International Collegiate Programming Contest,简称ACM-ICPC或ICPC)和中国大学生程序设计竞赛(China Collegiate Programming Contest, 简称CCPC)。他们以团队的形式代表各学校参赛,每队由至多3名队员组成。比赛期间,每队使用1台电脑需要在5个小时内使用C、C++、Pascal或Java中的一种编写程序解决7到13个问题。程序完成之后提交裁判运行,运行的结果会判定为正确或错误两种并及时通知参赛队。而且有趣的是每队在正确完成一题后,组织者将在其位置上升起一只代表该题颜色的气球,每道题目第一支解决掉它的队还会额外获得一个FIRST PROBLEM SOLVED的气球。

 

第1关:程序三步曲

任务描述

本关任务:编写一个程序实现两个整数ab的大小比较,并完成数据读取、运算分析和输出结果三步曲。

相关知识

为了完成本关任务,你需要掌握:1.数据读取,2.运算分析,3.输出结果。

数据读取

C语言常用的读取函数是scanf,它是格式输入函数,被声明在头文件stdio.h里,因此在使用scanf函数时要加上#include <stdio.h>。 函数原型:

1 int scanf(const char * restrict format,...);
2 // format表示输入指令格式

例如读取两个整数 和 

1 int a, b;
2 scanf("%d %d", &a, &b);

C++程序设计语言常用的读取函数是cin,使用提取运算符 >> ,读取数据格式多样,使用cin时要加上#include <iostream.h>(新版本编译器为#include <iostream>)。 例如:

1 int a;
2 float b;
3 char c;
4 cin>>a>>b>>c;

在算法竞赛中,程序I/O的时间开销是非常关键的,scanf因其格式化输入与cin相比只需要很小的时间开销,更为常用。

运算分析

运算分析是算法竞赛中的重中之重,它决定了该问题选取什么算法,做出什么改进,最终得出什么结论。 计算机程序语言中变量的比较实际上是ASCII码的比较,例如a=0b=1,他们的ASCII码值分别是4849,因此0<1符合ASCII值48<49

输出结果

printf函数是格式化输出函数,调用格式为: printf("<格式化字符串>", <参量表>),与scanf一样被定义在被声明在头文件stdio.h里。

函数原型:

1 extern int printf(const char *format,...);

另外,cout函数是C++编程语言互换流中的标准输出流,需要iostream支持。 在算法竞赛中,printf格式化输出函数对程序结果的指定输出来说是非常方便实用的。

编程要求

本关的编程任务是补全右侧代码片段mainBeginEnd中间的代码,具体要求如下:

  • mian中,完成两个整数ab的读取,并且比较他们的大小,最后输出这两个整数的升序序列。

测试说明

平台将自动编译补全后的代码,并生成若干组测试数据,接着根据程序的输出判断程序是否正确。

以下是平台的测试样例:

测试输入:2 1

预期输出:1 2

输入格式:两个整数 ab

输出格式:输出两个整数的升序,中间空格隔开,末尾换行。


Tips:竞赛中采用黑盒测试的方式对输出结果进行验证,因此输出结果的格式是异常严格的。

 

 

 1 //
 2 //  main.cpp
 3 //  step1
 4 //
 5 //  Created by ljpc on 2018/6/20.
 6 //  Copyright © 2018年 ljpc. All rights reserved.
 7 //
 8 
 9 #include <iostream>
10 
11 int main(int argc, const char * argv[]) {
12     
13     // 请在这里补充代码,完成本关任务
14     /********** Begin *********/
15     int a,b;
16     scanf("%d %d",&a,&b);
17     if(a>b) printf("%d %d",b,a);
18     else printf("%d %d",a,b);
19 
20     /********** End **********/
21     
22     return 0;
23 }
点击查看代码

 

第2关:牛刀小试

任务描述

本关任务:编写一个程序实现三个整数abc的大小比较,并完成数据读取、运算分析和输出结果三步曲。

相关知识

为了完成本关任务,你需要掌握:1.三个数比较。

三个数比较

三个数abc的比较方法比两个数的比较方法稍微复杂一点,但仍然是简单的,例如以下两种思路:

  • 三个数共3x2x1六种排列,暴力判断a<b && b<cc<b && b<a六种排列。
  • 先判断一个最小值a<b && a<c,若满足再判断b<c还是c<b

编程要求

本关的编程任务是补全右侧代码片段mainBeginEnd中间的代码,具体要求如下:

  • main中,完成三个整数abc的读取,并且比较他们的大小,最后输出这三个整数的升序序列。

测试说明

平台将自动编译补全后的代码,并生成若干组测试数据,接着根据程序的输出判断程序是否正确。

以下是平台的测试样例:

测试输入:3 2 1

预期输出:1 2 3

输入格式:三个整数abc

输出格式:输出三个整数的升序,中间空格隔开,末尾换行。


开始你的任务吧,祝你成功!

 

 

 1 //
 2 //  main.cpp
 3 //  step2
 4 //
 5 //  Created by ljpc on 2018/6/20.
 6 //  Copyright © 2018年 ljpc. All rights reserved.
 7 //
 8 
 9 #include <iostream>
10 
11 int main(int argc, const char * argv[]) {
12     
13     // 请在这里补充代码,完成本关任务
14     /********** Begin *********/
15     int a,b,c;
16     scanf("%d %d %d",&a,&b,&c);
17     if(a>b&&b>c) printf("%d %d %d",c,b,a); 
18     if(a>c&&c>b) printf("%d %d %d",b,c,a); 
19     if(b>c&&c>a) printf("%d %d %d",a,c,b); 
20     if(b>a&&a>c) printf("%d %d %d",c,a,b); 
21     if(c>b&&b>a) printf("%d %d %d",a,b,c); 
22     if(c>a&&a>b) printf("%d %d %d",b,a,c); 
23     /********** End **********/
24     
25     return 0;
26 }
点击查看代码

 

 

第3关:崭露头角

任务描述

本关任务:编写一个程序实现n个整数的大小比较,输出升序序列,并完成数据读取、运算分析和输出结果三步曲。

相关知识

为了完成本关任务,你需要掌握:1.数列排序。

数列排序

在算法竞赛中,往往根据数据的规模而设计相应的算法来求解问题。前两个关卡的数据规模非常小,少量的代码就能完成程序的实现。但本关卡的数据规模为n,将有n!种排列,难以枚举。因此需要设计针对n个整数的排序算法,例如冒泡排序。

冒泡排序重复地遍历待排序的数列,每次比较两个相邻元素,如果它们的顺序错误就把它们交换。重复地进行遍历直到没有再需要交换时表示数列已经排序完成。

  • 算法步骤:

    1. 比较相邻的元素:若第一个比第二个大,则交换;

    2. 遍历开始第一对到结尾最后一对,执行步骤1

    3. 重复步骤1~2,直到排序完成。

  • 可改进的冒泡排序:第一趟排序之后最后一个元素是最大的,因此下一趟遍历只需执行到倒数第二对。

编程要求

本关的编程任务是补全右侧代码片段mainBeginEnd中间的代码,具体要求如下:

  • main中,完成n个整数的读取,并且比较他们的大小,最后输出这n个整数的升序序列。

测试说明

平台将自动编译补全后的代码,并生成若干组测试数据,接着根据程序的输出判断程序是否正确。

以下是平台的测试样例:

测试输入: 10 9 8 7 6 5 4 3 2 1 0

预期输出: 0 1 2 3 4 5 6 7 8 9

输入格式:第一行整数n,第二行n个整数。

输出格式:n个整数,中间空格隔开,末尾换行。


开始你的任务吧,祝你成功!

Tips:更多的排序算法请参考实训《数据结构-十大经典排序算法》 https://www.educoder.net/shixuns/r5xsukn4/challenges

 

 

 1 //
 2 //  main.cpp
 3 //  step3
 4 //
 5 //  Created by ljpc on 2018/6/20.
 6 //  Copyright ? 2018年 ljpc. All rights reserved.
 7 //
 8 
 9 #include <iostream>
10 int a[100001];
11 int main(int argc, const char * argv[]) {
12     
13     // 请在这里补充代码,完成本关任务
14     /********** Begin *********/
15     int t,c;
16     scanf("%d",&t);
17     for(int i=1;i<=t;i++){
18         scanf("%d",&a[i]);
19     }
20     for(int i=1;i<=t;i++)
21         for(int j=1;j<=t-1;j++){
22             if(a[j]>a[j+1]){
23                 c=a[j];
24                 a[j]=a[j+1];
25                 a[j+1]=c;
26             }
27             else continue;
28         }
29     for(int i=1;i<=t;i++)
30         printf("%d ",a[i]);
31     /********** End **********/
32     return 0;
33 }
点击查看代码

 

 

 

第4关:结构体运

任务描述

本关任务:给定矩形的某一对角线坐标,编写一个程序运用结构体完成矩形中心点、面积和周长的计算。

相关知识

为了完成本关任务,你需要掌握:1.结构体,2.矩形相关概念。

结构体

C++中除了支持结构体struct之外,还支持类class,由此C++的结构体除了可以有变量(称之为成员变量)外,还可以有函数(称之为成员函数)。算法竞赛中因为时间紧张,通常使用结构体来替代类,提升编程效率,而工程中则是将结构体作为纯数据类型,仅仅包含少量的辅助成员函数。C++中类的成员变量,成员函数,构造函数都可以在C++结构体中得以实现。

例如定义一个二维坐标轴中的点结构体Point,包含两个成员变量:横坐标x和纵坐标y,以及一些成员函数和重载函数:

 1 struct Point{
 2     double x, y;
 3     Point(){x=y=0;}//  重载初始化函数
 4     Point(double x_, double y_):x(x_), y(y_){}
 5     void in(){scanf("%lf %lf", &x, &y);}// 读入数据函数
 6     void out(){printf("%.2lf %.2lf\n", x, y);}// 输出数据函数
 7     Point operator + (Point P){// 重载 + 操作
 8         Point Q;
 9         Q.x = x + P.x;
10         Q.y = y + P.y;
11         return Q;
12     }
13 };
14 Point P1; // 定义一个点 P1
15 Point P2 = Point(1, 1); // 定义一个点 P2

矩形相关概念

  • 矩形中心点:对角线的交点
  • 矩形面积:矩形长乘以宽的结果
  • 矩形周长:矩形四条边的长度和

编程要求

本关的编程任务是补全右侧代码片段areaperimetercenterBeginEnd中间的代码,具体要求如下:

  • area中,利用结构体的相关操作完成矩形面积的计算。
  • perimeter中,利用结构体的相关操作完成矩形周长的计算。
  • center中,利用结构体的相关操作完成矩形中心点的计算。

测试说明

平台将自动编译补全后的代码,并生成若干组测试数据,接着根据程序的输出判断程序是否正确。

以下是平台的测试样例:

测试输入:

0 0

2 2

预期输出:

中心点 1.00 1.00

面积 4.00 

周长 8.00

输入格式:矩形对角线上的两点在二维坐标轴的位置坐标

输出格式:输出结果保留小数点后两位,中间空格隔开,末尾换行。


开始你的任务吧,祝你成功!

 

 

  1 //
  2 //  main.cpp
  3 //  step4
  4 //
  5 //  Created by ljpc on 2018/6/20.
  6 //  Copyright © 2018年 ljpc. All rights reserved.
  7 //
  8 
  9 #include <iostream>
 10 #include <math.h>
 11 struct Point{
 12     double x, y;
 13     //  重载初始化函数
 14     Point(){x=y=0;}
 15     Point(double x_, double y_):x(x_), y(y_){}
 16     
 17     // 读入数据函数
 18     void in(){scanf("%lf %lf", &x, &y);}
 19     
 20     // 输出数据函数
 21     void out(){printf("%.2lf %.2lf\n", x, y);}
 22     
 23     // 重载 + 操作
 24     Point operator + (Point P){
 25         Point Q;
 26         Q.x = x + P.x;
 27         Q.y = y + P.y;
 28         return Q;
 29     }
 30     
 31     // 重载 - 操作
 32     Point operator - (Point P){
 33         Point Q = Point(0, 0);
 34         Q.x = x - P.x;
 35         Q.y = y - P.y;
 36         return Q;
 37     }
 38     
 39     // 重载 * 操作
 40     Point operator * (double scale){
 41         Point Q = Point(0, 0);
 42         Q.x = x * scale;
 43         Q.y = y * scale;
 44         return Q;
 45     }
 46     
 47 };
 48 
 49 // 计算面积
 50 double area(Point p1, Point p2)
 51 // 参数:矩形对角线上的两点p1(x1, y1), p2(x2, y2)
 52 // 返回:矩形面积
 53 {
 54     // 请在这里补充代码,完成本关任务
 55     /********** Begin *********/
 56     return abs((p1.x-p2.x)*(p1.y-p2.y));
 57 
 58     /********** End **********/
 59 }
 60 
 61 // 计算周长
 62 double perimeter(Point p1, Point p2)
 63 // 参数:矩形对角线上的两点p1(x1, y1), p2(x2, y2)
 64 // 返回:矩形周长
 65 {
 66     // 请在这里补充代码,完成本关任务
 67     /********** Begin *********/
 68     return (abs(p1.x-p2.x)+abs(p1.y-p2.y))*2;
 69 
 70     /********** End **********/
 71 }
 72 
 73 // 计算中心点
 74 Point center(Point p1, Point p2)
 75 // 参数:矩形对角线上的两点p1(x1, y1), p2(x2, y2)
 76 // 返回:矩形中心点
 77 {
 78     // 请在这里补充代码,完成本关任务
 79     /********** Begin *********/
 80     Point Q = Point(0,0);
 81     Q.x=(p1.x+p2.x)*0.5;
 82     Q.y=(p1.y+p2.y)*0.5;
 83     return Q;
 84     /********** End **********/
 85 }
 86 
 87 int main(int argc, const char * argv[]) {
 88     
 89     
 90     // 1.读取数据
 91     Point p1, p2;
 92     p1.in();
 93     p2.in();
 94     
 95     // 2.运算分析
 96     Point pc = center(p1, p2);
 97     double s = area(p1, p2);
 98     double c = perimeter(p1, p2);
 99     
100     // 3.输出结果
101     printf("中心点 ");
102     pc.out();
103     
104     printf("面积 %.2lf\n", s);
105     
106     printf("周长 %.2lf\n", c);
107     
108     
109     return 0;
110 }
点击查看代码

 

这篇关于头歌 | 数据结构与算法课程设计-算法与竞赛(第1章) - 入门指南的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!