78 lines
4.3 KiB
TeX
78 lines
4.3 KiB
TeX
|
\documentclass[实验报告模板]{subfiles}
|
|||
|
|
|
|||
|
|
\renewcommand{\mydate}{
|
|||
|
|
2023/11/24
|
|||
|
|
}
|
|||
|
|
\renewcommand{\mychapternum}{6}
|
|||
|
|
|
|||
|
|
\begin{document}
|
|||
|
|
\mytitle
|
|||
|
|
\begin{enumerate}
|
|||
|
|
\myitem{实验目的}{
|
|||
|
|
\item 使用第六章的知识解决图的综合问
|
|||
|
|
题。
|
|||
|
|
}
|
|||
|
|
\myitem{实验内容}{
|
|||
|
|
\item 某国有 n 个城市，他们之间没有路连通，因此交通十分不便，现决定修
|
|||
|
|
建公路，任务由各个城市共同完成。修建分为 n 轮，在每一轮，每个城
|
|||
|
|
市选择一个与它最近的城市，申请修往该城市的公路，政府负责审批这
|
|||
|
|
些申请决定是否同意修建。
|
|||
|
|
|
|||
|
|
政府审批规则如下：
|
|||
|
|
|
|||
|
|
I.如果两个城市申请修建同一条公路，则让后申请修建的城市重新选择
|
|||
|
|
未申请修建的公路。
|
|||
|
|
|
|||
|
|
II.如果三个或以上城市申请修建的公路成环，即 A 申请修建 AB，B 申
|
|||
|
|
请修建 BC，C 申请修建 CA，则政府将否决其中最短的一条公路的修建申
|
|||
|
|
请。
|
|||
|
|
|
|||
|
|
III.其他情况一律同意。
|
|||
|
|
|
|||
|
|
一轮修建后，若干城市将会直接或间接相连，连通的城市被看作一个
|
|||
|
|
league，下一轮修建中，league 被看作为一个城市。当所有的城市都连
|
|||
|
|
通时，则修建完毕。根据上述规则计算需要修建的公路的总长度。
|
|||
|
|
|
|||
|
|
\item 每个城市的规模大小是不同的（在初始需要赋值），在每个城市申请修
|
|||
|
|
建通往其他城市的道路时，需要查看城市规模系数$\alpha $，若规模小于目标
|
|||
|
|
城市，则政府拒绝修建，若两个城市规模相等，则修建过后两座城市形
|
|||
|
|
成的 league 城市规模系数$\alpha $增一，若大于目标城市，则同意修建，规
|
|||
|
|
模系数不变。当城市规模系数$\alpha $到达限定系数$\beta $后，我们认为该 league
|
|||
|
|
已经到达“稳定”，不再与任何其他城市修建公路。根据上述规则计算
|
|||
|
|
需要修建的公路的总长度。
|
|||
|
|
}
|
|||
|
|
\myitem{实验原理}{
|
|||
|
|
\item 程序设计原理。
|
|||
|
|
}
|
|||
|
|
\myitem{实验步骤}{
|
|||
|
|
\item 问题抽象
|
|||
|
|
\item 编写程序
|
|||
|
|
\item 调试程序
|
|||
|
|
\item 完善总结
|
|||
|
|
}
|
|||
|
|
\myitem{调试过程、结果和分析}{
|
|||
|
|
\item 子类继承父类的时候应该不需要手动调用父类的析构函数，因为编译器会自动调用；
|
|||
|
|
\item 调试带有随机性质的程序要先把随机数种子固定下来，调试完再用时间戳作为随机种子；
|
|||
|
|
\item 类的保护属性在类外能直接访问？
|
|||
|
|
}
|
|||
|
|
\myitem{总结}{
|
|||
|
|
\item 采用何种设计架构要综合考虑项目周期、系统复杂度、掌握熟练度等一系列因素，比如虽然这次的题可能有在时间复杂度或空间复杂度上更优的算法来解决，但是考虑到时间有限，还是使用了比较容易实现的思路；
|
|||
|
|
\item CLion的自动补全确实更加顺手，而且还能自动生成构造函数、析构函数等；
|
|||
|
|
\item 此次也没有进行非常复杂的对象设计，只实现了并查集的类、图的类、复杂图的类；
|
|||
|
|
\item 由于需要多次合并城市为一个联盟，所以使用了并查集；
|
|||
|
|
\item 做题之前可以先考虑是否可以简化问题，比如这次的题的第二条规则就是无效的；
|
|||
|
|
\item 输出的方式不一定要像图形界面，可以用文字表示，比如图可以用邻接矩阵、关系矩阵表示。
|
|||
|
|
}
|
|||
|
|
\myitem{附件}{
|
|||
|
|
\itemsep 5em
|
|||
|
|
\item graph.cpp
|
|||
|
|
\inputminted[linenos=true, breaklines=true]{cpp}{../C++/第六章作业/graph.hpp}
|
|||
|
|
\item 第六章作业1.cpp
|
|||
|
|
\inputminted[linenos=true, breaklines=true]{cpp}{../C++/第六章作业/第六章作业1.cpp}
|
|||
|
|
\item 第六章作业2.cpp
|
|||
|
|
\inputminted[linenos=true, breaklines=true]{cpp}{../C++/第六章作业/第六章作业2.cpp}
|
|||
|
|
\item CMakeLists.txt
|
|||
|
|
\inputminted[linenos=true, breaklines=true]{cmake}{../C++/第六章作业/CMakeLists.txt}
|
|||
|
|
}
|
|||
|
|
\end{enumerate}
|
|||
|
|
\end{document}
|