数学矩阵GCD和lCM(详解)

2024-04-06 09:20
文章标签 详解 数学 矩阵 gcd lcm

本文主要是介绍数学矩阵GCD和lCM(详解),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

矩阵乘法

知阵乘法是《线性代数》中的基础内容,但在考察数学的算法题中也会出现。
本节我们学习基础的矩阵乘法规则。
每个矩阵会有一个行数和一个列数,只有当相乘的两个矩阵的左矩阵的列数等于右矩阵的行数
时,才能相乘,否则不允许做矩阵乘法。
例如,3x5的矩阵可以和5x7的矩阵做乘法,但是3x5的阵不能和4x7的矩阵做乘法N*M的知阵利M*K的矩阵做乘法后的矩阵大小为N*K
矩阵乘法的规则用一句话描述就是,第一个矩阵A的第i行和第二个矩阵B的第i列的各M个元素对应相乘再相加得到新矩阵C[i][j]的值

 例题

矩阵相乘

题目描述

小明最近刚刚学习了矩阵乘法,但是他计算的速度太慢,于是他希望你能帮他写一个矩阵乘法的运算器。

输入描述

输入的第一行包含三个正整数 N,M,K,表示一个 $NM的矩阵乘以一个的矩阵乘以一个MK的矩阵。接下来N行,每行M个整数,表示第一个矩阵。再接下来的M行,每行K$ 个整数,表示第二个矩阵。

0<<N,M,K≤100, 0≤ 矩阵中的每个数 ≤1000

输出描述

输出有 N 行,每行 K 个整数,表示矩阵乘法的结果。

输入输出样例

示例

输入

2 1 3
1
2
1 2 3

输出

1 2 3
2 4 6
package shuxeu;
import java.util.*;
public class juzhen {public static void main(String[] args) {// TODO Auto-generated method stubScanner scan=new Scanner(System.in);int m=scan.nextInt();int n=scan.nextInt();int k=scan.nextInt();int [][]a=new int[m][n];int [][]p=new int[n][k];for(int i=0;i<m;i++) {for(int j=0;j<n;j++) {a[i][j]=scan.nextInt();}}for(int i=0;i<n;i++) {for(int j=0;j<k;j++) {p[n][k]=scan.nextInt();}}int[][]sum=new int[m][k];for(int i=0;i<m;i++) {for(int j=0;j<k;j++) {for(int c=0;c<n;c++) {sum[i][j]+=a[i][c]*p[c][j];		}System.out.println(sum[i][j]);}System.out.println("");}}}

 整除

在计算机中,整数之间的除法往往是整除且向下取整的

同余 

同余是数论中非常重要的概念,意思是两个或多个数字x,对于一个模数M的余数是相等的
或者说在模M意义下,他们是相等的。
例如当M=7,x=[1,8,15,8,50]是同余的,这些x有一个共同的关系,就是x%M=1。

GCD和LCM

GCD( Greatest Common Divisor) 是最大公约数,LCM(Least Common Multiple) 是最小公倍数。大多数情况下,我们更关注GCD如果题口和LCM有关,也通常会转换成和GCD相关的。
gcd通过欧几里得辗转相除法得到,同样,初次学习不必过于深究其原理,学会使用最重要lcm通过gcd(x,y)*lcm(x,y)=x*y来得到。

gcd欧几里得辗转相除法

public int gcd(int a,int b){

        return b==0?a:gcd(b,a%b);

}

简单地理解一下,首先不妨设a<b,有gcd(a,b)=gcd(a,b-a)=gcd(a,b-2a)...=gcd(a,b%a),又有
b%a<a,于是将他们两个调换位置,继续向下递归,直到b变为0,gcd(x,0)=x。

LCM求解方法

public int lcm(int a,int b){

        return a/gcd(a,b)*m;

}

推荐先做除法,再做乘法,避免溢出。

例题

最大公约数

题目描述

给定两个正整数A,B,求它们的最大公约数。

输入描述

第 1 行为一个整数 T,表示测试数据数量。

接下来的 T 行每行包含两个正整数 A,B。

1≤T≤10^5,1≤A,B≤10^9。

输出描述

输出共 T 行,每行包含一个整数,表示答案。

输入输出样例

示例 1

输入

5
2 4
3 7
5 10
6 8
7 9

输出

2
1
5
2
1
package gcd;
import java.util.*;
public class chapter1 {public static void main(String[] args) {// TODO Auto-generated method stubScanner scan=new Scanner(System.in);long T=scan.nextLong();while(T-->0) {long A=scan.nextLong();long B=scan.nextLong();long sum=gcd(A,B);System.out.println(sum);}}private static long gcd(long a, long b) {// TODO Auto-generated method stubreturn b==0?a:gcd(b,a%b);}}

这篇关于数学矩阵GCD和lCM(详解)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/879570

相关文章

一文深入详解Python的secrets模块

《一文深入详解Python的secrets模块》在构建涉及用户身份认证、权限管理、加密通信等系统时,开发者最不能忽视的一个问题就是“安全性”,Python在3.6版本中引入了专门面向安全用途的secr... 目录引言一、背景与动机:为什么需要 secrets 模块?二、secrets 模块的核心功能1. 基

一文详解MySQL如何设置自动备份任务

《一文详解MySQL如何设置自动备份任务》设置自动备份任务可以确保你的数据库定期备份,防止数据丢失,下面我们就来详细介绍一下如何使用Bash脚本和Cron任务在Linux系统上设置MySQL数据库的自... 目录1. 编写备份脚本1.1 创建并编辑备份脚本1.2 给予脚本执行权限2. 设置 Cron 任务2

一文详解如何在idea中快速搭建一个Spring Boot项目

《一文详解如何在idea中快速搭建一个SpringBoot项目》IntelliJIDEA作为Java开发者的‌首选IDE‌,深度集成SpringBoot支持,可一键生成项目骨架、智能配置依赖,这篇文... 目录前言1、创建项目名称2、勾选需要的依赖3、在setting中检查maven4、编写数据源5、开启热

Python常用命令提示符使用方法详解

《Python常用命令提示符使用方法详解》在学习python的过程中,我们需要用到命令提示符(CMD)进行环境的配置,:本文主要介绍Python常用命令提示符使用方法的相关资料,文中通过代码介绍的... 目录一、python环境基础命令【Windows】1、检查Python是否安装2、 查看Python的安

HTML5 搜索框Search Box详解

《HTML5搜索框SearchBox详解》HTML5的搜索框是一个强大的工具,能够有效提升用户体验,通过结合自动补全功能和适当的样式,可以创建出既美观又实用的搜索界面,这篇文章给大家介绍HTML5... html5 搜索框(Search Box)详解搜索框是一个用于输入查询内容的控件,通常用于网站或应用程

Python中使用uv创建环境及原理举例详解

《Python中使用uv创建环境及原理举例详解》uv是Astral团队开发的高性能Python工具,整合包管理、虚拟环境、Python版本控制等功能,:本文主要介绍Python中使用uv创建环境及... 目录一、uv工具简介核心特点:二、安装uv1. 通过pip安装2. 通过脚本安装验证安装:配置镜像源(可

C++ 函数 strftime 和时间格式示例详解

《C++函数strftime和时间格式示例详解》strftime是C/C++标准库中用于格式化日期和时间的函数,定义在ctime头文件中,它将tm结构体中的时间信息转换为指定格式的字符串,是处理... 目录C++ 函数 strftipythonme 详解一、函数原型二、功能描述三、格式字符串说明四、返回值五

LiteFlow轻量级工作流引擎使用示例详解

《LiteFlow轻量级工作流引擎使用示例详解》:本文主要介绍LiteFlow是一个灵活、简洁且轻量的工作流引擎,适合用于中小型项目和微服务架构中的流程编排,本文给大家介绍LiteFlow轻量级工... 目录1. LiteFlow 主要特点2. 工作流定义方式3. LiteFlow 流程示例4. LiteF

CSS3中的字体及相关属性详解

《CSS3中的字体及相关属性详解》:本文主要介绍了CSS3中的字体及相关属性,详细内容请阅读本文,希望能对你有所帮助... 字体网页字体的三个来源:用户机器上安装的字体,放心使用。保存在第三方网站上的字体,例如Typekit和Google,可以link标签链接到你的页面上。保存在你自己Web服务器上的字

MySQL存储过程之循环遍历查询的结果集详解

《MySQL存储过程之循环遍历查询的结果集详解》:本文主要介绍MySQL存储过程之循环遍历查询的结果集,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录前言1. 表结构2. 存储过程3. 关于存储过程的SQL补充总结前言近来碰到这样一个问题:在生产上导入的数据发现