LAB1

这是往年学期THU课堂的第一道题目的部分内容。每个学期使用的题目版本可能会有变化。

你可以在开学前做一些尝试。我们也预留了开学后再开始做这道题目的时间，也可以在开学后加入OJ完成和提交这道题目。

1. 背景概述

实际工作科研中编写代码时，经常需要对程序进行测试和调试。比起实际场景中的工程项目，数据结构的编程作业都属于简短的小型程序。不过为了高效地完成作业，同学最好也掌握一些基本的程序调试和测试技巧。

这道LAB题目会通过一道简单的例题，为你展示一些调试和测试代码的技巧，首先你要跟着题目的指示，完成一些思考题和一些测试/调试的任务。最后，你要实现一个时间复杂度符合要求、常数因子合理的程序，通过黑盒测试（大部分普通的作业题目只需要构思算法、实现程序通过黑盒测试并编写实验报告）。

2. 一道例题

2.1 应用背景

农机跨区作业是中国农民在农业机械化生产中的一个创举。每年夏季，按照我国小麦成熟“南早北晚”的时间顺序，机收队伍由南向北一路进发，为各地成熟的麦田提供小麦机收服务，提高了农机使用效率。但如何将大量的农机和大量待收割的麦田进行时间、空间上的匹配，为大量的农机规划行进路线，确保机器不闲置、麦熟及时收，是一个调度难题，需要多个层次的统计分析和分级调度。

农机手往往组成合作社，由社长帮忙联系有麦田待收割的客户，指挥社内的农机赶往急需农机的地块提供麦收服务。

县、市各级行政辖区，会对下属各个行政辖区的农机数量、待收麦田数目进行统计，绘制农机作业分布图。

大量收割机上安装的北斗终端通过移动通信网络，向农机企业回传收割机的位置与工况数据；农机企业向中国农业大学建设的国家农机作业大数据中心，实时转发北斗终端的部分数据；中国农业大学北斗团队据此统计作业时长、作业里程和作业面积，制作每日收割作业热点图、每日进度动图、单机收割作业效率图、地市收割面积分布图、地市累计收割面积分布图、单机收割面积排行榜等信息产品。

某个较大区域内的收割总面积，是用区域内所有小地块的收割面积累加得到的。

现在要求实现这样的功能：已知各个小地块的收割情况，多次请求汇总一个较大的矩形区域的收割总量，每次询问的矩形区域可能不同。（暂不考虑小地块的收割情况随时间变化）。

2.2 模型抽象

从这个背景中，我们抽象出一道这样的题目：

输入一个n行m列的数字矩阵，多次查询某个子矩阵中的所有数字之和。我们用左上角的坐标(x, y)和子矩阵大小(a,b)表示一个子矩阵，也就是从第x行到第 x+a-1 行，从第y列到第y+b-1列，这些数字加起来求和。

2.3 输入输出格式

输入格式:

第一行两个数字n,m 表示行数和列数，

接下来n行每行m个数字表示整个矩阵。

接下来一个数字q表示询问次数。

接下来q行，每行四个数字x,y,a,b,表示查询左上角(x,y),大小a行b列的子矩阵的所有数字之和。

输出格式：

对于每次询问，输出一行一个数字，表示查询的结果。

2.4 样例输入输出

样例输入

4 4
1 2 3 4
5 6 7 8
4 3 2 1
9 8 7 6
4
1 1 1 1
1 3 4 2
2 2 3 3
1 1 4 4

样例输出

1
38
48
76

2.5 黑盒测试数据范围和时空限制

n,m <= 2000，q <= 100000

矩阵中每个元素<=1000.

空间限制：128 MB

时间限制：1s

3 关于黑盒测试

3.1 黑盒测试简介

我们的OJ（online judge，在线评测系统）会通过黑盒测试来检验程序是否具有合理的常数因子和正确的渐进时间复杂度。

尽管渐进时间复杂度的定义中，要求问题规模n（也就是测试数据的数据范围）趋于无穷大。

但实际中，我们不能让程序在评测系统中执行无穷长的时间，可以选择一个“足够大”的n来进行测试。

原理为：限定执行程序的硬件平台（我们的OJ服务器）、测试数据的范围、程序执行的时间空间限制，如果程序在给定的时间空间内能够执行完成，就说明程序的时间复杂度和常数因子都是合理的。

例如，如果程序在1秒内能够通过 测试数据范围 n=3000 的测试，我们说这个程序大概率具有不超过 \(O(n^2)\) 的渐进时间复杂度和合理的常数因子。

例如，如果程序在1秒内能够通过 测试数据范围 n=500000 的测试，我们说这个程序大概率具有不超过 \(O(nlogn)\) 的渐进时间复杂度和合理的常数因子。

具体的数据范围n的大小可能根据题目的类型、硬件平台的性能有所不同，这里的3000、500000都是用来举例的数字。

3.2 思考题

下面是两道思考题，需要在实验报告中提交。

思考题1:

假设某个评测系统在测试程序时每秒钟执行\(10^8\)条指令，执行一条指令的用时是确定的。对于某个问题P，问题规模为\(n\), 助教编写的一个较为正确的程序可以执行\(10 \times n^2\)条指令完成计算。

假设程序运行时间只取决于程序执行指令条数, 我们认为，只要某个同学提交的程序在测试时，执行的指令条数/运行时间不超出助教程序的2倍，就都认为正确的，否则认为程序超时。

现在将评测系统上这道题目的时间限制设置为1秒，为了让我们认为正确的程序在时间限制内通过测试，超时的程序不通过测试，助教应当准备\(n\)最大为多少的黑盒测试数据？

时间限制1秒不变，如果助教编写的程序执行\(20n\times log_2n\)条指令，又应当准备n最大为多少的黑盒测试数据？

时间限制1秒不变，如果问题规模包含两个参数n,m, 助教编写的程序执行\(20n\times log_2m\)条指令，又应当如何准备一系列黑盒测试数据，才能尽量确保通过黑盒测试的程序具有合理的时间复杂度？假设可以准备的黑盒测试数据个数是有限的，如20个。

（要求都给出计算或思考过程）

思考题2:

在思考题1中，我们假设的计算模型“执行一条指令的用时是确定的”，实际计算机的指令执行是这样的吗？如果不是这样，那么我们的假设在何种意义下合理？

（简单描述，100字以内即可）

4 调试和测试

4.1 完成下列任务

首先准备一个命令行环境。我们建议你使用类Unix命令行环境（可以是linux命令行、Mac OS命令行 或 Window Subsystem for Linux，即WSL）进行开发，并使用较高版本的g++/clang++编译器，结合Visual Studio Code编辑器进行开发。如果使用其他开发环境，并遇到和环境有关的问题，助教将无法为你提供帮助。配置环境中遇到问题请联系助教。

下载附件: https://github.com/Tsinghua-DSA/JumpIntoDSA/blob/main/docs/LAB1/LAB1.zip。

附件中包含例题的两份代码（solution_1.cpp和solution_2.cpp)，时间复杂度不同，各自具有一些bug。另外还包括一个“多文件项目”，在link文件夹下。

完成下列任务:

1. 尝试通过仔细阅读代码，找出 solution_1.cpp 和 solution_2.cpp 中存在的bug，并进行修改。即使你认为这一步已经找出了所有bug，也要将接下来的步骤做完。
2. 尝试在程序中增加更多的输出语句，打印计算的中间结果。例如打印循环中的sum变量每一次被累加上的数值是多少、累加之后sum的数值变成了多少。在打印时附加额外的提示信息，输出形如“sum = xxx，sum+=xxx” 这样的信息，否则你看到的就只是一大长串意义模糊的数字。
3. 学习命令行中的gdb用法，在命令行中编译程序，在命令行尝试通过gdb对solution_1.cpp进行单步调试。一次执行一行代码、打印当前某个变量的数值、在某一行代码设置断点。
4. 尝试使用battle.cpp对solution_1和solution_2进行“对拍”: 不断生成随机的输入数据，用相同的输入执行两个程序，比较它们输出的不同。如果它们的输出不同，说明两个程序中至少有一个是错的。找到一个使得程序出错的测例，就可以用这个测例来进一步仔细调试。
5. 代码补全: link文件夹中是一个多文件项目，包含main.cpp, solve1.cpp, solve2.cpp, solve1.h, solve2.h 五个文件。你需要参考solution_1.cpp补全solve1()函数，参考solution_2.cpp补全solve2()函数。将这些文件编译链接，最终编译出的程序接受一个命令行参数，命令行参数为1时，执行solve1.cpp中的算法（相当于solution_1.cpp)。命令行参数为2时，执行solve2.cpp中的算法(相当于solution_2.cpp)。提示：solve2()所需进行的初始化可以借助在函数内定义static变量来完成。
6. （选做，不计分）: 用面向对象的代码风格重构link文件夹中的项目。提示：strategy pattern。

4.2 填写实验报告

在实验报告中描述你找出了哪些bug，是怎样找到的。

在实验报告中描述你如何用gdb单步执行程序（使用什么命令），为了在命令行使用gdb调试需要使用什么编译选项。

rand_input.cpp中，首先会调用srand(time(0))，在实验报告中回答，它的作用是什么？

查询相关文档，在实验报告中描述battle.cpp每一次调用system()执行了什么命令，做了什么事情。

在实验报告中回答: 命令行参数 argv[0] 的含义是什么?

在实验报告中提交你编译link文件夹中的项目的编译命令、用命令行参数运行程序的命令，以及补全后的solve1(), solve2()两个函数。

5 优化和比较

5.1 完成下列任务

请你编写一个更加优化的程序，它多做一些预处理，但处理每次询问只需要O(1)的时间。

提示：solution_2比solution_1减少了一层循环。运用同样的方法，在solution_2的基础上再减少一层循环。将这个新的解法叫做solution_3.

现在，你可以修改rand_input.cpp, 指定n,m,q, 生成几个测试数据，分别测试修改正确的solution_1, solution_2, solution_3 的用时。 （在命令行使用time命令测试程序执行使用的时间）

至少构造两类测试数据，一类测试数据使得solution_3相比另外两个程序展现出明显优势，一类测试数据中solution_3没有明显优势。

5.2 填写实验报告

包括前面所有提到要在实验报告中体现的内容。