数学矩阵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

相关文章

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

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

MyBatis ResultMap 的基本用法示例详解

《MyBatisResultMap的基本用法示例详解》在MyBatis中,resultMap用于定义数据库查询结果到Java对象属性的映射关系,本文给大家介绍MyBatisResultMap的基本... 目录MyBATis 中的 resultMap1. resultMap 的基本语法2. 简单的 resul

从基础到进阶详解Pandas时间数据处理指南

《从基础到进阶详解Pandas时间数据处理指南》Pandas构建了完整的时间数据处理生态,核心由四个基础类构成,Timestamp,DatetimeIndex,Period和Timedelta,下面我... 目录1. 时间数据类型与基础操作1.1 核心时间对象体系1.2 时间数据生成技巧2. 时间索引与数据

Mybatis Plus Join使用方法示例详解

《MybatisPlusJoin使用方法示例详解》:本文主要介绍MybatisPlusJoin使用方法示例详解,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,... 目录1、pom文件2、yaml配置文件3、分页插件4、示例代码:5、测试代码6、和PageHelper结合6

一文全面详解Python变量作用域

《一文全面详解Python变量作用域》变量作用域是Python中非常重要的概念,它决定了在哪里可以访问变量,下面我将用通俗易懂的方式,结合代码示例和图表,带你全面了解Python变量作用域,需要的朋友... 目录一、什么是变量作用域?二、python的四种作用域作用域查找顺序图示三、各作用域详解1. 局部作

Java SWT库详解与安装指南(最新推荐)

《JavaSWT库详解与安装指南(最新推荐)》:本文主要介绍JavaSWT库详解与安装指南,在本章中,我们介绍了如何下载、安装SWTJAR包,并详述了在Eclipse以及命令行环境中配置Java... 目录1. Java SWT类库概述2. SWT与AWT和Swing的区别2.1 历史背景与设计理念2.1.

C++作用域和标识符查找规则详解

《C++作用域和标识符查找规则详解》在C++中,作用域(Scope)和标识符查找(IdentifierLookup)是理解代码行为的重要概念,本文将详细介绍这些规则,并通过实例来说明它们的工作原理,需... 目录作用域标识符查找规则1. 普通查找(Ordinary Lookup)2. 限定查找(Qualif

SpringBoot 中 CommandLineRunner的作用示例详解

《SpringBoot中CommandLineRunner的作用示例详解》SpringBoot提供的一种简单的实现方案就是添加一个model并实现CommandLineRunner接口,实现功能的... 目录1、CommandLineRunnerSpringBoot中CommandLineRunner的作用

Java死锁问题解决方案及示例详解

《Java死锁问题解决方案及示例详解》死锁是指两个或多个线程因争夺资源而相互等待,导致所有线程都无法继续执行的一种状态,本文给大家详细介绍了Java死锁问题解决方案详解及实践样例,需要的朋友可以参考下... 目录1、简述死锁的四个必要条件:2、死锁示例代码3、如何检测死锁?3.1 使用 jstack3.2

详解Linux中常见环境变量的特点与设置

《详解Linux中常见环境变量的特点与设置》环境变量是操作系统和用户设置的一些动态键值对,为运行的程序提供配置信息,理解环境变量对于系统管理、软件开发都很重要,下面小编就为大家详细介绍一下吧... 目录前言一、环境变量的概念二、常见的环境变量三、环境变量特点及其相关指令3.1 环境变量的全局性3.2、环境变