算法设计与分析实验报告-贪心算法
校课程的简单实验报告。
算法设计与分析实验报告-递归与分治策略
算法设计与分析实验报告-动态规划算法
算法设计与分析实验报告-贪心算法
dijkstra迪杰斯特拉算法(邻接表法)
算法设计与分析实验报告-回溯法
算法设计与分析实验报告-分支限界法
算法设计与分析实验报告-分治法相关练题
北京大学出版社-算法设计与分析
一、实验目的
1.理解贪心算法的概念;
2.掌握贪心算法的基本要素;
3.掌握设计贪心算法的步骤和策略。
二、实验内容
使用贪心法求解以下问题,要求给出程序代码,并编译运行程序:
1.P118习题2。
2.P118习题5。
三、实验环境
1. 使用的操作系统及版本:
Windows 10
2. 使用的编译系统及版本:
CLion 2022.2.4
四、实验步骤及说明
1、P118习题2
对于用邻接链表表示的有向无环图,设计一个解单起点最短路径问题的线性算法。
dijkstra迪杰斯特拉算法(邻接表法)
代码如下:
//
// Created by GiperHsiue on 2022/11/27.
//
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
#define INFINE 99999 // 定义最大
// 邻接表
struct ArcNode // 边信息
{int adjvex; //有向边的 目标顶点 下标(从1开始)int weight; //边的权值struct ArcNode *next; //邻接表, 指向下一个邻接边信息
};
struct VertexNode // 顶点
{int vertex; //顶点下标(1 ~)ArcNode *firstedge; // 有向边信息节点指针(源为vertex)
};
struct AdjList // 图
{vector<VertexNode> adjlist; //顶点数组int vexnum; //顶点数 int arcnum; //边数
};
// 图的初始化
void createGraph(AdjList& G){cout << "输入顶点数 边数: " << endl;cin >> G. vexnum >> G. arcnum;// 初始化G的顶点数组for(int i = 0; i <= G. vexnum; i ++){ // 下标从1开始, 所以初始化vexnum + 1个顶点(0无作用)VertexNode* tmp = new VertexNode;tmp->vertex = i, tmp->firstedge = nullptr;G. adjlist. emplace_back(*tmp);}//边信息// n1: 源顶点 n2: 目标顶点 we: 权重(距离)int n1, n2, we;cout << "输入边信息: (a b we): " << endl; // a -> b weight: wefor(int i = 0; i < G. arcnum; i ++){cin >> n1 >> n2 >> we;// 初始化一个边节点, 目标顶点为n2ArcNode* tmp = new ArcNode;tmp->adjvex = n2, tmp->weight = we;// 头插法 将边信息节点插入// 节约时间(尾插要一直遍历到尾部插入)tmp->next = G. adjlist[n1]. firstedge;G. adjlist[n1]. firstedge = tmp;}
}
// 获取两顶点之间权重weight(距离)
int getWeight(AdjList& G, int n1, int n2){if(n1 == n2) return 0;ArcNode* tmp = G. adjlist[n1]. firstedge;while(tmp){if(tmp->adjvex == n2) return tmp->weight;tmp = tmp->next;}// 两点之间没有边, 返回INFINEreturn INFINE;
}
void Dijkstra(AdjList& G, int ear, vector<int>& prev, vector<int>& dist){// 初始化// flag数组记录 某点是否纳入已找到点集合// prev数组记录 前驱顶点下标// dist数组记录 从源顶点ear 到 i顶点的最短路径vector<bool> flag (G. adjlist. size() + 1, false);for(int i = 1; i <= G. vexnum; i ++) dist[i] = getWeight(G, ear, i), prev[i] = ear;flag[ear] = true, prev[ear] = 0;// 开始for(int i = 2; i <= G. vexnum; i ++){int pos = 1; // 未纳入的距离最小的顶点int weiMin = INFINE;for(int j = 1; j <= G. vexnum; j ++){if(!flag[j] && dist[j] < weiMin){weiMin = dist[j], pos = j;}}flag[pos] = true;for(int j = 1; j <= G. vexnum; j ++){if(!flag[j]){ // 未纳入点集中, 找到pos到这些点的距离, 与dist数组比较是否更新int tmpWei = getWeight(G, pos, j);if(tmpWei != INFINE) tmpWei = tmpWei + weiMin; // 两点距离应该为ear -> pos -> jif(tmpWei < dist[j]) {dist[j] = tmpWei; // 距离更小则更新distprev[j] = pos; // 前顶点更新为pos}}}}
}
// 找路径
void pathDist(vector<int>& prev, vector<int>& dist, int ear){// prev数组中为1有2种情况(djikstra初始化过程的时候全赋值为1, 后续一直未改变):// 1: 从ear到 顶点 只有 ear -> 顶点 这一条路最短// 2: 无法从ear到达的顶点for(int i = 1; i <= prev. size() - 1; i ++){stack<int> trace;if(ear == i) continue;cout << ear << " 到 " << i ;// 无连通if(dist[i] == INFINE) {cout << "无连通" << endl;continue;}cout << "最短距离: " << dist[i] << " 最短路径: ";int tmp = i;while(tmp){ // 源顶点prev是0trace. push(tmp);tmp = prev[tmp];}// 开始出栈, 栈顶一定是ear源顶点cout << trace. top();trace. pop();while(!trace. empty()){cout << " -> " << trace. top();trace. pop();}cout << endl;}
}
int main(){AdjList G;createGraph(G);// prev数组记录 前驱顶点下标vector<int> prev (G. vexnum + 1, 0);// dist数组记录 从源顶点ear 到 i顶点的最短路径vector<int> dist (G. vexnum + 1, INFINE);// 从源点ear 出发, 到达其余所有点的最短路径cout << "输入源顶点ear: ";int ear;cin >> ear;Dijkstra(G, ear, prev, dist);pathDist(prev, dist, ear);return 0;
}
测试如下:

- P118习题5 小船过河问题
一群人划船过河,河边只有一条船,这条船可以容纳两个人,船过河后需要一人将船开回,以便所有人都可以过河,每个人过河速度不一样,两个人过河速度取决于慢的那个人,请问最少需要多久让所有人过河?
//
// Created by GiperHsiue on 2022/11/27.
//
// 小船过河问题
#include <iostream>
#include <vector>
using namespace std;
// 归并排序
void mergeSort(vector<int>& num, int l, int r){if(l >= r) return;int mid = l + (r - l) / 2;mergeSort(num, l, mid), mergeSort(num, mid + 1, r);int a = l, b = mid + 1, k = 0;vector<int> tmp (r - l + 1, 0);while(a <= mid && b <= r){if(num[a] <= num[b]) tmp[k++] = num[a++];else tmp[k++] = num[b++];}while(a <= mid) tmp[k++] = num[a++];while (b <= r) tmp[k++] = num[b++];for(int i = 0, j = l; j <= r; i ++, j ++) num[j] = tmp[i];
}
int calTime(vector<int>& num){int cnt = num. size(), res = 0;while(cnt > 3){int tmp1 = num + 2 * num + num[cnt - 1];int tmp2 = 2 * num + num[cnt - 1] + num[cnt - 2];res += min(tmp1, tmp2);cnt -= 2;}if(cnt == 2) res += num;if(cnt == 3) res += num + num + num;return res;
}
int main(){int n;cin >> n;vector<int> people(n, 0);for(auto &x: people) cin >> x;mergeSort(people, 0, n - 1);cout << "过河最少时间: " << calTime(people) << endl;return 0;
}
代码如下:
测试如下:

五、实验小结及思考
通过本次实验对于贪心算法有了进一步的认识与理解,并运用贪心思维解决实际问题,理解贪心算法的概念,掌握贪心算法的基本要素,掌握设计贪心算法的步骤和策略。
相关文章:
算法设计与分析实验报告-贪心算法
校课程的简单实验报告。 算法设计与分析实验报告-递归与分治策略 算法设计与分析实验报告-动态规划算法 算法设计与分析实验报告-贪心算法 dijkstra迪杰斯特拉算法(邻接表法) 算法设计与分析实验报告-回溯法 算法设计与分析实验报告-分支限界法 …...
Unity读取服务器声音文件
Unity读取服务器声音文件 功能1.在网站的根目录放置一个声音文件Alarm01.wav(这个是window系统自带的找不到这个格式的可以直接在C盘搜索)2.在WebManager.cs脚本中添加clipPath、audio、m_downloadClip属性和DownloadSound()函数&…...
掌握ElasticSearch(一):Elasticsearch安装与配置、Kibana安装
文章目录 〇、简介1.Elasticsearch简介2.典型业务场景3.数据采集工具4.名词解释 一、安装1.使用docker(1)创建虚拟网络(2)Elasticsearch安装步骤 2.使用压缩包 二、配置1.目录介绍2.配置文件介绍3.elasticsearch.yml节点配置4.jvm.options堆配置 二、可视化工具Kibana1.介绍2.安…...
《剑指offer》Java版--13.机器人的运动范围(BFS)
剑指offer原题13:机器人的运动范围 地上有一个m行n列的方格。一个机器人从坐标(0,0)的格子开始移动,它每次可以向左、右、上、下移动一格,但不能进入行坐标和列坐标的数位之和大于k的格子。例如,当k为18时,机器人能够进入方格(35,37),因为353…...
基于流程挖掘的保险理赔优化策略实践
引言 在当今日益竞争的商业环境中,保险公司面临着日益增长的业务量和客户期望的挑战。特别是在理赔领域,理赔是保险行业的重要环节,也是保险公司和客户之间最直接的联系点。然而,长周期和繁琐的理赔流程常常给保险公司和投保人带来困扰。因此,如何提供准确且高效的理赔处…...
Docker五 | DockerFile
目录 DockerFile 常用保留字 FROM MAINTAINER RUN EXPOSE WORKDIR USER ENV VOLUME ADD COPY CMD ENTRYPOINT DockerFile案例 前期准备 编写DockerFile文件 运行DockerFile 运行镜像 DockerFile是用来构建Docker镜像的文本文件,是由一条条构建…...
2023年度总结:技术旅程的杨帆远航⛵
文章目录 职业规划与心灵成长 ❤️🔥我的最大收获与成长 💪新年Flag 🚩我的技术发展规划 ⌛对技术行业的深度思考 🤔祝愿 🌇 2023 年对我来说是一个充实而令人难以忘怀的一年。这一年,我在CSDN上发表了 1…...
SpringBoot+AOP+Redis 防止重复请求提交
本文项目基于以下教程的代码版本: https://javaxbfs.blog.csdn.net/article/details/135224261 代码仓库: springboot一些案例的整合_1: springboot一些案例的整合 1、实现步骤 2.引入依赖 我们需要redis、aop的依赖。 <dependency><groupId>org.spr…...
偷流量、端口占用、网络负载高、socket创建释放异常等Android高阶TCP/IP网络问题定位思路
一,背景 通常一些偷流量、端口占用、网络负载高、socket创建释放异常等Android网络相关问题,可以通过使用tcpdump抓tcp/ip报文,来定位。但是tcpdump无进程信息,也没有APK包名信息,无法确认异常的报文来自哪些Apk或者n…...
《人人都能用英语》学习笔记
https://github.com/xiaolai/everyone-can-use-english 核心: 用 What──它究竟是什么?Why──为什么它是那个样子?How──要掌握它、应用它,必须得遵循什么样的步骤? 在运行程序之前,要反复浏览代码&a…...
NFC与ZigBee技术在智慧农业物联网监测系统中的应用
近年来,我国农业物联网技术飞速发展,基于物联网技术的智能农业监测系统有望得到较大规模的推广应用。但传统的物联网农业监测系统其网络结构层次单一,多采用基于有线或无线结构的节点-上位机数据采集模式,节点数据访问模式缺乏灵活…...
k8s-cni网络 10
Flannel vxlan模式跨主机通信原理 在同一个节点上的pod 流量通过cni网桥可以直接进行转发; 在需要跨主机访问时,数据包通过flannel(隧道) 知道另一边的mac地址,就可以拿到另一边的ip地址,然后构建常规的以太网数据包,…...
听GPT 讲Rust源代码--src/tools(27)
File: rust/src/tools/clippy/clippy_lints/src/methods/suspicious_to_owned.rs 文件rust/src/tools/clippy/clippy_lints/src/methods/suspicious_to_owned.rs的作用是实施Clippy lint规则,检测产生潜在性能问题的字符转换代码,并给出相关建议。 在Rus…...
经济危机下,我们普通人如何翻身?2024创业新风口,适合普通人的创业项目
明年的商业环境会比今年更残酷,不是贩卖危机。旅游行业还在刺激性消费,再过几个月大家就没钱了,估计慢慢也消停。中小微企业资金链断裂,大部分公司倒闭,大批人失业,所以经济恢复需要一个周期。 30年河东&am…...
深入浅出图解C#堆与栈 C# Heap(ing) VS Stack(ing) 第五节 引用类型复制问题及用克隆接口ICloneable修复
深入浅出图解C#堆与栈 C# Heaping VS Stacking 第五节 引用类型复制问题及用克隆接口ICloneable修复 [深入浅出图解C#堆与栈 C# Heap(ing) VS Stack(ing) 第一节 理解堆与栈](https://mp.csdn.net/mdeditor/101021023)[深入浅出图解C#堆与栈 C# Heap(ing) VS Stack(ing) 第二节…...
python中基本元素的pop函数
python中基本元素的pop函数 一、列表List二、元组Tuple三、字典dict四、集合set 一、列表List pop() 根据索引删除并返回被删除的元素,索引默认为-1 a [1, 2, 3, 2, 5] b a.pop() # b5,默认返回最后一个值 print(b) b a.pop(2) # b3,返回a[2] pri…...
MPLS动态协议LDP配置示例
一、预习: MPLS是一种根据报文中携带的标签来转发数据的技术,两台LSR必须在它们之间转的数据 的标签使用上“达成共识”。LSR之间可以运行LDP来告知其他LSR本设备上的标签绑定信息,从而实现标签报文的正确转发。 LSR:Label Switch…...
JS调用栈:为何会栈溢出
JS调用栈:为何会栈溢出 JS调用栈什么是函数调用什么是栈在开发中利用调用栈栈溢出 JS调用栈 JavaScript 经常会出现一个函数中调用另外一个函数的情况,调用栈就是用来管理函数调用关系的一种数据结构,首先你要先弄明白函数调用和栈结构 什么…...
代码随想Day52 | 300.最长递增子序列、674. 最长连续递增序列、718. 最长重复子数组
300.最长递增子序列 这道题目的重点在于动态数组的定义 dp[i]:以nums[i]为结尾的最长递增子序列,因为这样定义可以进行递推; 递推:j从0-i进行对比,如果nums[i]大于nums[j],dp[i]dp[j]1; 初始化…...
使用 pytest 相关特性重构 appium_helloworld
一、前置说明 在 pytest 基础讲解 章节,介绍了 pytest 的特性和基本用法,现在我们可以使用 pytest 的一些机制,来重构 appium_helloworld 。 appium_helloworld 链接: 编写第一个APP自动化脚本 appium_helloworld ,将脚本跑起来 代码目录结构: pytest.ini 设置: [pyt…...
Java 语言特性(面试系列1)
一、面向对象编程 1. 封装(Encapsulation) 定义:将数据(属性)和操作数据的方法绑定在一起,通过访问控制符(private、protected、public)隐藏内部实现细节。示例: public …...
Opencv中的addweighted函数
一.addweighted函数作用 addweighted()是OpenCV库中用于图像处理的函数,主要功能是将两个输入图像(尺寸和类型相同)按照指定的权重进行加权叠加(图像融合),并添加一个标量值&#x…...
鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院查看报告小程序
一、开发环境准备 工具安装: 下载安装DevEco Studio 4.0(支持HarmonyOS 5)配置HarmonyOS SDK 5.0确保Node.js版本≥14 项目初始化: ohpm init harmony/hospital-report-app 二、核心功能模块实现 1. 报告列表…...
CMake 从 GitHub 下载第三方库并使用
有时我们希望直接使用 GitHub 上的开源库,而不想手动下载、编译和安装。 可以利用 CMake 提供的 FetchContent 模块来实现自动下载、构建和链接第三方库。 FetchContent 命令官方文档✅ 示例代码 我们将以 fmt 这个流行的格式化库为例,演示如何: 使用 FetchContent 从 GitH…...
高防服务器能够抵御哪些网络攻击呢?
高防服务器作为一种有着高度防御能力的服务器,可以帮助网站应对分布式拒绝服务攻击,有效识别和清理一些恶意的网络流量,为用户提供安全且稳定的网络环境,那么,高防服务器一般都可以抵御哪些网络攻击呢?下面…...
【碎碎念】宝可梦 Mesh GO : 基于MESH网络的口袋妖怪 宝可梦GO游戏自组网系统
目录 游戏说明《宝可梦 Mesh GO》 —— 局域宝可梦探索Pokmon GO 类游戏核心理念应用场景Mesh 特性 宝可梦玩法融合设计游戏构想要素1. 地图探索(基于物理空间 广播范围)2. 野生宝可梦生成与广播3. 对战系统4. 道具与通信5. 延伸玩法 安全性设计 技术选…...
什么是Ansible Jinja2
理解 Ansible Jinja2 模板 Ansible 是一款功能强大的开源自动化工具,可让您无缝地管理和配置系统。Ansible 的一大亮点是它使用 Jinja2 模板,允许您根据变量数据动态生成文件、配置设置和脚本。本文将向您介绍 Ansible 中的 Jinja2 模板,并通…...
Linux --进程控制
本文从以下五个方面来初步认识进程控制: 目录 进程创建 进程终止 进程等待 进程替换 模拟实现一个微型shell 进程创建 在Linux系统中我们可以在一个进程使用系统调用fork()来创建子进程,创建出来的进程就是子进程,原来的进程为父进程。…...
OPENCV形态学基础之二腐蚀
一.腐蚀的原理 (图1) 数学表达式:dst(x,y) erode(src(x,y)) min(x,y)src(xx,yy) 腐蚀也是图像形态学的基本功能之一,腐蚀跟膨胀属于反向操作,膨胀是把图像图像变大,而腐蚀就是把图像变小。腐蚀后的图像变小变暗淡。 腐蚀…...
JVM虚拟机:内存结构、垃圾回收、性能优化
1、JVM虚拟机的简介 Java 虚拟机(Java Virtual Machine 简称:JVM)是运行所有 Java 程序的抽象计算机,是 Java 语言的运行环境,实现了 Java 程序的跨平台特性。JVM 屏蔽了与具体操作系统平台相关的信息,使得 Java 程序只需生成在 JVM 上运行的目标代码(字节码),就可以…...

