欧几里得算法
2021/4/22 20:28:41
本文主要是介绍欧几里得算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
拓展欧几里得算法:
1. 概述:
不仅能求出两个正整数m和n的最大公因数d,还能求出两个整数x和y(不一定为正)使得mx+ny=d
2. 分析:
这个其实挺简单的步骤如下:
- 我们假设m是d的a倍;n是d的b倍,而a和b我们是可以通过求最大公因数d来求出来的
- 原式可以化为:ax+by=1;
- 这就是一个简单的一次方程了,我们可以得到方程的无穷多种解;
- 对于给定的x。y=(1-ax)/ b。
- 这种情况给出的是一般解,我们要给出整个方程的通解
- 这个一个非齐次方程,通解等于对应齐次方程的通解+自身的一个特解
最后得
x=x0+b*t
y=y0- a*t
3. Java实现如下:
GCF gcf = new GCF(); public String findResult(int a,int b){ int g = gcf.FindGCF(a,b); int k1,k2; k1=a/g; k2=b/g; return "y=(1 - "+k1+"x) / "+k2; }
- 这里只对一般解进行求值。具体求通解。并不难,自己实现~
GCF类的代码
public class GCF { /** * @Mehtods:递归方法实现找最大公因数 * */ public int reFindGCD(int a,int b){ if(b==0){ return a; }else{ return reFindGCD(b,a%b); } } /** * @Methods:非递归找最大公因数,辗转相除法 * */ public int FindGCF(int a,int b){ int min=Math.min(a,b); int max=Math.max(a,b); while(max%min!=0){ int temp=max%min; max=min; min=temp; } return min; } /** * @Methods:找最小公倍数,辗转相除法 * */ public int FindLCM(int a,int b){ int gcf=FindGCF(a,b); int k=1; while((gcf*k)%a!=0||(gcf*k)%b!=0){ k++; } return gcf*k; } }
这篇关于欧几里得算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-01为什么公共事业机构会偏爱 TiDB :TiDB 数据库在某省妇幼健康管理系统的应用
- 2024-04-26敏捷开发:想要快速交付就必须舍弃产品质量?
- 2024-04-26静态代码分析的这些好处,我竟然都不知道?
- 2024-04-26你在测试金字塔的哪一层?(下)
- 2024-04-26快刀斩乱麻,DevOps让代码评审也自动起来
- 2024-04-262024年最好用的10款ER图神器!
- 2024-04-2203-为啥大模型LLM还没能完全替代你?
- 2024-04-2101-大语言模型发展
- 2024-04-17基于SpringWeb MultipartFile文件上传、下载功能
- 2024-04-14个人开发者,Spring Boot 项目如何部署