《程序设计艺术与方法》课程实验报告

程序设计艺术与方法 课程实验报告 一 实验名称 STL 的熟悉与使用 姓 名系院专业 信息工程 系 班 级 物联网一 班 学 号 实验日期指导教师成 绩 一 实验目的和要求一 实验目的和要求 1 1 掌握 C 中 STL 的容器类使用 2 掌握 C 中 STL 的算法类的使用 二 实验预习内容二 实验预习内容 Vector list 可当作列表使用的数据结构 它们都是动态增长的 1 vector 表示一段连续的内存区域每个元素被顺序储存在这段内存中 对 vector 的随即访问效 率很高 但是在任意位置而不是在 vector 末尾插入元素则效率很低 因为它需要把待插入元 素的右边的每个元素都拷贝一遍 类似的删除任一个而不是 vector 的最后一个元素效率低 2list 表示非连续的内存区域并通过一对指向首尾元素的指针双向进行遍历在 list 的任意位置 插入和删除元素的效率都很高 指针必须被赋值但不需要用拷贝元素来实现移动 另一方面 它对随机访问的支持并不好访问一个元素需要遍历中间的元素 另外每个元素还有俩不能给 个指针的额外空间开销 3 泛型算法让编写一般化并可重复使用的算法 其效率与指针对某特定数据类型而设计的算 法相同 泛型即是指具有在多种数据类型上皆可操作的含义 与模板有些相似 STL 巨大而 且可以扩充 它包含很多计算机基本算法和数据结构 而且将算法与数据结构完全分离 其 中算法是泛型的 不与任何特定数据结构或对象类型系在一起 三 实验项目摘要三 实验项目摘要 1 练习vector 和list 的使用 定义一个空的vector 元素类型为int 生成10 个随机数插入到vector 中 用迭代 器遍历vector 并输出其中的元素值 在vector 头部插入一个随机数 用迭代器遍历vector 并输出其中的元素值 用泛型算法find 查找某个随机数 如果找到便输出 否则将此数 插入vector 尾部 用泛型算法sort 将vector 排序 用迭代器遍历vector 并输出其中的元 素值 删除vector 尾部的元素 用迭代器遍历vector 并输出其中的元素值 将vector 清 空 定义一个list 并重复上述实验 并注意观察结果 2 练习泛型算法的使用 定义一个vector 元素类型为int 插入10 个随机数 使用sort 按升序排序 输出 每个元素的值 再按降叙排序 输出每个元素的值 练习用find 查找元素 用min 和 max 找出容器中的最小元素个最大元素 并输出 四 实验结果与分析 源程序及相关说明 四 实验结果与分析 源程序及相关说明 1 练习vector 和list 的使用 include include include include include using namespace std vector myV bool sortup int v1 int v2 return v1 v2 int main int argc char argv srand time NULL 随机产生十个数 for int i 0 i 10 i myV push back rand sort myV begin myV end sortup 用 sort 排序升序 vector iterator it1 for it1 myV begin it1 myV end it1 cout it1 setw 6 打印数组 cout endl int min myV 0 for it1 myV begin 1 it1 myV end it1 if it1 min min it1 cout 最小元素为 min max max it1 cout 最大元素为 max endl cout endl int value rand it1 find myV begin myV end value if it1 value cout 找到了这个随机数 endl else cout 没有找到这个随机数 endl myV insert myV end value 数组中没有随机数 插入尾部 cout 插入尾部的随机数为 value endl for it1 myV begin it1 myV end it1 cout it1 setw 6 cout n endl 随机在 vector 头部插入一个随机数 int t rand 定义 t 将一个随机数赋给 t 插入到数组 头部 myV insert myV begin t cout 插入头部的随机数为 t endl for it1 myV begin it1 myV end it1 cout it1 setw 6 cout endl 删除尾部元素 myV pop back for it1 myV begin it1 myV end it1 cout it1 setw 6 cout endl myV clear 清空数组 if myV empty cout It s empty endl system PAUSE press any key to continue return 0 运行截图 2 练习泛型算法的使用 include include inclued using namespace std typedef list lin int value 2 4 6 1 8 void print lin lin iterator lit 定义一个迭代器 for lit l begin lit l end lit cout lit 打印 list 中的元素 cout v2 int main lin lin2 lin2 push front 3 lin2 push front 4 lin2 insert lin2 begin value value 5 cout lin2 内的元素为 print lin2 lin2 sort cout 排序后的 lin2 print lin2 lin2 push front 10 在 list 头部插入 10 cout 在 list 头部插入 10 之后的结果 print lin2 lin2 remove 6 cout 删除一个数后的 lin1 print lin2 system PAUSE press any key to contineu return 0 运行截图 二 实验名称 搜索算法的实验 姓 名系院专业 信息工程 系 班 级 物联网一 班 学 号 实验日期指导教师成 绩 一 实验目的和要求一 实验目的和要求 1 掌握宽度优先搜索算法 2 掌握深度优先搜索算法 二 实验预习内容二 实验预习内容 1 宽度优先搜索算法 又称广度优搜索 是最简单的图的算法的原形 其属于一种盲搜寻法 目的是系统地展开并检查图中的所有节点 以寻找结果 换句话说 它并不考虑结果的可能 位址 彻底地搜索整张图 直到找到结果为止 2 深度优先搜索算法 它的目的是要达到被搜索结构的叶结点 在一个 HTML 文件中 当一 个超链被选择后 被连接的 HTML 文件将执行深度优先搜索 即在搜索其余的超链走到不能 再深入为止 然后返回到某一个 HTML 文件 再继续选择该 HTML 文件中的其他超链 当 不再有其他超链可选择时 说明搜索已经结束 三 实验项目摘要三 实验项目摘要 1 将书上的走迷宫代码上机运行并检验结果 并注意体会搜索的思想 2 八皇后问题 在一个国际象棋棋盘上放八个皇后 使得任何两个皇后之间不相互攻击 求出所有 的布棋方法 上机运行并检验结果 思考 将此题推广到N 皇后的情况 检验在N 比较大的情况下 比方说N 16 的时 候 你的程序能否快速的求出结果 如果不能 思考有什么方法能够优化算法 3骑士游历问题 在国际棋盘上使一个骑士遍历所有的格子一遍且仅一遍 对于任意给定的顶点 输出一条符合上述要求的路径 4 倒水问题 给定2 个没有刻度容器 对于任意给定的容积 求出如何只用两个瓶装出L 升 的水 如果可以 输出步骤 如果不可以 请输出 No Solution 四 实验结果与分析 源程序及相关说明 四 实验结果与分析 源程序及相关说明 2 八皇后问题 include 声明常量 N 存储行和列 define N 8 define NUM 8 声明全局变量 h N N 控制盘格 H N N 控制输出 n N 存储每一步的 纵坐标 count 用于计数 int h N N n N H N N int count 0 声明函数 void tryit int int 尝试符合条件的方法 void tryit int int 声明函数 void outputArray int N 输出数组 void outputArray int N main int x 0 y 0 i j 初始化为零 for i 0 i N 1 i for j 0 j N 1 j h i j 0 tryit x y printf 其他的布局略 n printf 共有 d 种布局 n 92 return 0 定义函数 void tryit int int 尝试符合条件的方法 void tryit int x int y int i j if count 0j 0 对皇后处的点作出标志 h x y x 1 完成一种走法作出处理 if x 7 转换成输出的格式 for i 0 i N 1 i for j 0 j N 1 j if h i j 0 H i j 1 else H i j 0 count count 1 输出前几种情况 if count NUM printf 布局 d n count outputArray H 对下一种走法 清楚前一次的影响 for i 0 i N 1 i for j 0 j7 清楚前一次影响 for i 0 i N 1 i for j 0 j 0 tryit x 1 n x 1 1 else tryit 0 0 尝试下一格 else tryit x y 1 定义函数 void outputArray int N 输出数组 void outputArray int h N int i j for i 0 i N 1 i for j 0 j N 1 j printf d h i j printf n 运行截图 4 倒水问题 include stdio h int main int ca cb cc x y while scanf d d d else if ca cc printf fill A n printf pour A B n else x y 0 if caca x 如果 b 中的水大于 a 中的剩余容积 就把 a 灌满 y ca x x ca printf pour B A n else 如果 b 中的水小于 a 中的剩余容积 那么把 b 中的水全加入 a x y y 0 printf pour B A n if y cc 如果 b 中的水已经和 cc 相等 那就结束 break if ca x 如果 a 中的水满了 就把 a 倒空 x 0 printf empty A n else while 1 if x 0 x ca printf fill A n if x cb y 如果 a 中的水大于 b 中的剩余容积 就把 b 灌满 x cb y y cb printf pour A B n else 如果 a 中的水小于 b 中的剩余容积 那么把 a 中的水全加入 b y x x 0 printf pour A B n if y cc 如果 b 中的水已经和 cc 相等 那就结束 break if y cb 如果 b 中的水满了 就把 b 倒空 y 0 printf empty B n printf success n return 0 运行截图 三 实验名称 计算几何算法的实现 姓 名系院专业 信息工程 系 班 级 物联网一 班 学 号 实验日期指导教师成 绩 一 实验目的和要求一 实验目的和要求 1 理解线段的性质 叉积和有向面积 2 掌握寻找凸包的算法 3 综合运用计算几何和搜索中的知识求解有关问题 二 实验预习内容二 实验预习内容 凸包 是一组点集中的子集 这一子集形成的凸多边形可以将点集中所有的点都围住 并且 这一凸边形的面积是最小的 一种寻找凸包的算法 打包法 首先 我们找出点集中最下方的点 如果这样的点不止一个 就选用 最左边的点 如P0 显然 这个点 P0 是凸包子集中的一个点 可以设想在P0 处拴了一根 皮筋的一端 另一端放在和P0 成水平位置的右侧 现在 将皮筋 沿逆时针方向转动 首先会 碰到P1 这样就找到了另一个凸包子集中的点 以P1 为中心 做和P0 一样的事 会发现 我 们将碰到P3 又一个凸包的点 我们可以一直这样做下去 直到再一次遇到P0 凸包就被找出 来了 具体而言 在第一次找到P0 点之后 以P0 为每个矢量的起点 其它的点为矢量的终点 来比较任意两个矢量的转角 就可以对余下的点进行按极角排序 三 实验项目摘要三 实验项目摘要 1 将讲义第三章第三节中的凸包代码上机运行并检验结果 2完成讲义第三章的课后习题 上机运行并检验结果 3思考 判线段相交时 如果有个线段的端点在另一条线段上 注意可能与另一条线段上的 端点重合 思考这样的情况 4房间最短路问题 给顶一个内含阻碍墙的房间 求解出一条从起点到终点的最最短路径 房间的边界 固定在x 0 x 10 y 0 和y 10 起点和重点固定在 0 5 和 10 5 房间里还有0 到18 个 墙 每个墙有两个门 输入给定的墙的个数 每个墙的x 位置和两个门的y 坐标区间 输出最短路的长度 四 实验结果与分析 源程序及相关说明 四 实验结果与分析 源程序及相关说明 3 思考 用跨立方法 跨立的含义是 如果一条线段的一个端点在一条直线的一边 另一个 端点在这条直线的另一端 我们就说这条线段跨立在这条直线上 线段相交满足且 只需满足如下两个条件就可以了 1 两条线段相互跨立 2 一条线段的一个端点在 另一条线段上 如果两线段相交 则两线段必然相互跨立对方 若 p1p2 跨立 p3p4 则矢量 p1 p3 和 p2 p1 位于矢量 p4 p3 的两侧 即 p1 p3 p4 p3 p2 p3 p4 p3 0 当 p1 p3 p4 p3 0 时 说明 p1 p3 和 p4 p3 共线 但是因为已经通过快速排斥试验 所以 p1 一定在线段 p3p4 上 同理 p4 p3 p2 p3 0 说明 p2 一定在 p3p4 上 所以判断 p1p2 跨立 Q1Q2 的依据 是 p1 p3 p4 p3 p4 p3 p2 p3 0 同理判断 Q1Q2 跨立 P1P2 的依据是 p3 p1 p2 p1 p2 p1 p4 p1 0 代码中函数 bool segment intersect 用于判断 p1 p2 构成的线段和 p3 p4 构成的线段是否相交 可以看出共五种情况两线段是相交的 反之就输出 The two are Not intersected 4 房间最短路问题 include include include innclude using namespace std typedef pair POINT 线段 double direction POINT p POINT p1 POINT p2 POINT v1 v2 v1 first p2 first p1 first v1 second p2 second p1 first v2 first p1 first p first v2 second p1 second p second return v1 first v2 second v1 second v2 second bool on segment POINT p POINT p1 POINT p2 double min x p1 firstp2 first p1 first p2 first double min y p1 secondp2 second p1 second p2 second if p first min x else return fal