当前位置: 首页 > news >正文

Monge矩阵

Monge矩阵

对一个m*n的实数矩阵A,如果对所有i,j,k和l,1≤ i<k ≤ m和1≤ j<l ≤ n,有          A[i,j]+A[k,l] ≤ A[i,l]+A[k,j]   那么,此矩阵A为Monge矩阵。

换句话说,每当我们从矩阵中挑出两行与两列,并且考虑行列交叉处的4个元素,左上角与右下角的和小于或等于左下角与右上角元素的和。

例如,下面这个就是一个Monge矩阵

(1)证明一个矩阵为Monge阵,当且仅当对所有i=1,2,...,m-1和j=1,2,...,n-1,有            A[i,j]+A[i+1,j+1] ≤ A[i,j+1]+A[i+1,j]

(提示:在当部分,对行、列分别使用归纳法。)

(2)下面的矩阵不是Monge阵。改变一个元素,把它变成Monge矩阵

             37       23       22      32

             21        6       27      10

             53       34       30      31

             32       13        9       6

             43       21       15       8

很明显是要改27,27可以改成【2,5】内的任何一个实数

(3)假设f(i)是第i行包含最左端最小值的列的索引值。证明对任何的m x n Monge矩阵,有f(1) ≤ f(2) ≤...≤ f(m)。

(4)下面是一个用来计算m x n 的Monge矩阵A中每一行的最左最小值的分治算法的描述:

   构造一个包含所有A的偶数行的子矩阵A'。递归地计算A'中每一行的最左端最小值。然后计算A中奇数行的最左端最小值。

   解释如何能在O(m+n)时间内计算出A的奇数行的最左端最小值?(在偶数行最左最小值已知的情况下)

解释:看下面的代码就很明显了。

其实这个算法,我个人感觉,就结构而言比较像分治,但是就思想而言比较像动态规划。

(5)写出(4)所描述算法的运行时间的递归式,并证明其解为O(m+nlogm)

T(m)=T(m/2)+ O(m+n)(求解略)

我的代码:
 

#include<iostream>
using namespace std;void calculate(double **A, int r1, int r2, int min, int max, int *f)	//计算f(r1)到f(r2)
{if (r1 > r2)return;int r = (r1 + r2) / 2;int result = min;int flag = A[r][min];for (int i = min + 1; i <= max; i++)	//寻找最左最小元素flag,和它的的下标result{if (A[r][i] < flag){flag = A[r][i];result = i;}}f[r] = result;calculate(A, r1, r - 1, min, result, f);calculate(A, r + 1, r2, result, max, f);
}bool isMonge(double **A, int m, int n)	//判断是否是Monge矩阵
{for (int i = 0; i < m - 1; i++)for (int j = 0; j < n - 1; j++)if (A[i][j] + A[i + 1][j + 1]>A[i + 1][j] + A[i][j + 1])return false;return true;
}
int main()
{int m, n;while (cin >> m >> n && m>1 && n > 1){double **A = new double*[m];		//Monge矩阵int *f = new int[m];	//不需要在主函数里面进行初始化,这个工作由calculate函数完成for (int i = 0; i < m; i++){A[i] = new double[n];for (int j = 0; j < n; j++)cin >> A[i][j];}if (isMonge(A, m, n)){cout << "这个是Monge矩阵" << endl;calculate(A, 0, m - 1, 0, n - 1, f);for (int i = 0; i < m; i++)cout << "第" << i << "行的最左最小元素的列下标是" << f[i] << endl;}else cout << "这个不是Monge矩阵";}return 0;
}

相关文章:

Monge矩阵

Monge矩阵 对一个m*n的实数矩阵A&#xff0c;如果对所有i&#xff0c;j&#xff0c;k和l&#xff0c;1≤ i<k ≤ m和1≤ j<l ≤ n&#xff0c;有 A[i,j]A[k,l] ≤ A[i,l]A[k,j] 那么&#xff0c;此矩阵A为Monge矩阵。 换句话说&#xff0c;每当我们从矩阵中挑…...

(5)所有角色数据分析页面的构建-5

所有角色数据分析页面&#xff0c;包括一个时间轴柱状图、六个散点图、六个柱状图(每个属性角色的生命值/防御力/攻击力的max与min的对比)。 """绘图""" from pyecharts.charts import Timeline from find_type import FindType import pandas …...

专利进阶(三):专利撰写资料汇总

文章目录 一、前言二、资料汇总三、拓展阅读 一、前言 在专利撰写前&#xff0c;需要首先了解专利撰写所需遵守的基本规则。可以借助的撰写工具是什么。文献检索在哪里&#xff1f;注意事项是什么&#xff1f;本篇博文会就以上问题进行逐一解答。 专利撰写基本原则&#xff1…...

maven编译始终提示无效的目标发行版的解决方法

摘自个人印象笔记2021-05-07&#xff1a;https://app.yinxiang.com/fx/55e1d5f4-aeea-446a-a768-0f1a48195f5b(图显示不完整可查看原笔记内容)1&#xff1a;确保IDE中的编译版本正确 在idea中&#xff0c;主要看项目属性中和setting的java compiler中对应的jdk版本是否正确&…...

系统架构设计高级技能 · 软件可靠性分析与设计(三)【系统架构设计师】

系列文章目录 系统架构设计高级技能 软件架构概念、架构风格、ABSD、架构复用、DSSA&#xff08;一&#xff09;【系统架构设计师】 系统架构设计高级技能 系统质量属性与架构评估&#xff08;二&#xff09;【系统架构设计师】 系统架构设计高级技能 软件可靠性分析与设计…...

界面控件DevExpress WPF Chart组件——拥有超快的数据可视化库!

DevExpress WPF Chart组件拥有超大的可视化数据集&#xff0c;并提供交互式仪表板与高性能WPF图表库。DevExpress Charts提供了全面的2D / 3D图形集合&#xff0c;包括数十个UI定制和数据分析/数据挖掘选项。 PS&#xff1a;DevExpress WPF拥有120个控件和库&#xff0c;将帮助…...

【网络安全】等保测评安全物理环境

【网络安全】等保测评&安全物理环境 前言第1章 安全物理环境1.1 物理位置选择1.2 物理访问控制&#xff08;高风险项&#xff09;1.3 防盗窃1.4 防雷击1.5 防火1.6 防水防潮1.7 防静电1.8 温湿度控制1.9 电力供应1.10 电磁防护 前言 等级保护对象是由计算机或其他信息终端…...

Intellij IDEA 导入 eclipse web 项目详细操作

Eclipse当中的web项目都会有这两个文件。但是idea当中应该是没有的&#xff0c;所以导入会出现兼容问题。但是本篇文章会教大家如何导入&#xff0c;并且导入过后还能使用tomcat运行。文章尽可能以图片的形式进行演示。我的idea使用的版本是2022.3.3版本。当然按正常来说版本之…...

安卓java A应用切换到B应用,来回切换不执行OnCreate

需求&#xff1a;安卓java如何做到A应用切换到B应用&#xff0c;如果B应用没启动就启动&#xff0c;如果B应用已经启动就仅仅切换到B应用。B应用再切换回A应用&#xff0c;不要重复执行OnCreate! 在 A 应用中的&#xff1a; 在 A 应用中&#xff0c;如果你希望在切换回 B 应用…...

【Linux】批量恢复文件权限

批量恢复文件权限 Linux 中&#xff0c;如果意外误操作将根目录目录权限批量设置&#xff0c;比如 chmod -R 777 / &#xff0c;系统中的大部分服务以及命令将无法使用&#xff0c;这时候可以通过系统自带的 getfacl 命令来拷贝和还原系统权限&#xff0c;若是其他系统目录被误…...

数据可视化(八)堆叠图,双y轴,热力图

1.双y轴绘制 #双Y轴可视化数据分析图表 #add_subplot() dfpd.read_excel(mrbook.xlsx) x[i for i in range(1,7)] y1df[销量] y2df[rate] #用来正常显示负号 plt.rcParams[axes.unicode_minus]False figplt.figure() ax1fig.add_subplot(1,1,1)#一行一列&#xff0c;第一个区域…...

前台自动化测试:基于敏捷测试驱动开发(TDD)的自动化测试原理

一、自动化测试概述 自动化测试主要应用到查询结果的自动化比较&#xff0c;把借助自动化把相同的数据库数据的相同查询条件查询到的结果同理想的数据进行自动化比较或者同已经保障的数据进行不同版本的自动化比较&#xff0c;减轻人为的重复验证测试。多用户并发操作需要自动…...

基于SLAM的规划算法仿真复现|SLAM|智能规划

图片来自百度百科 前言 那么这里博主先安利一些干货满满的专栏了&#xff01; 首先是博主的高质量博客的汇总&#xff0c;这个专栏里面的博客&#xff0c;都是博主最最用心写的一部分&#xff0c;干货满满&#xff0c;希望对大家有帮助。 高质量博客汇总https://blog.csdn.n…...

sqlite3多线程操作问题

在项目中使用sqlite3&#xff0c;有时会报database is locked 两种方式 1、多线程读&#xff0c;多线程写&#xff0c;只使用共同一个数据库连接&#xff0c;即使用同一个SQLiteHelper连接&#xff0c;调用sqlite3_busy_timeout 2、多线程读&#xff0c;单线程写&#xff0c;每…...

ACCESS数据库增删改查

[添加COM组件] A: Microsoft ADO Ext. 2.8 for DDL and Security B: Microsoft ActiveX Data Objects 2.8 Library [添加头文件]using System.Data.OleDb; using System.Data; using ADOX; using System.IO; using System; using System.Collections.Generic; using System.L…...

动捕系统mockup_optitrack替换为VRPN传递信息

motive&#xff1a;启动→载入已有→layout选择capture→view选择data streming→复选marker右键create刚体→rename刚体→修改local interface为本机ip→勾选vrpn ROS端&#xff1a;roslaunch vrpn_client_ros vrpn_efy.launch 记得修改server地址为motiveip地址 关掉motive…...

【服务平台】Rancher运行和管理Docker和Kubernetes,提供管理生产中的容器所需的整个软件堆栈

Rancher是一个开源软件平台&#xff0c;使组织能够在生产中运行和管理Docker和Kubernetes。使用Rancher&#xff0c;组织不再需要使用一套独特的开源技术从头开始构建容器服务平台。Rancher提供了管理生产中的容器所需的整个软件堆栈。  完整软件堆栈 Rancher是供采用容器的团…...

二叉树的完全性检验

给定一个二叉树的 root &#xff0c;确定它是否是一个 完全二叉树 。 在一个 完全二叉树 中&#xff0c;除了最后一个关卡外&#xff0c;所有关卡都是完全被填满的&#xff0c;并且最后一个关卡中的所有节点都是尽可能靠左的。它可以包含 1 到 2h 节点之间的最后一级 h 。 示…...

激活函数总结(六):ReLU系列激活函数补充(RReLU、CELU、ReLU6)

激活函数总结&#xff08;六&#xff09;&#xff1a;ReLU系列激活函数补充 1 引言2 激活函数2.1 RReLU激活函数2.2 CELU激活函数2.3 ReLU6 激活函数 3. 总结 1 引言 在前面的文章中已经介绍了介绍了一系列激活函数 (Sigmoid、Tanh、ReLU、Leaky ReLU、PReLU、Swish、ELU、SEL…...

tp5中的事务处理

使用事务首先要数据库支持事务&#xff1b; 如下MySQL数据库user表开启事务支持&#xff0c;即设计表->引擎设置为InnoDB->保存 事务处理 1. 数据库的表引擎需要是 InnoDB 才可以使用&#xff0c;如果不是调整即可&#xff1b; 2. 事务处理&#xff0c;需要执行多个 SQ…...

RestClient

什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端&#xff0c;它允许HTTP与Elasticsearch 集群通信&#xff0c;而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级&#xff…...

测试微信模版消息推送

进入“开发接口管理”--“公众平台测试账号”&#xff0c;无需申请公众账号、可在测试账号中体验并测试微信公众平台所有高级接口。 获取access_token: 自定义模版消息&#xff1a; 关注测试号&#xff1a;扫二维码关注测试号。 发送模版消息&#xff1a; import requests da…...

相机Camera日志实例分析之二:相机Camx【专业模式开启直方图拍照】单帧流程日志详解

【关注我&#xff0c;后续持续新增专题博文&#xff0c;谢谢&#xff01;&#xff01;&#xff01;】 上一篇我们讲了&#xff1a; 这一篇我们开始讲&#xff1a; 目录 一、场景操作步骤 二、日志基础关键字分级如下 三、场景日志如下&#xff1a; 一、场景操作步骤 操作步…...

渗透实战PortSwigger靶场-XSS Lab 14:大多数标签和属性被阻止

<script>标签被拦截 我们需要把全部可用的 tag 和 event 进行暴力破解 XSS cheat sheet&#xff1a; https://portswigger.net/web-security/cross-site-scripting/cheat-sheet 通过爆破发现body可以用 再把全部 events 放进去爆破 这些 event 全部可用 <body onres…...

ardupilot 开发环境eclipse 中import 缺少C++

目录 文章目录 目录摘要1.修复过程摘要 本节主要解决ardupilot 开发环境eclipse 中import 缺少C++,无法导入ardupilot代码,会引起查看不方便的问题。如下图所示 1.修复过程 0.安装ubuntu 软件中自带的eclipse 1.打开eclipse—Help—install new software 2.在 Work with中…...

大数据学习(132)-HIve数据分析

​​​​&#x1f34b;&#x1f34b;大数据学习&#x1f34b;&#x1f34b; &#x1f525;系列专栏&#xff1a; &#x1f451;哲学语录: 用力所能及&#xff0c;改变世界。 &#x1f496;如果觉得博主的文章还不错的话&#xff0c;请点赞&#x1f44d;收藏⭐️留言&#x1f4…...

【无标题】路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论

路径问题的革命性重构&#xff1a;基于二维拓扑收缩色动力学模型的零点隧穿理论 一、传统路径模型的根本缺陷 在经典正方形路径问题中&#xff08;图1&#xff09;&#xff1a; mermaid graph LR A((A)) --- B((B)) B --- C((C)) C --- D((D)) D --- A A -.- C[无直接路径] B -…...

纯 Java 项目(非 SpringBoot)集成 Mybatis-Plus 和 Mybatis-Plus-Join

纯 Java 项目&#xff08;非 SpringBoot&#xff09;集成 Mybatis-Plus 和 Mybatis-Plus-Join 1、依赖1.1、依赖版本1.2、pom.xml 2、代码2.1、SqlSession 构造器2.2、MybatisPlus代码生成器2.3、获取 config.yml 配置2.3.1、config.yml2.3.2、项目配置类 2.4、ftl 模板2.4.1、…...

C# 表达式和运算符(求值顺序)

求值顺序 表达式可以由许多嵌套的子表达式构成。子表达式的求值顺序可以使表达式的最终值发生 变化。 例如&#xff0c;已知表达式3*52&#xff0c;依照子表达式的求值顺序&#xff0c;有两种可能的结果&#xff0c;如图9-3所示。 如果乘法先执行&#xff0c;结果是17。如果5…...

Scrapy-Redis分布式爬虫架构的可扩展性与容错性增强:基于微服务与容器化的解决方案

在大数据时代&#xff0c;海量数据的采集与处理成为企业和研究机构获取信息的关键环节。Scrapy-Redis作为一种经典的分布式爬虫架构&#xff0c;在处理大规模数据抓取任务时展现出强大的能力。然而&#xff0c;随着业务规模的不断扩大和数据抓取需求的日益复杂&#xff0c;传统…...