jianguanthu / uoj_offline Goto Github PK
View Code? Open in Web Editor NEWOffline test system for THUOOP
Offline test system for THUOOP
模板、继承、函数多态
function
是 c++11 中提供的模板类,其可以储存、复制、调用任何接口相同的可调用目标,例如函数、成员函数、lambda 表达式等。
例如你可以通过 function<int(int,int)>f = max
来构造一个 function
,其接受两个 int
作为传入参数,并返回类型为 int
。
请编写一个 my_func
模板类来实现 function
的基本功能,即包装可调用对象。
有部分分,不同的部分分中使用不同的 main.cpp
进行评测。
第一部分,保证函数类型仅有 void(void)
,且只会使用函数构造 function
。
第二部分,保证可调用目标的传入参数不超过三个。
第三部分无额外限制。
选手还需要实现 my_func
的相关构造、赋值函数与运算符。
如在转发参数时出现了额外的移动或拷贝,会扣除一定分数。
有了STL的帮助,我们可以做出很多东西。这次让我们来做一个简单的文本编辑器TextEditor
。
重要说明:它的行为和一般的文本编辑器基本一致,如windows自带的记事本、vscode等。如果有理解上的困难,可以在这些编辑器上操作一下,来观察其功能,例如光标的移动规律,撤销、重做的模式等等。
TextEditor
的基本构成有:
文本:被编辑的对象。文本可以被加载到TextEditor
内部进行操作,也可以由TextEditor
输出。
光标:指示正在进行编辑的位置,由行号和列号确定,即(row, col)
。**为方便起见,一切编号从0开始,**同时约定:
举例如下:
abc
hello
具体来说,TextEditor
具有以下功能:
光标:
移动光标(moveCursor
):移动光标至指定位置。
选择(select
):接受两个位置beg
、end
,选中[beg,end)
区域,以便进一步编辑。
输入与输出:
输入(operator>>
):读入一行字符串,插入到光标所在位置。
输出(operator<<
):输出光标所在行。
截屏(screenShot
):将目前文本编辑器处理得到的文本输出至标准输出。用*
标出光标的位置或选中区域的位置。如:
光标在$(0,2)$处:
ab*c
hello
选中区域为$[(0,0),(1,0))$:
*abc
*
hello
编辑:
write
):写入一定内容。光标随之移动。del
):若无选中区域,则删除光标位置的一个字符,光标位置不变;若有选中区域,则删除已选中的内容,同时退出选中状态,光标置于选中区域靠近开头的位置。copy
):复制选中区域的内容至剪贴板。若无选中区域,则无任何影响。cut
):剪切选中区域的内容至剪贴板,等价于先复制再删除。若无选中区域,则无任何影响。paste
):若无选中区域,将剪贴板现有内容粘贴到光标处;若有选中区域,则替换之,即先删除再粘贴。若剪贴板为空,则无任何影响。关于历史的操作:注意,光标和文本受影响,而剪贴板不受影响。
undo
):撤销一次操作。连续的写入/删除可以被一次撤销,例如:连续输入abcde,撤销时将完全删除abcde。redo
):重做一次操作。连续的写入/删除可以被一次重做,同上。clearHistory
):清空现有的历史记录。main.cpp
将会给定。请编写TextEditor.h
,可以增加文件。将你所写的文件和makefile打包提交。
模板类、内存检测
模拟 c++ stl 中的模板类栈,实现对应的功能
template<typename T>
class Stack {
private:
T *save; // 内存池
int ed; // 末尾指针位置(内存池的下标在区间 [0, ed) 中为合法下标)
public:
Stack(int n); // 构造函数,n 表示内存池大小
~Stack(); // 析构函数,在下发代码中会检测内存是否泄漏
bool empty(); // 判断是否为空
int size(); // 栈的大小
void push(T element); // 向栈顶推入一个元素
void pop(T element); // 弹出栈顶的元素
T top(); // 返回栈顶的元素
};
下发 Stack.h,需要自行实现 Stack.cpp,通过给定的 main.cpp 和 Makefile 进行测试
在 main.cpp 中给出一个简单的自定义类 myclass ,生成 Stack <myclass>
的对象并对其测试相关函数的正确性
为防止做题人实现模板函数的特化,在实际的 main.cpp 中采用不同的类名(把 myclass 换个名字)
为检测内存泄漏情况,在 myclass 中加入静态变量指示构造和析构函数调用次数
(如果这个题太简单了可以考虑继承 Stack 类实现一个 Deque 类,但是这样可能就太难了..
输入 n, m 表示内存池大小和操作数,维护一个 myclass 类的栈,接下来 m 行表示 m 个操作,每行开头为一个 int 类型 op
op=1: 输出 true/false 表示栈是否为空
op=2: 输出栈的大小
op=3: 额外输入一个 myclass 类型变量并推入栈顶
op=4: 弹出栈顶元素,如果栈为空需要输出一条异常信息并什么都不做
op=5: 返回栈顶的元素,如果栈为空需要输出一条异常信息并什么都不做
对每种输入输出指定信息
在每次操作后,考虑输出一个类哈希值(比如 ed 和所有元素的一个值异或起来)来判断栈的当前状态有没有错,防止出现奇异的错误(如 ed 变成 -1)但没有检测到
在程序结束前,需要析构所有栈中元素,会检测内存是否泄漏
开发网站的时候,服务器处理用户传来的数据时需要有足够的鲁棒性,其中就包括对数据格式的检查。现在从网站前端传来了包含用户注册帐号时提交信息的字符串,请你完成后端检验代码,如果存在非法格式的数据,则输出报错信息;如果注册信息合法,则在屏蔽掉私密信息后输出注册信息。
用户名username:长度4 - 15,由字母或数字或下划线_构成,且首字符必须为字母
密码password:长度8-20,为字母和数字的组合,且二者必须都有。
邮箱email: 本题只考虑满足正则表达式([\w]+@[\w.]+)的邮箱为合法邮箱地址。
输入一行简单的json格式的字符串:字符串首尾为'{'、'}',内部以 "键" : "值" 的格式记录信息。键和值中不会出现 " 和 : 。不同的键值对之间使用 , 进行分隔。需要注意双引号之外可能存在多余的空格。题目保证在输入数据在json格式上不会出错。
{"username":"wrongpass", "password":"abc", "email":"[email protected]"}
{"username": "twoillegal?", "email": "test.thu.com", "password": "abc12345"}
{"password" : "abc12345", "username": "correct", "email": "[email protected]"}
用户名:保留开头三个字符,后续字符用*代替
密码:所有字符用*代替
邮箱:除了@与.外的其他字符用*代替。
根据三个字段的非法情况输出"Illegal [username],[password],[email]"
(由于后端只需要检验数据格式的合法性,因此不需要返回具体的错误原因)
对应”输入数据“部分三个样例的输出:
Illegal password
解释:密码长度过短
Illegal username,email
解释:用户名中包含除了字母和密码以外的特殊字符?,邮箱不符合题给正则表达式(不含@)
Successfully registered.
username: cor****
password: ********
email: *@*.*.***
提交一个main.cpp,完成上述要求。
STL、regex
类与对象、函数重载、运算符重载
实现一个整数矩阵类Matrix,并通过运算符重载完成矩阵的
等功能。
再附加实现求转置的函数transpose()。(求逆和求行列式啥的可能有点难?)
c++ stl库中实现了map,通过红黑树等数据结构实现了键值对应关系,但每次查询需要经过多次比较才能得到,可以基于hash table实现同样的功能,但效率更高。
为简化算法,已经给出了hash算法,需要在头文件HashFunc.h
中,完善模板类Hash和模板类HashTable的成员函数,以实现添加、删除和查询元素的基本功能。
HashClass.h
template <typename T>
class Hash
{
private:
int n;
public:
Hash(int _n) : n(_n) {}
int operator()(const T &x);
};
template <typename T1, typename T2>
class HashTable
{
private:
T2 *buckets;
bool *isFull;
int size;
Hash<T1> hash;
public:
HashTable(int);
~HashTable();
void addItem(const T1 &key, const T2 &value);
void removeItem(const T1 &key);
T2 *findByKey(const T1 &key);
};
HashFunc.h
int Hash<int>::operator()(const int &x)
{
return x % n;
}
int Hash<std::string>::operator()(const std::string &x)
{
int ret = 0;
for (char c : x)
{
ret += static_cast<int>(c);
ret %= n;
}
return ret;
}
main.cpp
#include "HashClass.h"
#include "HashFunc.h"
using namespace std;
int main()
{
int n1, n2, n3, n4, p, q, opr;
cin >> n1 >> n2 >> n3 >> n4;
HashTable<int, int> hii(n1);
HashTable<int, string> his(n2);
HashTable<string, int> hsi(n3);
HashTable<string, string> hss(n4);
int a, b;
string c, d;
cin >> p;
for (int i = 0; i < p; i++)
{
cin >> opr;
switch (opr)
{
case 1:
cin >> a >> b;
hii.addItem(a, b);
break;
case -1:
cin >> a;
hii.removeItem(a);
break;
case 2:
cin >> a >> c;
his.addItem(a, c);
break;
case -2:
cin >> a;
his.removeItem(a);
break;
case 3:
cin >> c >> a;
hsi.addItem(c, a);
break;
case -3:
cin >> c;
hsi.removeItem(c);
break;
case 4:
cin >> c >> d;
hss.addItem(c, d);
break;
case -4:
cin >> c >> d;
hss.removeItem(c);
break;
default:
break;
}
}
int *intPointer;
string *stringPointer;
cin >> q;
for (int i = 0; i < q; i++)
{
cin >> opr;
switch (opr)
{
case 1:
cin >> a;
intPointer = hii.findByKey(a);
if (intPointer == nullptr)
cout << "NULL\n";
else
cout << *intPointer << "\n";
break;
case 2:
cin >> a;
stringPointer = his.findByKey(a);
if (stringPointer == nullptr)
cout << "NULL\n";
else
cout << *stringPointer << "\n";
break;
case 3:
cin >> c;
intPointer = hsi.findByKey(c);
if (intPointer == nullptr)
cout << "NULL\n";
else
cout << *intPointer << "\n";
break;
case 4:
cin >> c;
stringPointer = hss.findByKey(c);
if (stringPointer == nullptr)
cout << "NULL\n";
else
cout << *stringPointer << "\n";
break;
default:
break;
}
}
return 0;
}
模板类,模板类成员函数的实现,模板类的特化/模板类成员函数的特化,函数类等
给定 main.cpp
,要求实现表示 3 维浮点数向量的类 Vec3
,从下列操作中选择一些有代表性或能提高完成度的支持:
==
、!=
operator bool
和 !
判断是否为 0
for
循环遍历iostream
输入输出另外可以要求考察操作对 this
const
和非 const
的区分,如下标和复合赋值操作会受到影响。
此题考察的知识点是典型的带有运算符重载的 C++ 类实现,可以展示不可变性在 C++ 中的使用、不同运算间的代码复用等。
在minecraft这款游戏中,作为主角的Steve和Alex两人遇到了挑战——挖矿。Steve身强力壮,会挖掉身边的矿石;而Alex没有合适的工具,强行破坏矿石会一无所获。
具体而言,程序随机在玩家列表中加入Alex和Steve两类玩家,需要根据对象类型来决定是否调用Player::work()
函数,来实现Game::run()
和Game::~Game()
函数。
Game.h
class Game
{
private:
std::vector<Player *> playerList;
std::vector<Ore *> oreList;
public:
Game(int num);
~Game(); //TODO
void run(); //TODO
friend bool check(Game &);
};
Ore.h
class Ore
{
private:
bool isMined, shouldBeMined;
public:
static int cntInstance;
Ore(bool tag) : isMined(false), shouldBeMined(tag) { cntInstance++; }
virtual ~Ore() { cntInstance--; };
friend class Steve;
friend class Alex;
friend bool check(Game &);
};
class CoalOre : public Ore
{
public:
CoalOre(bool tag) : Ore(tag) {}
};
Player.h
class Player
{
public:
static int cntInstance;
Player() { cntInstance++; }
virtual ~Player() { cntInstance--; };
virtual void work(Ore *) = 0;
};
class Steve : public Player
{
public:
void work(Ore *ore) override { ore->isMined = true; }
};
class Alex : public Player
{
public:
void work(Ore *ore) override { ore->isMined = true; };
};
main.cpp
Game::Game(int num)
{
srand(time(0));
for (int i = 0; i < num; i++)
{
int tmp = rand();
if (tmp & 1)
{
playerList.push_back(new Steve);
oreList.push_back(new CoalOre(true));
}
else
{
playerList.push_back(new Alex);
oreList.push_back(new CoalOre(false));
}
}
}
int Player::cntInstance = 0;
int Ore::cntInstance = 0;
bool check(Game &game)
{
for (int i = 0; i < game.oreList.size(); i++)
if (game.oreList[i]->isMined != game.oreList[i]->shouldBeMined)
return false;
return true;
}
int main()
{
int round;
std::cin >> round;
for (int i = 0; i < round; i++)
{
int n;
std::cin >> n;
Game *nowGame = new Game(n);
nowGame->run();
if (check(*nowGame))
{
delete nowGame;
if (Player::cntInstance == 0 && Ore::cntInstance == 0)
std::cout << "ok\n";
}
}
return 0;
}
虚函数(虚析构函数)、多态中向下类型转换、STL应用、析构函数
课上讲述了简单的加减法重载,但是还有很多符号可以重载,虽然在以后的编程当中没有什么用(x),但是作为一门编程设计入门课作业可以了解到更多的操作符重载的方式,并且尝试在陌生的背景下运用课内知识解决问题。今年的操作符重载作业感觉更多时间画在调试微积分运算上了,没有很好地体现操作符重载带来的编程灵活性。本题具体考察了流输出运算符,逗号运算符,逻辑判断运算符,位运算符,函数运算符,涵盖了除复杂的空间申请释放与成员访问运算符外的各类型的运算符。
小陈暑假实习遇到了一个难缠的店长,店长为了将新到的货物进行排序,写了一段代码,但出现了多达12处的语法错误,自诩熟练掌握C++的店长不愿意修改他的代码,请你完善Rack类,使得程序可以正常编译运行。店长编写的主函数main.cpp如下:
#include "Rack.hpp"
#include <iostream>
int main(){
Rack A,B,C,D;
int n,temp;
for(int i=0;i<n;i++){//初始给A和B货架添加货物
cin>>temp;
if(A<B) A+=temp;//如果A上的货物数量比B少就给A上添加货物
else B+=temp;
}
C=(A,2023,B,2023);//C货架上按照 {A上的货物,标号为2023的货物,B上的货物,标号为2023的货物} 的顺序排列
cout<<C;//将C货架上的元素按照加入的顺序打印出来,然后让店员摆放
D=A&&B;//D由A和B**有的元素组成
cout<<D;
D=~D;//将C货架上的货物倒序
D--;//将D货架上最后一个货物卸掉(直接删掉)
--D;//将D货架上最后一个货物卸掉(直接删掉)
cout<<D;
cout<<D[2023]<<endl;//打印出D货架上标号号为2023的货物的个数
return 0;
}
小陈同学在Rack.hpp里的已经编写了Rack类的基本框架,请你补充一些函数使得程序可以正常运行,提示:使用操作符重载。
By 刘泓尊 [email protected]
数字微流控芯片(Digital Microfluidic BioChips)利用液滴在疏水化表面的电润湿现象,操作液滴进行移动(Move),合并(Merge)等操作。小明的实验室正在进行相关的研究,但是苦于没有一个管理系统。
因此,小明委托你开发一个基础的液滴管理系统,负责管理芯片上液滴的产生、移动等操作。
x坐标(int
),y坐标(int
),大小(用半径表示,int
),颜色(string
, 唯一标识)
1.液滴的产生,通过重载DropCollection
的>>
实现,输入信息分别为:颜色-x-y-半径
,如:
yellow-1-2-10
2.液滴的移动:如:
Move yellow 1 3
3.通过液滴颜色来查询两个液滴的位置。按照升序(优先级:x坐标>y坐标>半径) 输出两个液滴信息,如
Ask yellow red
4.液滴的合并: 合并后,原先的两个液滴消失,产生一个新液滴。其颜色是前者的颜色,位置是两个液滴的位置中点,半径是两液滴半径的和。
Merge yellow red
5.液滴的减量,液滴的半径减1,若半径减至1则不再减少(即至少为1)
Reduce yellow
6.液滴按位置升序排序, (优先级:x坐标>y坐标>半径)
7.所有液滴信息的输出
你需要实现:DropCollection.h
, Drop.h
及其对应的.cpp
文件 其中,所有的液滴由DropCollection
管理。
#include "Drop.h"
#include "DropCollection.h"
#include <iostream>
#include <string>
using namespace std;
inline int str2int(const string& str){
return atoi(str.data());
}
int main(){
int n;
cin >> n;
DropCollection dc;
for(int i = 0; i < n; i++){
cin >> dc; //add a new drop
}
int m;
cin >> m;
for(int i = 0; i < m; i++){
string opt, colorA, colorB, locx, locy;
cin >> opt;
if (opt == "Move") { //Move a drop to (x, y)
cin >> colorA >> locx >> locy;
dc[colorA].moveTo(str2int(locx), str2int(locy));
} else if (opt == "Merge") { //Merge to different drops
cin >> colorA >> colorB;
dc.merge(colorA, colorB);
} else if (opt == "Ask") { //Ask for a drop's location
cin >> colorA >> colorB;
if(dc[colorA] < dc[colorB]){
cout << dc[colorA] << dc[colorB] << endl;
} else {
cout << dc[colorB] << dc[colorA] << endl;
}
} else if (opt == "Reduce") { // Reduce the radius of a drop
cin >> colorA;
dc[colorA]--;
} else {
continue;
}
}
dc.sortDrops(); //Sort drops by x and y
cout << dc; //print all drops
return 0;
}
3
red-1-1-10
yellow-2-1-10
green-1-3-30
6
Ask red green
Move yellow 3 3
Merge red yellow
Move red 3 4
Reduce red
Ask red green
red-1-1-10
green-1-3-30
green-1-3-30
red-3-4-19
green-1-3-30
red-3-4-19
运算符重载([], --, <<, >>)
类的基本知识
类似于stl_function.h里的 unary_opr, 但是没有模板
提供main.cpp
, 要求实现Operator.h
// main.cpp
#include <iostream>
#include "Operator.h"
int n;
int v[10];
void apply(int *a, int n, UnaryOpr* opr) {
for (int i = 0; i < n; ++i)
opr->work(a[i]);
}
int find_if(int *a, int n, BoolUnaryOpr* opr) {
for (int i = 0; i < n; ++i)
if (opr->work(a[i])) return i;
return -1;
}
int main() {
std::cin >> n;
for (int i = 0; i < n; ++i)
std::cin >> v[i];
UnaryOpr* a[3] = {new PlusOpr(2), new MultOpr(3), new NegateOpr()};
BoolUnaryOpr* b[2] = {new LessOpr(8), new GreaterOpr(3)};
for (int i = 0; i < 3; ++i) {
apply(v, n, a[i]);
for (int j = 0; j < n; ++j)
std::cout << v[j] << " ";
std::cout << std::endl;
delete a[i];
}
for (int i = 0; i < 2; ++i) {
std::cout << find_if(v, n, b[i]) << std::endl;
delete b[i];
}
return 0;
}
5
1 -2 3 -4 5
3 0 5 -2 7
~PlusOpr()
9 0 15 -6 21
~MultOpr()
-9 0 -15 6 -21
~NegateOpr()
0
~LessOpr()
3
~GreaterOpr()
多态、虚析构函数
很多同学会在申请内存之后忘了释放,为了解决这个问题,C++ 11中实现了一些智能指针类
auto_ptr, shared_ptr, unique_ptr
可以通过#include <memory>来使用
详细解析可以见 https://blog.csdn.net/zy19940906/article/details/50470087
这次作业希望同学们自己实现一个简单的智能指针,要求能够实现自动析构一段没有被指向的内存
main.cpp
#include <iostream>
#include "shareptr.h"
#include "Node.h"
using namespace std;
void test(){
SharePtr<Node> a(new Node(2));
{
SharePtr<Node> b = a;
SharePtr<Node> c(new Node(3));
cout << *b << endl;
b = c;
cout << *c << endl;
}
if(Node::num_createfunc + Node::num_createfunc_default + Node::num_copyfunc + Node::num_movefunc != Node:: num_delfunc + 1){
cout << "No" << endl;
}
cout << *a << endl;
}
int main(){
test();
Node::outputResult();
return 0;
}
shareptr.h
#pragma once
template <typename T>
class SharePtr{
private:
int *_n;
T *_ptr;
public:
SharePtr(const SharePtr & t) {
// Todo
}
SharePtr(T * t) : _ptr(t){
// Todo
}
SharePtr<T>&operator=(const SharePtr& t){
// Todo
}
T& operator*() {
// Todo
}
T*operator->(){
// Todo
}
~SharePtr(){
// Todo
}
};
以下两段代码来自第三次作业 Vector类的简易实现与封装 改变而成
node.h
#pragma once
#include <iostream>
void test();
class Node{
private:
static long long int num_createfunc_default, num_createfunc, num_copyfunc, num_movefunc, num_copyassign, num_moveassign, num_delfunc;
int val;
public:
Node(int v);
Node();
~Node();
Node(const Node &y);
Node(Node &&y);
Node& operator=(const Node &y);
Node& operator=(Node &&y);
bool operator!=(const Node &y);
friend std::istream& operator>>(std::istream& in, Node& x);
friend std::ostream& operator<<(std::ostream& out, const Node& x);
static void outputResult();
friend void test();
};
node.cpp
#include "Node.h"
long long int Node::num_createfunc = 0, Node::num_copyfunc = 0, Node::num_movefunc = 0;
long long int Node::num_copyassign = 0, Node::num_moveassign = 0, Node::num_delfunc = 0;
long long int Node::num_createfunc_default = 0;
Node::Node(int v): val(v) {
num_createfunc++;
}
Node::Node(){
num_createfunc_default++;
}
Node::~Node() {
num_delfunc++;
}
Node::Node(const Node &y): val(y.val) {
num_copyfunc++;
}
Node::Node(Node &&y): val(y.val) {
y.val = 0;
num_movefunc++;
}
Node& Node::operator=(const Node &y) {
val = y.val;
num_copyassign++;
return *this;
}
Node& Node::operator=(Node &&y) {
val = y.val;
y.val = 0;
num_moveassign++;
return *this;
}
bool Node::operator!=(const Node & y){
return val != y.val;
}
void Node::outputResult() {
std::cout << Node::num_createfunc_default << " " << Node::num_createfunc << " " << Node::num_copyfunc << " " << Node::num_movefunc << " " << Node::num_copyassign << " " << Node::num_moveassign << " " << Node::num_delfunc << std::endl;
if (Node::num_createfunc + Node::num_createfunc_default + Node::num_copyfunc + Node::num_movefunc == Node:: num_delfunc){
std::cout << "YES" << std::endl;
}
else{
std::cout << "NO" << std::endl;
}
}
std::istream& operator>>(std::istream& in, Node& x){
in >> x.val;
return in;
}
std::ostream& operator<<(std::ostream& out, const Node& x){
out << x.val;
return out;
}
模板类、智能指针
实现类模板Display
,使得继承它的容器类可以通过operator<<
和operator>>
进行IO操作。operator>>
规定为向容器末尾添加内容。
实现类模板MathExt
,使得继承它的容器类有min
、max
、sum
等成员函数,返回相应的最大值、最小值、所有元素之和。
保证容器类T有以下接口:T::begin()
,T::end()
,T::cbegin()
,T::cend()
,T::size()
,T::value_type
,T::push_back(const T::value_type &)
。
使用CRTP可以方便地拓展类的功能。
你需要编写一个模板类Display
,使得任意继承了Display
类的容器类T
,都可以通过operator<<
和operator>>
进行输入输出。operator<<
将T
中的所有元素逐个输出,每个元素之间用一个空格分隔。operator>>
每次读取一行(如果是空行,则重新读取一行),对这一行通过T
中元素的operator>>
进行读取,并将每次读取到的元素添加到T
末尾。保证T
中的元素(即T::value_type
)正确重载了operator<<
和operator>>
。
你还需要编写一个模板类MathExt
,使得任意继承了MathExt
类的容器类T
,拥有成员函数max()
、min()
、sum()
和doubled()
。其中max()
、min()
和sum()
的返回类型均为T::value_type
,分别返回T
中最大元素值、最小元素值、所有元素之和(如果最大/最小元素不唯一,任意返回一个元素)。double()
使T
中的所有元素都*2,返回T
的引用。保证T
中的元素重载了operator<
、operator>
、operator+
、operator*(T::value_type,int)
。
main.cpp和point.h已写好,你不能修改;你需要编写mathExt.h和display.h(以及相应的cpp文件)以完成上述功能
main.cpp:
#include <iostream>
#include <string>
#include <list>
#include "display.h"
#include "mathExt.h"
#include "point.h"
using namespace std;
#define MAXSIZE 1000
template<typename T>
class MyArray :public Display<MyArray<T>>, public MathExt<MyArray<T>>
{
T data_[MAXSIZE];
int n = 0;
public:
using value_type = T;
int size() const { return n; }
T* begin() { return data_; }
T* end() { return data_ + n; }
const T* cbegin() const { return data_; }
const T* cend() const { return data_ + n; }
void push_back(const T& x) { data_[n++] = x; }
};
template<typename T>
class MyList :public list<T>, public Display<MyList<T>>, public MathExt<MyList<T>>
{
public:
using list<T>::list;
};
template<typename T>
void test(int m)
{
T testObj;
cin >> testObj;
while (m--)
{
string command;
cin >> command;
if (command == "cout")
cout << testObj << endl;
if (command == "cin")
cin >> testObj;
else if (command == "min")
cout << testObj.min() << endl;
else if (command == "max")
cout << testObj.max() << endl;
else if (command == "sum")
cout << testObj.sum() << endl;
else if (command == "double")
cout << testObj.doubled() << endl;
}
}
int main()
{
int n, m;
cin >> n >> m;
if (n == 1) test<MyList<int>>(m);
if (n == 2) test<MyArray<point>>(m);
return 0;
}
point.h
#pragma once
#include <cstdio>
#include <iostream>
#include <string>
using namespace std;
struct point {
int x = 0, y = 0;
point() {}
point(int x_, int y_) :x(x_), y(y_) {}
int dis() { return x * x + y * y; }
};
bool operator<(point l, point r) { return l.dis() < r.dis(); }
bool operator>(point l, point r) { return l.dis() > r.dis(); }
point operator+(point l, point r) { return point( l.x + r.x,l.y + r.y ); }
point operator*(point l, int t) { return point( l.x*t, l.y*t ); }
istream& operator>> (istream& in, point& p) {
string s; int x, y;
in >> s;
sscanf(s.c_str(), "(%d,%d)", &x, &y);
p.x = x, p.y = y;
return in;
}
ostream& operator<< (ostream& out, const point& p) {
out << "(" << p.x << "," << p.y << ")";
return out;
}
模板、继承、多态、虚函数重载、函数指针
装饰器模式是一种设计模式,可以在不定义新的类的情况下扩展对象的功能。
上学期初有一款爆火的游戏叫《人生重开模拟器》,现在你要实现这款游戏的简化版。
在简化版游戏中,每个人会有 财富、快乐 两种属性。
随着年龄增长,每一年都会遇到某个事件,例如:
宫崎英矮发布了售价 x 的新游戏:财富减少 x,快乐增加 x
上司宣布执行 996 工作制:快乐减半,财富增加等同于快乐减少量的两倍
等等等等
经过你的观察,这些事件分为两种(设事件发生前财富为
Spend_wealth(f,g)
:财富减少
Spend_joy(f,g)
:财富增加
其中 int(int)
的函数。
你至少需要实现 Human
,After_spending_wealth
,After_spending_joy
三个类,其中后两个类继承自 Human
。
main.cpp
中实现了 Spend_wealth(f,g)
和 Spend_joy(f,g)
的功能。
例如对于一个 Human*
类的实例 x
,Spend_wealth(f,g)
表示为 x=new After_spending_wealth(x,f,g)
Human
中还需实现一个函数 life_review
,以输出目前经历过的所有事件,形如:在 i 年获得了 x 点财富,失去了 y 点快乐
。
(利用装饰器模式来实现对类中变量和成员函数的修改)
(因为刚刚一直上不去 github 所以提交超时了)
SHRDLU是由MIT的Terry Winograd在1970年开发的一个以“积木世界”模拟为背景的自然语言理解程序。程序构建了一个“积木世界”,用户可以通过英语来控制“机器人”与积木进行命名、移动、查询等互动。本作业不会考察你的程序对英语文本的理解,而是让你实现一个对“积木世界”的模拟(我们对原本的“积木世界”有所改编,以适应作业需求)。
积木的种类包括:长方体(box)、圆柱体(column)、四棱锥体(pyramid)。
输入包含N+1行:第一行为指令数N,随后每行为一个指令。
输入的指令包括以下几种:
构建积木(1):输入包括积木种类(B/C/P)、长宽高(均为不大于100的正整数,保证圆柱长宽相同)、名称。构造一个对应积木。输出“YES. THE (BOX/COLUMN/PYRAMID) NAMED XXX.\n”
放置积木(2):输入包括积木名称、目的(x,y)坐标。将(未放置的)对应积木放置到底面中心为(x,y)的位置,且其底面z坐标为此矩形范围内最高的积木(若为平面)顶部(你可以理解为这个世界有重力);若放置成功,输出“OK.\n”。若不可放置该积木,则输出“I CAN'T.\n”。
放置积木时,只要底面范围内有棱锥,就不可放置(即所有棱锥必须在顶部);否则底面范围内最高的积木顶部为底面Z坐标。(提示,棱锥的get_h()可以返回一个足够高的高度)“底面相交”指底面的公共面积大于0。
移除积木(3):输入包括积木名称。将(已放置的)对应积木移除(需要先移除高于该积木且底面有交集的所有积木,这些移除不需要提示信息);若移除成功,输出”OK.\n”。若该积木未被放置则输出“I CAN'T.\n”。
查询坐标(4):输入包括(x,y)坐标。输出对应位置俯视看到的积木”THE (BOX/COLUMN/PYRAMID) NAMED XXX.\n”;若没有积木则输出“NO.\n”。若该坐标恰为某积木的边界,不算看到该积木。
查询积木位置(5):输入包括积木名称。输出对应积木重心的(x,y,z)坐标;若其未被放置,则输出“NO.\n”。
销毁积木(0): 输入包括积木名称。将对应积木销毁。由指令销毁积木时,必须保证积木未被放置,否则输出"I CAN'T\n"。若成功销毁,输出”GOODBYE.\n”
对输入积木名称的(除构建积木外的)指令:成功选择时输出”THE (BOX/COLUMN/PYRAMID) NAMED XXX. ”不存在对应名称积木,则输出”I DON'T UNDERSTAND WHICH BLOCK YOU MEAN. \n“并不进行任何操作。
在你的程序结束时,应当销毁所有尚未销毁的积木,顺序与构建的相反。此时仍需要输出提示信息(仅有”GOODBYE.\n”)。
我们将给定Makefile、main.cpp、block.h/cpp、world.h,你不应该改动这些文件。
你的任务是在实现block类的基础上继承box、column、pyramid类;并完成world类的函数定义。
一个简单的样例:
INPUT
10
1 B 10 10 5 BEN
2 BEN 0 0
5 TIM
1 P 6 6 4 PETER
2 PETER 1 3
1 C 5 5 5 CLANCY
4 -2 -2
3 CLANCY
0 CLANCY
5 BEN
OUTPUT
YES. THE BOX NAMED BEN.
THE BOX NAMED BEN. OK.
I DON'T UNDERSTAND WHICH BLOCK YOU MEAN.
YES. THE PYRAMID NAMED PETER.
THE PYRAMID NAMED PETER. OK.
YES. THE COLUMN NAMED CLANCY.
THE BOX NAMED BEN.
THE COLUMN NAMED CLANCY. I CAN’T.
THE COLUMN NAMED CLANCY. GOODBYE.
THE BOX NAMED BEN. (0,0,2.5).
GOODBYE.
GOODBYE.
数据范围:
指令数不大于1000
积木数不大于100 且每个积木长宽高不大于100
涉及的所有xyz坐标为绝对值不大于1000的整数
保证每个积木名称为各不相同的2-20位字符串
已经达成一致的proposal请在16周周末前提交代码、数据、标程,之后助教将检验题目数据是否合适
如果有已经提出,但未与助教达成一致的,请尽快与助教联系,可能会根据题目完成度延长时间
小明想要利用类的继承来实现不同种类的宝可梦之间的对战,他已经定好了主游戏流程以及宝可梦的基类,想请你实现两个最基本的宝可梦:杰尼龟和喷火龙
控制游戏流程的代码已经在main.cpp中写好,主要包含如下环节:
type
(1时为杰尼龟,2时为喷火龙)、生命值hp
、攻击力atk
rounds
,若经过rounds轮后双方宝可梦均存活,则自动结束游戏player[0]
先开始操作,输入skill
和target
决定使用的技能和目标,再由player[1]
进行同样的操作#include "Pokemon.h"
#include <string>
#include <iostream>
using namespace std;
int main()
{
Pokemon *players[2];
for(int i = 0; i < 2; ++i)
{
int type, hp, atk;
cin >> type >> hp >> atk;
if(type == 1)
// 宝可梦的名字形如 S(1)、C(0)等,括号中数字i表示player[i]
players[i] = new Squirtle(hp, atk, "S(" + string(1, '0' + i) + ")");
if(type == 2)
players[i] = new Charizard(hp, atk, "C(" + string(1, '0' + i) + ")");
}
int rounds;
cin >> rounds;
while(rounds--)
{
int skill, target;
cin >> skill >> target;
players[0]->use_skill(skill, players[target]);
if(!players[0]->alive() || !players[1]->alive())
break;
cin >> skill >> target;
players[1]->use_skill(skill, players[target]);
if(!players[0]->alive() || !players[1]->alive())
break;
}
cout << "-----game over-----" << endl;
cout << players[0]->get_name() << " " << players[0]->get_hp() << " " << players[0]->get_atk() << endl;
cout << players[1]->get_name() << " " << players[1]->get_hp() << " " << players[1]->get_atk() << endl;
delete players[0];
delete players[1];
return 0;
}
class Pokemon
{
protected:
int tot_hp, hp, atk;
string name;
public:
Pokemon(int hp, int atk, string name);
Pokemon();
virtual void use_skill(int idx, Pokemon* target);// 对目标target使用idx号技能
virtual void hurt(int dmg, Pokemon* from);// 受到来自from的dmg点伤害时的反应
string get_name(); // 获取宝可梦名字
bool alive(); // 宝可梦是否存活
int get_hp(); // 获取生命值
int get_atk(); // 获取攻击力
~Pokemon();
};
所有宝可梦的技能都通过use_skill函数调用,如果该技能不要求目标,则调用时向target传入任意指针,不影响执行结果。
有两项技能,分别是:
0:回血(无target):恢复自身最大生命值的1/5,生命值最大不超过原来的生命值
1:喷射:对目标宝可梦造成自身攻击力的伤害
杰尼龟受到伤害时,如果当前生命值小于等于最大生命值的1/5,则受到的伤害减半(不小于1)
喷火龙有一个额外属性fire(初始为1)以及两项技能:
0:点燃(无target):fire属性+= 1,自身攻击力×2,然后自身生命值减少fire * 10
1:喷火:对目标宝可梦造成自身攻击力atk点伤害
喷火龙受到(非自己造成的)大于10的伤害时,对来源造成所受伤害dmg * 1/5的伤害。
[pokemon_name] used [Skillname] (to [target_name])
例:S(0) used Splash to C(1)
、 C(1) used Ignite
[pokemon_name] received [final_damage] damage from [from_name]
例:Charizard(1) received 100 damage from Squirtle(0)
1 120 30
2 160 40
10
0 0
0 1
1 1
0 1
1 1
1 0
样例解释:
1 120 30 // player[0]选择宝可梦1(杰尼龟) 生命值120 攻击力 30
2 160 40 // player[1]选择宝可梦2(喷火龙) 生命值160 攻击力 40
10 // 最大回合数
0 0 // 杰尼龟使用0号技能回血,后面的目标0无意义
0 1 // 喷火龙使用0号技能点燃,后面的目标1无意义
1 1 // 0号杰尼龟对1号喷火龙使用喷射
0 1 // 喷火龙继续点燃
1 1 // 继续喷射
1 0 // 1号喷火龙对0号杰尼龟使用喷火
S(0) used Regen
C(1) used Ignite
C(1) received 20 damage from C(1)
S(0) used Splash to C(1)
C(1) received 30 damage from S(0)
S(0) received 6 damage from C(1)
C(1) used Ignite
C(1) received 30 damage from C(1)
S(0) used Splash to C(1)
C(1) received 30 damage from S(0)
S(0) received 6 damage from C(1)
C(1) used Flame to S(0)
S(0) received 160 damage from C(1)
-----game over-----
S(0) -52 30
C(1) 50 160
提交一个压缩包,内包含Pokemon.cpp, Pokemon.h,以及一个makefile文件,oj会自动加入main.cpp。
OJ自动评测占100%。
运算符重载(主要是位运算和下标运算)
题目给出自定义 Bitset 类的所有成员函数定义,功能与系统 bitset 类似,其中包含一个类中类 Reference 用来支持下标系列操作(但是 stl 的实现太难了我就用了个简单的方法),做题人需要提交 Bitset.cpp 实现所有成员函数
#include <string>
using namespace std;
using ull = unsigned long long; // 使用 unsigned long long 存储数据
const int ullSize = 64; // 长度
// template<size_t size> // 感觉用不上模板类
class Bitset { // 自定义的 bitset 类
ull *save; // 存储数据的头部指针
Bitset(int size = 1) { // 为防止做题人搞事情(比如开 size 个 ull, 每次直接访问下标),给出构造函数的实现
save = new ull[(size - 1) / ullSize + 1];
}
Bitset(string s); // 从 01 串构造
~Bitset() { // 给出析构函数的实现
delete[] save;
}
Bitset(const Bitset &a); // 拷贝构造,需要实现数组深拷贝
Bitset(Bitset &&a) = delete; // 禁用移动构造
Bitset &operator=(const Bitset &a); // 拷贝赋值,需要实现深拷贝
Bitset &operator=(Bitset &&a) = delete; // 禁用移动赋值
class Reference { // 用于实现下标操作的 reference 类(比如 a[i]=x )
Bitset *pointer; // 原 bitset 指针
int pos; // 下标
Reference(Bitset *pointer = nullptr, int pos = 0): pointer(pointer), pos(pos) {} // 给出构造函数
~Reference() {} // 给出析构函数(浅拷贝不用 delete )
Reference &operator=(bool x); // 重载赋值函数用于 a[i]=x
Reference &operator=(Reference r); // 重载赋值函数用于 a[i]=b[j]
bool operator~(); // 重载取反运算用于 a[i]=~b[j]
operator bool(); // 重载 bool() 方法用于 x=a[i]
};
// 一些 bitset 中的接口,太多可以删掉几个
bool any();
bool none();
int count();
int size();
void set();
void reset();
string to_string(); // 将 bitset 转 01 串
Reference &operator[](int id); // 取下标运算
// 一些重载的位运算,实现都差不多,太多可以留下两个主要的(比如左移和右移)
Bitset operator|(Bitset a);
Bitset &operator|=(Bitset a);
Bitset operator&(Bitset a);
Bitset &operator&=(Bitset a);
Bitset operator~();
Bitset operator^(Bitset a);
Bitset &operator^=(Bitset a);
Bitset operator<<(Bitset a);
Bitset &operator<<=(Bitset a);
Bitset operator>>(Bitset a);
Bitset &operator>>=(Bitset a);
};
计划主要考察和 Reference 类相关的重载(这里的嵌套可能稍微难一点),让同学们熟悉位运算的重载方法,所以禁用了移动构造和移动赋值(因为让做题人实现也不方便考察,再套一个用于检查的 ull 类感觉太复杂了)
会下发一个 main.cpp 检查所有函数的正确性
数据范围不会太大,不考察算法复杂度,正确实现即可
输入 n 表示有 n 个 Bitset
接下来 n 行每行一个 01串 表示 Bitset 初始值(这里也可以用重载输入输出流的方式实现)
接下来输入一个数 m 表示有 m 个操作
接下来 m 行,每行先输入一个 op 表示操作类型,根据 op 的值输入接下来的操作(能检查功能就行)
对每个查询操作有一行输出
在程序最后输出 n 行,依次表示每个 Bitset 的最终状态(考察 to_string 方法)
计划下发不可修改的 main.cpp 与 Makefile
类继承、虚函数与多态、STL容器
小明和李华很喜欢玩精灵宝可梦(Pokemon),他们在学习了类继承、虚函数与多态、STL相关知识后,希望能自己模拟出一些简单的宝可梦对战情景。宝可梦对战(本题中仅说明1v1单打对战)规则的简要描述如下:
1.双方各派出一只宝可梦,每个宝可梦都有自己的HP值(初始为满),每回合结束后,若一方HP值为0,则判定该方被击败,对战结束。
2.每只宝可梦均有自己的属性(type)
和技能(move)
(技能也有属性),出于简化考虑,本题仅考虑攻击技能(即:没有变化技能),若攻击技能的属性克制对方宝可梦的属性,该技能伤害翻倍,若被对方属性所抵抗,则伤害减半,若被对方属性所免疫,则不造成伤害。并伴随相应输出“效果拔群!”或“收效甚微...”或“对xxx完全没有效果...”(详细参见示例)。属性相克表已给出,你需要考虑如何使用合适的STL容器来在战斗中判定属性之间的关系。(从左到右,即从普通系到钢系,我们依次用整数0~16来表示这17种属性)
3.每只宝可梦均可携带道具(item)
,出于简化考虑,道具仅分为回复道具、攻击道具。回复道具可以在每回合结束后给宝可梦回复HP,攻击道具可以增加宝可梦的技能伤害(在使用技能时)。这两种道具均有可能是消耗型的,即仅可使用一次,消耗后你应当将道具立刻析构,之后将无法使用。题目已给出道具基类item,你需要补充出回复道具和攻击道具的定义。
(其他细节参见代码注释和样例解释)
name
,属性type
,初始体力值HP
,技能数量n
。item_name
,类型代号s1
(0表示回复道具,1表示攻击道具),类型代号s2
(0表示消耗道具,1表示非消耗道具)回复比例/提高伤害比率rate
(double型)。move_name
,技能伤害值harm
,技能属性type
。m1 m2
,中间用空格隔开。皮卡丘 4 400 2
生命宝珠 1 1 0.3
十万伏特 90 4
铁尾 90 16
水箭龟 2 540 4
吃剩的东西 0 1 0.0625
水炮 110 2
冰冻光束 90 5
加农光炮 80 16
地震 100 8
6
1 1
0 2
1 0
0 3
0 2
0 3
小明派出了皮卡丘!
李华派出了水箭龟!皮卡丘使用了铁尾,
收效甚微...
水箭龟使用了冰冻光束,
水箭龟用吃剩的东西回复了HP,
皮卡丘使用了十万伏特,
效果拔群!
水箭龟使用了加农光炮,
收效甚微...
水箭龟用吃剩的东西回复了HP,
皮卡丘使用了铁尾,
收效甚微...
水箭龟使用了水炮,
水箭龟用吃剩的东西回复了HP,
皮卡丘使用了十万伏特,
效果拔群!
水箭龟使用了地震,
效果拔群!
皮卡丘倒下了。李华战胜了小明!
第一回合,皮卡丘使用铁尾,由于水抵抗钢,故伤害减半,水箭龟使用冰冻光束,冰对电无克制/抵抗/免疫关系,回合结束后水箭龟使用吃剩的东西回复体力。(伤害计算公式为,实际伤害=技能伤害属性相克倍率(1+提高伤害比例)(不携带道具时提高伤害比例为0,如样例中皮卡丘伤害提升比例为0.3,水箭龟为0),结果向下取整。HP回复公式为:回复量=最大HP*回复比例,向下取整,如样例中水箭龟回复比例为0.0625,皮卡丘为0)
第二回合,皮卡丘使用十万伏特,由于电克制水,故伤害翻倍,水箭龟使用加农光炮,由于水抵抗钢,故伤害减半,回合结束后水箭龟使用吃剩的东西回复体力。
第三回合,皮卡丘使用铁尾,皮卡丘使用铁尾,由于水抵抗钢,故伤害减半,水箭龟使用水,水对电无克制/抵抗/免疫关系,回合结束后水箭龟使用吃剩的东西回复体力。
第四回合,皮卡丘使用十万伏特,由于电克制水,故伤害翻倍,水箭龟使用地震,由于地克制电,故伤害翻倍,回合结束后皮卡丘倒下,战斗结束。
你应该提交打包提交除要求中不能修改的文件,包含Healitem.h和Attackitem.h,Move.h,Effect.h。 我们会将main.cpp,Item.h复制进你上传的文件中编译并运行。
OJ评分占100%
字符串处理、正则表达式,(可选)一些运算符重载
判断输入的字符串是否符合 json 格式,若是则将其格式化后输出,否则输出"format error"
定义一个 json 对象为一个特殊的数组或字典,若为数组则其中所有元素可能为一个字符串或 json 对象,字符串只能包含小写字母,两端需要有双引号,所有元素由逗号分隔,最后一个元素后不能有逗号;若为字典则其中所有元素为 key-value 对,其中 key 必须为一个字符串,value 可能是一个字符串或 json 对象,元素和连接符(逗号,冒号,括号)之间可以有任意个空格,但字符串中不能有空格。
你需要检查输入的字符串是否为一个 json 对象,如果是则将其格式化输出,每级缩进为 4
举例:输入为 [{"name": "alice", "address": {"country": "china"}}, {"name": "bob", "address": {"country": "america"}}]
输出为
[
{
"name": "alice",
"address": {
"country": "china"
}
},
{
"name": "bob",
"address": {
"country": "america"
}
}
]
main.cpp:
#include <iostream>
#include "Json"
using namespace std;
int main()
{
string s;
getline(cin, s);
Json json;
if(!json.loads(s)) {
cout << "format error" << endl;
return 0;
}
cout << json << endl;
return 0;
}
数据保证输入字符串只有一行,只包含小写字母、逗号、冒号、方括号、花括号、双引号中的字符
感觉这样并不难实现,如果要加难度的话有一些可能的方案:
一行字符串输入,表示待解析的字符串
如果解析失败输出 "format error",否则输出格式化后的 json(这个格式化要求在最终题面还会进一步明确)
在进入大学后,微积分这门数学课让很多人头疼,但其中与整式相关的运算已经被研究得很透彻,很容易在计算机上实现。
为简化问题,需要实现单项式类Monomial
,重载流运算符、四则运算符、以及实现定积分、求导、代入求值操作
Monomial.h
#include <iostream>
class Monomial
{
private:
int coe; //系数
int deg; //次数
public:
Monomial();
Monomial(int _c, int _d);
Monomial operator+(const Monomial &x) const;
Monomial operator-(const Monomial &x) const;
Monomial operator*(const Monomial &x) const;
Monomial operator/(const Monomial &x) const;
int definite_integral(const int a, const int b) const;
Monomial derive() const;
int get_val(int x) const;
//TODO
// friend std::istream& operator>>(std::istream &in, Monomial &x);
// friend std::ostream& operator<<(std::ostream &out, const Monomial &x);
};
main.cpp
#include <iostream>
#include "Monomial.h"
using namespace std;
int main()
{
int n; //单项式个数
int m; //操作个数
for (int i = 0; i < n; i++)
{
Monomial x, y;
cin >> x;//输入格式类似于"3x^5","99999997x^100"
for (int j = 0; j < m; j++)
{
int opr, a, b;
cin >> opr;
switch (opr)
{
case 1:
cin >> y;
x = x + y;
cout << x << "\n";
break;
case 2:
cin >> y;
x = x - y;
cout << x << "\n";
break;
case 3:
cin >> y;
x = x * y;
cout << x << "\n";
break;
case 4:
cin >> y;
x = x / y;
cout << x << "\n";
break;
case 5:
cin >> a >> b;
cout << x.definite_integral(a, b) << "\n";
break;
case 6:
cout << x.derive() << "\n";//输出格式也类似于"3x^5","99999997x^100"
break;
default:
break;
}
}
int par;
cout << x.get_val(par) << endl;
}
return 0;
}
运算符重载、友元函数
虚函数
十滴水是一个经典的益智游戏。如果你没玩过,可以简单看看它的规则:
游戏的地图是正方形的棋盘,每个格子里可能会有不同大小的水滴(把最小的记为1,大一些的记为2,最大的记为3),也可能没有,用空格表示。
例如,一个$5\times 5$的游戏地图看起来可能是这样的:
1 2 1 3
3 3 1 2 2
1
1 1 3 2
2 2
你拥有“十滴水”,这意味着每局游戏你可以做10次操作。每次操作都是选择地图上的一个水滴并让它变大一级,如果已经是最大的水滴,它将会爆开,原来的位置变空,同时向上下左右各溅射出一滴水,使碰到的第一个水滴变大一级。这可能会触发连锁反应,造成意想不到的局面。例如,上面的地图中,如果让第2行第2列的水滴变大,最终的地图会是这样的:
2 3 1 3
3 2 2
1
2 2 3 2
2 2
为了让这个游戏更有意思一些,我们引入一些新的元素:
游戏类Splash
和地图上元素的抽象基类Object
已经写好,你需要继承Object
类,实现Water
、Empty
、Barrier
、Toxic
四个派生类,完善这个游戏。
我们来尝试模拟一个图形界面:在一个窗口(window)内,包含若干控件(widget),例如按钮(button)、文本框等等。为方便定位,同一窗口内的每一个控件都有一个独一无二的名字,因此我们可以这样定义Widget基类:
class Widget {
string _name;
public:
Widget(string name) :_name(name) {}
string getName() const { return _name; }
virtual ~Widget() {}
};
定义好了Widget基类,我们就可以定义Window类了。一个窗口包含若干个控件,可以用list<shared_ptr<Widget>>
保存;我们还希望能够通过控件的名字获取指向控件的指针和引用,Window类有getPointerByName
和getElementByName
两个成员函数,通过一个name字符串获取对应的widget;最后,Window类还可以动态添加控件,通过addElement
方法,可以将widget添加到Window中。
class Window {
list<shared_ptr<Widget>> Widgets;
public:
// 返回一个指向名称为name的控件的指针
shared_ptr<Widget> getPointerByName(string name);
// 返回一个指向名称为name的控件的引用
Widget& getElementByName(string name);
// 将控件w添加到窗口中。如果w的名字已经存在,则不添加w,返回false;否则返回true。
bool addElement(shared_ptr<Widget> w);
};
我们还希望,对于一个具体的控件,例如按钮,可以动态设置其被单击(click)后的响应,就像这样:
Button b;
b.setClickCommand([]{ cout << "Clicked!"; })
设置好后,每次运行b.click();
(按钮被单击一次),就运行一次先前设置的指令。
但是,不止按钮可以被单击,单选框、多选框等也可以被单击,因此我们将单击这一事件(event)抽象为一个基类Click
,只要继承它的类都能响应单击事件。Click
类有两个成员函数:setClickCommand
和click
。setClickCommand
接受一个void()
的可调用对象,设置单击时执行的代码(每次覆盖掉之前的设置);click()
则运行之前设置的代码。
同理,你需要实现DoubleClick
类,以实现控件被双击后的响应。该类有setDoubleClickCommand
和doubleClick
两个接口,含义同上。
接下来我们考虑具体控件的实现。为简单起见,我们只考虑按钮(button)、多选框(checkbox)、单选框(radio)三种控件。多选框和单选框在初始时都处于未选中状态。
按钮既能接受单击也能接受双击。在默认状态下,单击或双击一个按钮什么都不做。你需要实现Button
类。
多选框和单选框都只能接受单击。在默认状态下,单击一个多选框或单选框改变当前框的选中状态。你需要实现Checkbox
和Radio
类。
多选框和单选框有很多共同的地方,因此你需要实现一个Selectbox
类,Checkbox
和Radio
类从Selectbox
类中派生出来。
一个按钮可以有以下三种功能:全选、清空和提交。全选/清空可以将与按钮关联的多选框(Checkbox
类)全部选中/清空;“提交”功能将与按钮关联的单选框或多选框(Selectbox
类)的选择情况输出。
为了方便实现这三种指令,你需要分别实现三个函数对象:ClearCheckbox
、SelectAll
、Submit
。
ClearCheckbox
、SelectAll
类的构造函数接受一个std::list<shared_ptr<Checkbox>>
,Submit
类构造函数接受一个std::list<shared_ptr<Selectbox>>
,代表与按钮关联的选择框集合。目标是实现这样的代码:
auto c1 = std::make_shared<Checkbox>("c1");
auto c2 = std::make_shared<Checkbox>("c2");
auto b = std::make_shared<Button>("b");
std::list<std::shared_ptr<Checkbox>> l = { c1,c2 };
b->setClickCommand(SelectAll(l));
此后运行b->click();
就可以将Checkbox c1和c2全选。
Submit
类的输出格式是:按照关联的顺序,一个选择框一行,如果选中,输出(name) is selected;如果未选中,输出(name) is not selected
通常情况下一个组内的单选框最多只能选中一个,即,单击一个单选框时,该单选框会被选中,组内其他的单选框都会取消选中。为实现这一功能,你需要编写一个函数SetGroup
,该函数声明如下:void SetGroup(std::list<std::shared_ptr<Radio>>);
,即将list内的单选框设为一个组。
最后,你需要实现撤销功能,每次单击单选框/多选框、全选、清空都会改变框内的选项。你需要编写undo
函数实现撤销。bool undo();
如果成功撤销返回true;如果已经是第一个操作无法再撤销则返回false。
(上面列举的每个操作都是一次撤销,即使没有真正改变选项)
为了测试以上功能,main.cpp已经写好,你不能更改;你需要编写其他.h、.cpp文件以实现上述功能
main.cpp
#include <iostream>
#include <list>
#include <functional>
#include <memory>
#include <algorithm>
#include "window.h"
#include "widget.h"
#include "undo.h"
#include "command.h"
#include "event.h"
using namespace std;
template <typename T>
list<shared_ptr<T>> getLinkedObjects(Window& win) {
int n;
cin >> n;
list<shared_ptr<T>> l;
while (n--) {
string s;
cin >> s;
l.push_back(dynamic_pointer_cast<T>(win.getPointerByName(s)));
}
return l;
}
int main() {
Window win;
int n;
cin >> n;
while (n--) {
string command;
cin >> command;
if (command == "create") {
string type, name; bool flag;
cin >> type >> name;
if (type == "button") flag = win.addElement(make_shared<Button>(name));
else if (type == "checkbox") flag = win.addElement(make_shared<Checkbox>(name));
else if (type == "radio") flag = win.addElement(make_shared<Radio>(name));
if (flag) cout << name << " has been created successfully.\n";
else cout << name << " already exists.\n";
}
else if (command == "setclick" || command == "setdoubleclick") {
string name, type;
cin >> name >> type;
std::function<void()> fun;
if (type == "clear")
fun = ClearCheckbox(getLinkedObjects<Checkbox>(win));
else if (type == "selectAll")
fun = SelectAll(getLinkedObjects<Checkbox>(win));
else if (type == "submit")
fun = Submit(getLinkedObjects<Selectbox>(win));
auto& button = dynamic_cast<Button&>(win.getElementByName(name));
if(command == "setclick")
button.setClickCommand(fun);
else
button.setDoubleClickCommand(fun);
}
else if (command == "click") {
string name;
cin >> name;
auto& clickable_widget = dynamic_cast<Click&>(win.getElementByName(name));
clickable_widget.click();
}
else if (command == "doubleclick") {
string name;
cin >> name;
auto& doubleclickable_widget = dynamic_cast<DoubleClick&>(win.getElementByName(name));
doubleclickable_widget.doubleClick();
}
else if (command == "setgroup")
SetGroup(getLinkedObjects<Radio>(win));
else if (command == "undo") {
undo();
}
}
return 0;
}
类的继承、模板
编写一个模板函数 judge
,来判断类
在本题中不考虑多重继承的情况。
judge.h
:
template<class A,class B>bool judge();
参考的 main.cpp
如下:
#include"judge.h"
#include<iostream>
struct A{};
struct B:A{};
struct C{};
int main(){
std::cout<<judge<A,B>()<<'\n';
std::cout<<judge<A,C>()<<'\n';
}
Makefile
:
all : main.cpp judge.cpp
g++ main.cpp judge.cpp -omain -O2
选手需完善文件 judge.cpp
,评测时会将 judge.h
和 main.cpp
拷贝进代码目录。
实际测试时,main.cpp
中会包含更多的类型和调用更多次 judge
函数。
(某种程度上来说,main.cpp
就是输入数据以至于很难做到设计多个测试点。所以可能这个题只有一个测试点)
(另一个想法是写一个程序根据输入内容生成相应的 main.cpp
再分别编译,但不知道 UOJ 是否支持)
大概是要实现一个分数类,可以存储一个非负的分数。
需要支持如下操作(用重载运算符的形式):流读入,流输出,加法,乘法,除法(除0时会报错,比如输出一个错误信息然后exit(0)),大小比较,加乘除要返回约分后的最简形式。
//main.cpp
#include <iostream>
#include "my_fraction.h"
int main()
{
using namespace std;
fraction A, B;
cin >> A >> B;//输入格式形如a/b,不一定最简
//输出要给出约分后的最简形式,比如1/4 + 1/4 = 1/2;0的最简形式是0/1
cout << A + B << endl;
cout << A * B << endl;
cout << A / B << endl;
if (A == B)
cout << "equal" << endl;
if (A < B)
cout << "smaller" << endl;
if (A > B)
cout << "bigger" << endl;
return 0;
}
学生自己实现my_fraction.h
以及相关文件,并提交makefile
。
运算符重载。因为只要输出
模板、运算符重载
指针是C语言的重要概念,也是很容易造成bug的功能,同学们在日常编写程序的过程中应该都遇到过内存泄露、访问非法内存等错误。
事实上,在C++的标准模板库中提供了一些智能指针类,例如你今天要模仿的unique_ptr
。它实际上是一个封装好的指针,可以帮助你管理内存,并且不需要你操心内存的释放。
具体而言,unique_ptr
指向一块内存,这块内存应当是由这个unique_ptr
来唯一管理的。一方面,不允许通过拷贝构造、拷贝赋值等方式让两个unique_ptr
指向同一块内存;另一方面,当unique_ptr
被析构时,它需要释放掉它指向的内存。可以通过移动赋值和移动构造在两个unique_ptr
间交接一块内存的管理权。
你需要编写一个my_ptr
模板类,来实现unique_ptr
的基本功能,包括上面提到的内存管理,以及通过运算符重载来实现朴素指针应当具有的功能。
抽象类 Calendar 提供 addtime(),getyear(), getmonth(), getday() 等接口。
两个子类 : 公历 和 农历 。分别具体实现以上函数。范围1970~2069年,可提供打表用的表。
实现两个子类实例之间的赋值,重载其与int的加法、减法(定义为加上或减去若干天)。
重载> < == 。实现日期之间的比较。
重载++ --。
重载<< 和 >>, 实现使用cout ,cin 的io。
小明最近正在学习国际象棋,他想用OOP的知识做一个简单的程序来进行练习,并请你助他一臂之力。
以下内容摘自国际象棋的维基百科,有更改。
国际象棋的棋盘为正方形,由32个深色和32个浅色方格交替排列组成。每边8个方格。浅色棋格称为“白格”,深色棋格称为“黑格”。开局时棋手的棋盘右下角必须为白格。
国际象棋的棋子也分为两种颜色:浅色棋子称为“白棋”,执白棋的棋手称为“白方”;深色棋子称为“黑棋”,执黑棋的棋手称为“黑方”。对弈双方各有16枚棋子,分别为一王、一后、双象(象)、双马(马)、双车(车)和八兵。开局时即全部放在棋盘上规定的棋格内,如下图。
为了方便(程序员的思维),我们记坐标为(x,y),x为行号,y为列号。上图中左上角为(1,1),右下角为(8,8)。如a2对应坐标为(7,1)。
棋局由白方先下,对弈双方轮流移动棋盘上既有的己方棋子。一般来说,一步棋只能移动一个棋子,且棋子要么移动到未被占据的棋格,要么占据对方棋子所在的棋格并将对方棋子拿出棋盘(即为“吃子”)。尽管还有特殊移动规则,但为简单起见,本题中不考虑“王车易位”(Castling)及“吃过路兵”(En passant)的例外情形,仅考虑“兵的升变”(Promotion)。
棋的走法如下:(这里会有一些图片)
特殊规则:
如前所述,在本题中只考虑“兵的升变”这一种特殊情形,并且做了简化。当己方的兵走到对方的底线(即最远离己方的一行)时,玩家可选择把该兵升级为车、马、象或后,但不能变王,也不能选择不变。在本题中,我们简化为“玩家将该兵升级为后”(这也是大多数人的选择)。
我们的实现将主要由棋子基类Chess
及其派生类,以及棋盘类Chessboard
构成,分别定义于chess_base.h
、chess.h
、chessboard.h
中。其中,chess_base.h
、chessboard.h
及其相应实现已给出。
Chess
类如下:
// chess_base.h
#pragma once
enum Color {
WHITE, BLACK
};
class Chessboard;
class Chess {
protected:
int x, y;
Color color;
Chessboard* board;
public:
Chess(Chessboard* b, Color c, int x, int y);
~Chess();
// Get properties
Color getColor(); // 获取棋子颜色
virtual void printInfo() = 0; // 打印棋子信息
// Operations
// 保证此处传入的所有参数有意义(不会出现越界、“目标位置为自身位置”
// “目标位置已被占据”、“目标位置无子可吃”等情形)
virtual void move(int nxt_x, int nxt_y); // 直接移动至目标坐标,不做检查
virtual void attack(int nxt_x, int nxt_y); // 直接对目标坐标进行吃子,不做检查
virtual bool isLegalMove(int nxt_x, int nxt_y) = 0; // 检查能否合法移动至目标坐标
virtual bool isLegalAttack(int nxt_x, int nxt_y) = 0; // 检查能否合法对目标坐标吃子
};
Chessboard
类如下:
#pragma once
#include "chess.h"
#include <vector>
class Chessboard {
public:
static const int size = 8;
enum {
FIRST_BLACK_ROW = 1,
SECOND_BLACK_ROW = 2,
FIRST_WHITE_ROW = 8,
SECOND_WHITE_ROW = 7
};
private:
Chess* data[size+1][size+1];
std::vector<Chess*> removed;
void reset();
void clear();
public:
Chessboard();
Chessboard(const Chessboard& other) = default;
~Chessboard();
Chess* getChess(int x, int y);
void moveChess(int cur_x, int cur_y, int nxt_x, int nxt_y);
void placeChess(Chess* chess, int x, int y);
void removeChess(int x, int y);
};
程序的入口在main.cpp
中。main.cpp
实现如下:
#include "chess_base.h"
#include "chessboard.h"
#include <iostream>
int main()
{
Chessboard* chessboard = new Chessboard();
// 或Chessboard* chessboard = new Chessboard(init);
int rounds;
std::cin >> rounds;
Color cur_color = WHITE, opponent_color = BLACK;
while (rounds--)
{
bool flag = false;
while(!flag)
{
int opr_idx, x, y;
std::cin >> opr_idx >> x >> y;
Chess* selected = chessboard->getChess(x, y);
if (selected == nullptr)
{
std::cout << "There's nothing at (" << x << ',' << y << ")." << std::endl;
continue;
}
if (opr_idx == 0)
{
selected->printInfo();
flag = true; // This round ends.
}
else
{
int nxt_x, nxt_y; // FYI nxt is just a short for "next".
std::cin >> nxt_x >> nxt_y;
Chess* dest = chessboard->getChess(nxt_x, nxt_y);
if (nxt_x == x && nxt_y == y)
{
std::cout << "You are not allowed to move a chess with nothing changed." << std::endl;
continue;
}
if (selected->getColor() != cur_color)
{
std::cout << "You are not allowed to change your opponent's chesses." << std::endl;
continue;
}
if (opr_idx == 1)
{
if (dest != nullptr)
{
std::cout << "You are not allowed to move a chess to an occupied position." << std::endl;
continue;
}
if (selected->isLegalMove(nxt_x, nxt_y))
{
selected->move(nxt_x, nxt_y);
flag = true; // This round ends.
}
else
{
std::cout << "You are not allowed to move (" << x << ',' << y << ") to ("
<< nxt_x << ',' << nxt_y << ") because of the rules." << std::endl;
}
}
else if (opr_idx == 2)
{
if (dest == nullptr)
{
std::cout << "You are not allowed to attack nothing." << std::endl;
continue;
}
if (dest->getColor() == cur_color)
{
std::cout << "You are not allowed to attack your own chess." << std::endl;
continue;
}
if (selected->isLegalAttack(nxt_x, nxt_y))
{
selected->attack(nxt_x, nxt_y);
flag = true; // This round ends.
}
else
{
std::cout << "You are not allowed to use (" << x << ',' << y << ") to attack ("
<< nxt_x << ',' << nxt_y << ") because of the rules." << std::endl;
}
}
else
std::cout << "Invalid operation index." << std::endl;
}
}
cur_color = (cur_color == WHITE) ? BLACK : WHITE; // The opponent's turn.
}
delete chessboard;
return 0;
}
如你所见,棋局由白方开始,程序将不断读入数据并尝试执行,直到执行成功时换位另一方移动棋子。请注意,测试所用的main.cpp
可能与默认版本不同,chessboard
也可能由已有Chessboard
对象初始化(小明正在练习残局)。
请你编写chess.h
,并完成各类棋子的实现。
(这里是一个样例输入)
(这里是一个样例输出,可以看出需要输出什么东西,并会加以说明)
通过模板实现一个动态多维数组类(MultiDimArray)。其初始化时创建一个空数组,方式如下:
MultiDimArray<int,3> arr_1({2,3,4}); // int型的三维数组,尺寸为2*3*4
MultiDimArray<float,1> arr_2({7}); // float型的一维数组,尺寸为7
和普通数组一样,动态多维数组使用方括号加下标的方式来访问元素,如:
MultiDimArray<int,3> arr_3({2,3,4});
int a = arr_3[0][1][2];
arr_3[0][1][2] += 1;
const MultiDimArray<int,3> arr_4({1,2,3});
int b = arr_4[0][1][2];
// arr_4[0][1][2] += 1; // 错误,不能更改const数组的元素
动态多维数组支持拷贝和移动。在这个过程中,数组的维数保持不变,但是数组的尺寸可以改变(所谓“动态”),即每个维度的“大小”可以变化。例如,一个三维数组的初始尺寸是$3 \times 3 \times 3$,虽然不能将其改成四维数组或二维数组,但是可以把它的尺寸改为$2 \times 3 \times 4$。如:
MultiDimArray<int,3> arr_5({2,3,4});
MultiDimArray<int,3> arr_6 = arr_5; // 正确,arr_6是arr_5的一个副本
// MultiDimArray<int,4> arr_7 = arr_5; // 错误,维数不同不能复制或移动
MultiDimArray<int,3> arr_8({3,3,3});
arr_8 = std::move(arr_5); // 正确,arr_8尺寸变为2*3*4
模板、继承、函数多态
function
是 c++11 中提供的模板类,其可以储存、复制、调用任何接口相同的可调用目标,例如函数、成员函数、lambda 表达式等。
例如你可以通过 function<int(int,int)>f = max
来构造一个 function
,其接受两个 int
作为传入参数,并返回类型为 int
。
请编写一个 my_func
模板类来实现 function
的基本功能,即包装可调用对象。
有部分分,不同的部分分中使用不同的 main.cpp
进行评测。
第一部分,保证函数类型仅有 void(void)
,且只会使用函数构造 function
。
第二部分,保证可调用目标的传入参数不超过三个。
第三部分无额外限制。
选手还需要实现 my_func
的相关构造、赋值函数与运算符。
如在转发参数时出现了额外的移动或拷贝,会扣除一定分数。
众所周知,大一的小学期里大家就要自己写网页爬虫了,那么不如我们提前来熟悉一下正则表达式的使用。
我们需要将网页中的有效信息提取出来
以html网页文档中如下一段代码为例
<span class="abc" id="xxx">text</span>
span作为一个标签,class一般用于CSS样式相同的模块,统一设置其样式,精简代码。你可以理解为同一个class就是同一类的东西,我们需要编写一个正则表达式实现如下匹配
给定任意一个标签xxx,以及一个样式yyy,我们要把所有满足条件的代码块中的text部分提取出来,并输出,如果不满足则输出not found。
额外要求:输出至指定ostream
第一行标签名称
第二行样式名称
第三行 一个整数m表示后续有m行输入
比如如下输入
div
new
4
<div class="new" id="qwe">hello</span>
<div id="aaa" class="new">hello1</span>
<span class="new">hello2</span>
<div id="new" class="hahaha">hello3</span>
hello
hello1
not found
not found
会提供一个用于处理输入的main.cpp
需要同学们实现的是一个类,以及findText()函数,每次将输出内容传给传入的ostream
class Match{
public:
Match(string label, string classname, ostream & out){
}
void findText();
};
流输出对象
正则表达式
小明在计算函数值时发现很多函数都可以使用C++来实现,而math.h头文件中提供了大量实用的数学函数,在做数学题的他想偷偷懒,于是编写了一个函数类,并且实现了一个指数函数类。他现在又想偷懒了,于是找到了你,希望你完善一次函数、组合函数、复合函数的实现。
代码拆分、完整代码会在Proposal通过后进行编写(逃
main.cpp
主要用于测试三个类实现的正确性,以及是否补充了基类的虚析构函数,从而防止内存泄露
Function.h
#pragma once
#include <vector>
#include <cmath>
class Function{
public:
Function() {}
void getRange(double start, double finish, double step, std::vector<double> data){
for(double pos = start; pos <= finish; pos += step){
data.push_back(getPoint(pos));
}
}
virtual double getPoint(double point);
// Todo
};
// Todo
// 请参照指数函数类(ExponentialFunction)实现一个一次函数类并且补充完整下列的复合函数以及组合函数类
// 复合函数即f(g(x))
// 组合函数即a * f(x) + b * g(x) 形式
// 并且要求,传入的参数的析构在该类被析构时同时析构
// 即补充完整Function类
class LinnerFunction : public Function{
};
class ExponentialFunction : public Function{
private:
double _base;
public:
ExponentialFunction(double base) : _base(base) {}
double getPoint(double point){
return powl(_base, point);
}
};
class CombinationFunction : public Function{
private:
Function *_func_1; // function 1, denoted as f
Function *_func_2; // function 1, denoted as g
double _coefficient_1; // coefficient 1, denoted as a
double _coefficient_2; // coefficient 1, denoted as b
public:
CombinationFunction(Function *fun_1, Function *fun_2, double coe_1, double coe_2)
: _func_1(fun_1), _func_2(fun_2), _coefficient_1(coe_1), _coefficient_2(coe_2) {}
// compute a * f(x) + b * g(x)
// Todo
};
class CompositeFunction : public Function{
private:
Function *_outer; // function 1, denoted as f
Function *_inner; // function 1, denoted as g
public:
CompositeFunction(Function *outer, Function* inner)
: _outer(outer), _inner(inner) {}
// compute f(g(x))
// Todo
};
虚函数、析构函数
我们来模拟一个进行空中管制的塔台的工作。这里主要有两类对象:plane和tower。以下是一些说明。
plane:顾名思义,即飞机。飞机主要有两类属性:
航班号:字符串类型,每一架飞机都拥有一个唯一的航班号。
飞行状态:由位置和速度两部分构成。由于塔台使用雷达,所以飞机的位置采用柱坐标系,即平面极坐标系(距离,角度)加上高度。平常巡航时,飞机是平飞的(显然),所以这里的速度仅仅是指投影到水平面上的移动速度,它包括速度的大小和速度的方向。以上数据均采用double
类型。
距离的单位是海里,角度采用角度制(以x轴为0度,逆时针方向至360度),高度的单位是英尺,速度的单位是海里/小时。
plane的主要功能有:
更新(水平)位置:根据速度大小和方向更新(水平)位置。
更改属性:能够更改高度/速度大小/速度方向。更改时,将设定要达到的高度/速度大小/速度方向。
高度的变化率为60英尺/秒^2,速度大小的变化率是1海里/秒^2,速度方向变化率为2角度/秒。
输出信息:输出飞机航班号、所在位置及速度。
tower:塔台。主要属性为“范围”,即其所管辖的空域半径,double
类型。主要的功能有
我们将模拟一段时间内的管制过程,以1秒为单位时间(tick)进行。在每个tick中,先处理飞机高度/速度大小/速度方向的变化,再处理(水平)位置的更新。
请参考main.cpp,编写plane.h和tower.h。
// main.cpp
#include "plane.h"
#include "tower.h"
#include <iostream>
int main()
{
double range;
std::cin >> range;
Tower tower(range);
bool running = true;
int cmd_num, tick = 0;
std::cin >> cmd_num;
while (cmd_num--)
{
int cur_time;
std::cin >> cur_time;
while (tick < cur_time) // Update the time
{
tower.update();
if (tower.safety_check() == false)
{
running = false;
break;
}
++tick;
}
if (!running)
break;
int opr;
char name[10] = {};
std::cin >> opr >> name;
if (opr == 0) // New plane
{
double dist, angle;
int alt, spd, head;
char dest[10] = {};
std::cin >> dist >> angle >> alt >> spd >> head >> dest;
tower.addPlane(Plane(name, dist, angle, alt, spd, head));
}
else if (opr == 1) // Set altitude
{
int alt;
std::cin >> alt;
tower[name].setAltitude(alt);
}
else if (opr == 2) // Set speed
{
int spd;
std::cin >> spd;
tower[name].setSpeed(spd);
}
else if (opr == 3) // Set heading
{
int head;
std::cin >> head;
tower[name].setHeading(head);
}
else if (opr == 4) // Print a plane's information
{
tower[name].printInfo();
}
else if (opr == 5) // Print all information
{
tower.printAllInfo();
}
else
{
std::cout << "Invalid operation" << std::endl;
}
}
if (running)
std::cout << "Safe" << std::endl;
else
std::cout << "Game over" << std::endl;
return 0;
}
虚函数、多态、向下类型转换、输入输出流重载
题目提供基类 Point 表示二维平面上一点,重载输入输出
class Point { // 点类
private:
int x, y;
public:
Point(int _x, int _y); // 表示二维平面内一点
~Point();
friend istream &operator>>(istream &in, Point &P);
friend ostream &operator<<(ostream &out, const Point &P);
};
题目提供抽象基类 Shape 表示一个几何图形,继承自 Point
class Shape: public Point { // 形状类,抽象基类
public:
Shape();
virtual ~Shape() = 0;
virtual int area() = 0; // 表示面积
virtual int circum() = 0; // 表示周长
};
需要实现派生类 Rectangle 表示矩形,继承自 Shape
class Rectangle: public Shape { // 矩形类
private:
Point A, B; // 左下角和右上角坐标
public:
Rectangle(Point _A, Point _B);
~Rectangle();
int area() override;
int circum() override;
bool contain(Point P); // 判断点是否在矩形中(或边上)
};
需要实现派生类 Square 表示正方形,继承自 Rectangle
class Square: public Rectangle { // 正方形类
public:
Square(Point _A, Point _B);
~Square();
};
需要实现派生类 Circle 表示圆,继承自 Shape
class Circle: public Shape { // 圆形类
private:
Point O; // 圆心
int r; // 半径
public:
int area() override;
int circum() override;
};
额外函数:
Rectangle *init(Point A, Point B); // 根据 A 和 B 的位置关系生成一个 Rectangle 或 Square 类指针
string getType(Shape *S); // 返回一个字符串表示实际类型
计划在下发的 .h 中实现构造函数和析构函数,让做题人在 .cpp 中实现其余函数
输入 n 个形状(通过 Point 类输入流),只知道为 Rectangle 或 Circle ,对 Rectangle 类输入调用 init 函数,用 Shape* 数组存储所有形状
依次查询数组中每个元素的 area, circum, getType,需要与标准输出一致
计划下发不可修改的 main.cpp 与 Makefile
如下。
函数对象、std::function
、lambda表达式、类模板
很多时候排序仅仅靠一个关键字是不够的。例如考试排名,首先按总分降序排列;如果总分相同,再按照语文成绩降序排列;如果语文成绩也相同,再按照数学成绩降序排列……
现在我们来考虑一个具体的问题。给定n个2维点(x,y)
,首先按点到原点的距离从小到大排序;如果两点距离相同,则按x坐标从小到大排序;如果仍相同,则按y坐标从小到大排序。
我们有point
类已经写好:
class point {
public:
int x, y;
int dis() { return x*x + y*y; }
};
以及比较两个点到原点距离的函数、比较两点x/y坐标大小的函数:
auto discomp = [](point l, point r) { return l.dis() < r.dis(); };
auto xcomp = [](point l, point r) { return l.x < r.x; };
auto ycomp = [](point l, point r) { return l.y < r.y; };
你需要实现一个Compare类来完成这样的多重排序,就像这样:
vector<point> v;
// ...
Compare<point> comp = { discomp,xcomp,ycomp };
sort(v.begin(),v.end(),comp);
完整的main.cpp如下
#include <vector>
#include <algorithm>
#include <string>
#include <iostream>
#include <cstdio>
#include "compare.h"
using namespace std;
class point {
public:
int x, y;
int dis() { return x*x + y*y; }
};
istream& operator>> (istream& in, point& p) {
string s; int x, y;
in >> s;
sscanf(s.c_str(), "(%d,%d)", &x, &y);
p.x = x, p.y = y;
return in;
}
ostream& operator<< (ostream& out, const point& p) {
out << "(" << p.x << "," << p.y << ")";
return out;
}
int main()
{
auto discomp = [](point x, point y) { return x.dis() < y.dis(); };
auto xcomp = [](point x, point y) { return x.x < y.x; };
auto ycomp = [](point x, point y) { return x.y < y.y; };
Compare<point> comp = { discomp,xcomp,ycomp };
int n;
cin >> n;
vector<point> v;
while (n--) {
point p;
cin >> p;
v.push_back(p);
}
sort(v.begin(), v.end(), comp);
for (auto p : v)
cout << p << ' ';
return 0;
}
你需要自己编写compare.h以实现上述功能。
现在对于一个给定的表(每一列有列标题),你需要按用户指定的顺序进行多重排序。
表的内容都是int型。
输入样例:
4 4 3 // 表4行4列(不含列标题);多重排序有3个指令
Chinese math English total // 列标题
98 98 100 296
100 98 98 296
98 100 98 296
100 100 100 300
total d // 首先按total列降序排列
Chinese d // 然后按Chinese列降序排列
math a // 最后按math列升序排列
输出样例:
Chinese math English total
100 100 100 300
100 98 98 296
98 98 100 296
98 100 98 296
main.cpp已写好,已经实现表的列标题和内容的读取,以及整个表的输出,你不能修改;你需要编写sort.cpp实现make_comp
函数,从IO流中读入多重排序的指令,并返回一个Compare<vector<int>>
作为sort
函数的比较器。
main.cpp:
#include <vector>
#include <algorithm>
#include <iostream>
#include <string>
#include "compare.h"
using namespace std;
Compare<vector<int>> make_comp(vector<string>,int);
int main()
{
int m, n, b;
cin >> m >> n >> b;
vector<vector<int>> v(m, vector<int>(n)); // 生成m行n列的vector
vector<string> titles;
for (int i = 0; i < n; i++) {
string title;
cin >> title;
titles.push_back(title);
}
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
cin >> v[i][j];
sort(v.begin(), v.end(), make_comp(titles,b));
for (auto s : titles)
cout << s << ' ';
cout << '\n';
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
cout << v[i][j] << ' ';
cout << '\n';
}
return 0;
}
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.