当前位置: 首页 > 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…...

【Oracle APEX开发小技巧12】

有如下需求&#xff1a; 有一个问题反馈页面&#xff0c;要实现在apex页面展示能直观看到反馈时间超过7天未处理的数据&#xff0c;方便管理员及时处理反馈。 我的方法&#xff1a;直接将逻辑写在SQL中&#xff0c;这样可以直接在页面展示 完整代码&#xff1a; SELECTSF.FE…...

(二)TensorRT-LLM | 模型导出(v0.20.0rc3)

0. 概述 上一节 对安装和使用有个基本介绍。根据这个 issue 的描述&#xff0c;后续 TensorRT-LLM 团队可能更专注于更新和维护 pytorch backend。但 tensorrt backend 作为先前一直开发的工作&#xff0c;其中包含了大量可以学习的地方。本文主要看看它导出模型的部分&#x…...

1688商品列表API与其他数据源的对接思路

将1688商品列表API与其他数据源对接时&#xff0c;需结合业务场景设计数据流转链路&#xff0c;重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点&#xff1a; 一、核心对接场景与目标 商品数据同步 场景&#xff1a;将1688商品信息…...

Matlab | matlab常用命令总结

常用命令 一、 基础操作与环境二、 矩阵与数组操作(核心)三、 绘图与可视化四、 编程与控制流五、 符号计算 (Symbolic Math Toolbox)六、 文件与数据 I/O七、 常用函数类别重要提示这是一份 MATLAB 常用命令和功能的总结,涵盖了基础操作、矩阵运算、绘图、编程和文件处理等…...

Axios请求超时重发机制

Axios 超时重新请求实现方案 在 Axios 中实现超时重新请求可以通过以下几种方式&#xff1a; 1. 使用拦截器实现自动重试 import axios from axios;// 创建axios实例 const instance axios.create();// 设置超时时间 instance.defaults.timeout 5000;// 最大重试次数 cons…...

关于 WASM:1. WASM 基础原理

一、WASM 简介 1.1 WebAssembly 是什么&#xff1f; WebAssembly&#xff08;WASM&#xff09; 是一种能在现代浏览器中高效运行的二进制指令格式&#xff0c;它不是传统的编程语言&#xff0c;而是一种 低级字节码格式&#xff0c;可由高级语言&#xff08;如 C、C、Rust&am…...

使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台

🎯 使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台 📌 项目背景 随着大语言模型(LLM)的广泛应用,开发者常面临多个挑战: 各大模型(OpenAI、Claude、Gemini、Ollama)接口风格不统一;缺乏一个统一平台进行模型调用与测试;本地模型 Ollama 的集成与前…...

MySQL 知识小结(一)

一、my.cnf配置详解 我们知道安装MySQL有两种方式来安装咱们的MySQL数据库&#xff0c;分别是二进制安装编译数据库或者使用三方yum来进行安装,第三方yum的安装相对于二进制压缩包的安装更快捷&#xff0c;但是文件存放起来数据比较冗余&#xff0c;用二进制能够更好管理咱们M…...

Python+ZeroMQ实战:智能车辆状态监控与模拟模式自动切换

目录 关键点 技术实现1 技术实现2 摘要&#xff1a; 本文将介绍如何利用Python和ZeroMQ消息队列构建一个智能车辆状态监控系统。系统能够根据时间策略自动切换驾驶模式&#xff08;自动驾驶、人工驾驶、远程驾驶、主动安全&#xff09;&#xff0c;并通过实时消息推送更新车…...

宇树科技,改名了!

提到国内具身智能和机器人领域的代表企业&#xff0c;那宇树科技&#xff08;Unitree&#xff09;必须名列其榜。 最近&#xff0c;宇树科技的一项新变动消息在业界引发了不少关注和讨论&#xff0c;即&#xff1a; 宇树向其合作伙伴发布了一封公司名称变更函称&#xff0c;因…...