在网站上做播放视频广告是否违法,flash网站开发用什么语言,建设网站沙井,做类似3d溜溜的网站题目1 最大连续乘积子串 题目描述给一个浮点数序列#xff0c;取最大乘积连续子串的值#xff0c;例如 -2.5#xff0c;4#xff0c;0#xff0c;3#xff0c;0.5#xff0c;8#xff0c;-1#xff0c;则取出的最大乘积连续子串为3#xff0c;0.5#xff0c;8。也就…题目1 最大连续乘积子串 题目描述给一个浮点数序列取最大乘积连续子串的值例如 -2.54030.58-1则取出的最大乘积连续子串为30.58。也就是说上述数组中3 0.5 8这3个数的乘积30.5812是最大的而且是连续的。考虑到乘积子序列中有正有负也还可能有0我们可以把问题简化成这样数组中找一个子序列使得它的乘积最大同时找一个子序列使得它的乘积最小负数的情况。因为虽然我们只要一个最大积但由于负数的存在我们同时找这两个乘积做起来反而方便。也就是说不但记录最大乘积也要记录最小乘积。假设数组为a[]直接利用动态规划来求解考虑到可能存在负数的情况我们用maxend来表示以a[i]结尾的最大连续子串的乘积值用minend表示以a[i]结尾的最小的子串的乘积值那么状态转移方程为maxend max(max(maxend * a[i], minend * a[i]), a[i]);minend min(min(maxend * a[i], minend * a[i]), a[i]);初始状态为maxend minend a[0]。参考代码如下 double MaxProductSubString(double *a, int num){double MaxEnd a[0];double MinEnd a[0];double MaxResult a[0];for(int i 0; i num; i){double end1 MaxEnd * a[i], end2 MinEnd * a[i];MaxEnd max(max(end1, end2), a[i]);MinEnd min(min(end1, end2), a[i]);MaxResult max(MaxResult, MaxEnd);}return MaxResult;}// 动态规划求解的方法一个for循环搞定所以时间复杂度为O(n)。搜索算法中的老祖宗深度和广度优先搜索算法。
广度优先BFS Breadth-First Search搜索 这个用形象的比喻就像是地震波从起点向外辐射直到找到目标点。我们在实现的时候一般采用队列来实现。广搜是一层一层往外遍历寻找最短路径其策略是采取队列的方法。这个算法的优点1、简单。代码也就几十行2、路径能找到最优解不足1、算法消耗的时间比较大遍历的点会很多。广度优先搜索之所以能找到最优的路径原因就是每一次扩展的点都是距离出发点最近、步骤最少的。如此这样递推当扩展到目标点的时候也是距离出发点最近的。这样的路径自然形成了最短的路线。深度优先DFS Depth-First Search搜索 用俗话说就是不见棺材不回头。算法会朝一个方向(目标位置)进发直到遇到边界或者障碍物才改变方向。一般在实现的时候我们采用递归的方式来进行也可以采用模拟压栈的方式来实现。这个算法的好处就是实现简单可能就十几行代码。不过问题也很明显就是1、路径可能不是最优解2、寻路时间比较长。数据结构----BFS和DFS详解 c代码
A*算法 广度优先 启发式搜索 考虑距出发点距离 距目标点距离 正是由于广度优先搜索一层层的扩展虽然让他找到了最优的路线但是他却很傻的走完了绝大多数格子才找到我们的目标点。也就是他只关注了当前扩展点和出发点的关系而忽略了当前点和目标点的距离。如果如果如果……我们每扩展一个点就踮起脚尖看看诗和远方找找我们要寻找的那个目标是不是就有可能指引我们快速的去往正确的方向而不用傻乎乎的一层层的发展了呢答案是肯定的。A*算法相对广度优先搜索算法除了考虑中间某个点同出发点的距离以外还考虑了这个点同目标点的距离。这就是A*算法比广度优先算法智能的地方。也就是所谓的启发式搜索。如果用f(M)表示从起点S到终点E经过M点的距离那他就可以表示成为两段距离之和,M为中间策略点 即S→M的距离 M→E的距离。如果我们用符号表示的话就可以写成f(M) g(M) h(M)。 我们扩展到M点的时候S→M的距离就已经知道所以g(M)是已知的。但是M到E的距离我们还不知道。如果我们能用某种公式能大概预测一下这个距离而这个预测的值又比较精确我们是不是就能很精确的知道每一个即将扩展的点是否是最优的解路径上的点呢 估算函数h(M)如何计算 常见的距离计算公式有这么几种1、曼哈顿距离这个名字听起来好高端说白了就是上面我们讲的横向格子数纵向格子数(折线段距离)2、欧式距离这个名字听起来也很高端说白了就是两点间的直线距离sqrt((x1-x2)^2 (y1-y2)^2)3、欧式距离平方 (x1-x2)^2 (y1-y2)^2除了上述的距离计算公式以外还有一些变种的距离计算公式如对角线距离等等。这个就在具体的问题中做具体的优化了。 不同估算函数对于结果的影响 1、当估算的距离h完全等于实际距离h时也就是每次扩展的那个点我们都准确的知道如果选他以后我们的路径距离是多少这样我们就不用乱选了每次都选最小的那个一路下去肯定就是最优的解而且基本不用扩展其他的点。2、如果估算距离h小于实际距离h时我们到最后一定能找到一条最短路径(如果存在另外一条更短的评估路径就会选择更小的那个)但是有可能会经过很多无效的点。曼哈顿距离\欧式距离极端情况当h0的时候最终的距离函数就变成f(M)g(M)h(M) f(M)g(M)0 f(M)g(M)这不就是我们的广度优先搜索算法嘛 他只考虑和起始点的距离关系毫无启发而言。 3、如果估算距离h大于实际距离h时有可能就很快找到一条通往目的地的路径但是却不一定是最优的解。这种情况就是h值大于等于实际距离的明显他扩展的点很少不过找到的路径却不是最短路径。欧式距离平方Dijkstra(迪杰斯特拉)算法
算法特点 迪科斯彻算法使用了 广度优先搜索 BFS 解决 赋权的有向图 或者 无向图的 单源最短路径问题算法最终得到一个最短路径树。 该算法常用于路由算法或者作为其他图算法的一个子模块。
算法的思路 Dijkstra算法采用的是一种贪心的策略声明一个数组dis来保存源点s 到各个顶点m 的最短距离 和一个保存已经找到了最短路径的顶点的集合T初始时原点s 的路径权重被赋为 0 dis[s] 0。若对于顶点 s 存在能直接到达的边(s,m) 另一个顶点为m则把dis[m]设为w(s, m)即单个路径边上的权重值,同时把所有其他s不能直接到达的顶点的路径长度设为无穷大。初始时短路集合T 只有 顶点s。 然后从dis数组选择最小值则该值就是 源点s 到该值对应的顶点 m 的最短路径并且把该点加入到 短路集合T中OK此时完成一个顶点 然后我们需要看看新加入的顶点是否可以到达其他顶点并且看看通过该顶点到达其他点的路径长度是否比源点直接到达短如果是那么就替换这些顶点在dis中的值。 然后又从dis中找出最小值重复上述动作直到T中包含了图的所有顶点。示例: 顶点数 边数6 8起点 终点 权重值1 3 101 5 301 6 1002 3 53 4 504 6 105 4 205 6 60图的邻接矩阵为∞ ∞ 10 ∞ 30 100 v1节点直接到达其他节点的距离∞ ∞ 5 ∞ ∞ ∞∞ ∞ ∞ 50 ∞ ∞∞ ∞ ∞ ∞ ∞ 10 ...∞ ∞ ∞ 20 ∞ 60∞ ∞ ∞ ∞ ∞ ∞ v6节点直接到达其他节点的距离新建dis 向量(从v1到达各个点 经过的最短距离)dis {0, ∞, 10, ∞, 30, 100}解法步骤1v1 到 v3 路径最短 dis[2] 10, 下标从0开始 除去dis[0]外最小的 为dis[2] 到第三个顶点 v3v3可以到达v4v1-v3-v4 距离为 10 50 60而从v1直接到v4v1-v4距离为无穷大dis[3] 60dis {0, ∞, 10, 60, 30, 100}因此 dis[3]要更新为 60。这个过程有个专业术语叫做“松弛”。即 v1顶点到 v4顶点的路程即 dis[3]通过 v3,v4 这条边松弛成功。这便是 Dijkstra 算法的主要思想通过“边”来松弛v1顶点到其余各个顶点的路程。步骤2我们从除去 dis[0] 、 dis[2]中选择最小的 为 dis[4] 30 到第五个顶点 v5v5 可以到达 v4, v1-v5-v4 距离为 30 20 50而从v1-v4为 60 50 ,则 dis[3] 被更新为 50另外 v5 也可以到达 v6,而v1 - v5 - v6 30 60 90而从v1 - v6 为 100则dis[5] 被更为 90dis {0, ∞, 10, 50, 30, 90}步骤3我们再从 除去 dis[0] 、 dis[2]、 dis[4] 中选择最小的为 dis[3] 50 到第四个顶点 v4而v4 可以到达 v6v1 - v4 - v6 距离为 50 10 60而v1 - v6 90 60 则dis[5] 被更新为 60dis {0, ∞, 10, 50, 30, 60}步骤4然后从除去 dis[0] 、 dis[2]、 dis[4]、dis[3] 中选取最小的为 dis[5] 60 到第六个顶点 v4而 v6 到达不了其他地方更新不了Dijkstra算法的代码实现c Dijkstra.h 头文件的代码 // Dijkstra.h#pragma once//#pragma once是一个比较常用的C/C杂注//只要在头文件的最开始加入这条杂注//就能够保证头文件只被编译一次。#includeiostream#includestringusing namespace std;/*本程序是使用Dijkstra算法实现求解最短路径的问题采用的邻接矩阵来存储图*///记录起点到每个顶点的最短路径的信息struct Dis {string path;//字符串路径 int value; //最短路径值bool visit; //已经找到最短路径的标记 Dis() { //结构体初始化函数visit false; value 0; path “”; } }; // 自定义类的声明 class Graph_DG { private:// 私有变量 int vexnum; //图的顶点个数 v1v2…v6 int edge; //图的边数 int **arc; //邻接矩阵 二维数组 指针的指针 Dis * dis; //记录各个顶点最短路径的信息 public://共有函数方法 Graph_DG(int vexnum, int edge); // 默认构造函数 与类同名~Graph_DG(); // 销毁时自动执行的析构函数 构造函数前 ~//顶点从1开始编号 而权重必须大于0 bool check_edge_value(int start, int end, int weight); // 判断我们每次输入的的边的权重信息是否合法void createGraph(); //创建图void print(); //打印邻接矩阵void Dijkstra(int begin); //求最短路径void print_path(int); //打印最短路径};Dijkstra.cpp 源文件的代码 // Dijkstra.cpp 源文件的代码 #includeDijkstra.h// 包含声明 头文件 //默认构造函数Graph_DG::Graph_DG(int vexnum, int edge) {//初始化顶点数和边数this-vexnum vexnum;this-edge edge;//为邻接矩阵开辟空间和赋初值arc new int*[this-vexnum];// 指针数组 顶点数 * 顶点数的 二维数组dis new Dis[this-vexnum]; // 最短路径 向量for (int i 0; i this-vexnum; i) {arc[i] new int[this-vexnum];// 行数组for (int k 0; k this-vexnum; k) {arc[i][k] INT_MAX; //邻接矩阵初始化为无穷大}}}//析构函数Graph_DG::~Graph_DG() {delete[] dis;// delete[] 删除 最短路径 变量 数组for (int i 0; i this-vexnum; i) {delete this-arc[i];// 删除邻接矩阵 每一行的数组}delete arc; // 删除邻接矩阵 数组}// 判断我们每次输入的的边的信息是否合法 权重必须大于0 //顶点从1开始编号bool Graph_DG::check_edge_value(int start, int end, int weight) {if (start1 || end1 || startvexnum || endvexnum || weight 0) {return false;}return true;}//创建初始邻接图 根据输入信息void Graph_DG::createGraph() {cout 请输入每条边的起点和终点顶点编号从1开始以及其权重 endl;int start;int end;int weight;int count 0;// 输入边数记录while (count ! this-edge) {// 0~edge-1cin start end weight;// 得到 起点终点 对应权重//首先判断边的信息是否合法while (!this-check_edge_value(start, end, weight)) {cout 输入的边的信息不合法请重新输入 endl;cin start end weight;}//对邻接矩阵对应上的点赋值arc[start - 1][end - 1] weight;//无向图添加上这行代码//arc[end - 1][start - 1] weight;count;}}// 打印邻接矩阵void Graph_DG::print() {cout 图的邻接矩阵为 endl;int count_row 0; //打印行的标签int count_col 0; //打印列的标签//开始打印while (count_row ! this-vexnum) {count_col 0;while (count_col ! this-vexnum) {if (arc[count_row][count_col] INT_MAX)cout ∞ ;elsecout arc[count_row][count_col] ;count_col;// 列 下标}cout endl;count_row;// 行 下标}}// Dijkstra 求最短路径void Graph_DG::Dijkstra(int begin){//【1】首先初始化我们的dis数组int i;for (i 0; i this-vexnum; i) {//设置当前的路径dis[i].path v to_string(begin) --v to_string(i 1);dis[i].value arc[begin - 1][i];// v11 v12 v13 v14 v15 v16的值}//设置起点到起点的路径为0dis[begin - 1].value 0;dis[begin - 1].visit true;int count 1;//计算剩余的顶点的最短路径 剩余this-vexnum-1个顶点while (count ! this-vexnum) {// 【2】找到 dis数组内的最小路径值// temp用于保存当前dis数组中最小的那个下标// min记录的当前的最小值int temp0;// int min INT_MAX;for (i 0; i this-vexnum; i) {if (!dis[i].visit dis[i].value min) {min dis[i].value;// 最小值temp i;// 最小下标}}//cout temp 1 min endl;//把temp对应的顶点加入到已经找到的最短路径的集合中dis[temp].visit true;// 找到标志count;// 遍历该节点for (i 0; i this-vexnum; i) {//注意这里的条件arc[temp][i]!INT_MAX必须加不然会出现溢出从而造成程序异常if (!dis[i].visit arc[temp][i] !INT_MAX (dis[temp].value arc[temp][i]) dis[i].value) {//如果新得到的边可以影响其他为访问的顶点那就就更新它的最短路径和长度 v1-v4-v5 v1-v5 更新dis[i].value dis[temp].value arc[temp][i];dis[i].path dis[temp].path --v to_string(i 1);// 记录路径}}}}//打印最短路径void Graph_DG::print_path(int begin) {string str;str v to_string(begin);cout 以 str 为起点的图的最短路径为 endl;for (int i 0; i ! this-vexnum; i) {if(dis[i].value ! INT_MAX)cout dis[i].path dis[i].value endl;else {cout dis[i].path 是无最短路径的. endl;}}}
