java欧几里得算法代码 欧几里得算法 递归

欧几里得算法减法伪代码

欧几里得算法减法伪代码如下:

创新互联建站服务项目包括镇巴网站建设、镇巴网站制作、镇巴网页制作以及镇巴网络营销策划等。多年来,我们专注于互联网行业,利用自身积累的技术优势、行业经验、深度合作伙伴关系等,向广大中小型企业、政府机构等提供互联网行业的解决方案,镇巴网站推广取得了明显的社会效益与经济效益。目前,我们服务的客户以成都为中心已经辐射到镇巴省份的部分城市,未来相信会继续扩大服务区域并继续获得客户的支持与信任!

1.将被减数赋给大整数A, 减数赋给B

2.判断A和B大小:如果A B,跳到第3步,A B,交换A和B的值,并跳到第3步

3.循环执行以下步骤,直到B=0:

a. 将A的最高位与B的最高位比较,如果A的最高位大于B的最高位,则A = A - B,否则A = A + B

b. 把A的最高位移除并把A的位数减1

c. 把B的最高位移除并把B的位数减1

4. 返回A的值

关于欧几里得算法,主要是看不懂。请高手指点迷津。。。。

1、 欧几里德算法:给定两个正整数m和n,求他们的最大公因子,即能够同时整除m和n的最大的正整数。

E1:【求余数】以n除m并令r为所得余数(我们将有0=rn)。

E2:【余数为0?】若r=0,算法结束;n即为答案。

E3:【互换】置mßn,nßr,并返回步骤E1.

证明:

我们将两个正整数m和n的最大公因子表示为:t = gcd(m,n);

重复应用等式:gcd(m,n)= gcd(n,m mod n)直到m mod n 等于0;

m可以表示成m = kn + r;则 r = m mod n , 假设 d是 m 和 n的一个公约数,则有:

d|m 和 d|m 而 r =m – kn ,因此 d|r ,因此 d 是 (n,m mod n) 的公约数;假设 d 是 (n,m mod n) 的公约数,

则 d|n ,d|r ,但是 m=kn+r ,因此 d 也是 (a,b) 的公约数;因此 (a,b) 和

(b,a mod b) 的公约数是一样的,其最大公约数也必然相等,得证。

具体步骤描述如下:

第一步:如果 n=0 ,返回 m 的值作为结果,同时过程结束;否则,进入第二步。

第二步:用 n 去除 m ,将余数赋给 r 。

第三步:将 n 的值赋给 m,将 r的值赋给 n,返回第一步。

伪代码描述如下:

Euclid(m,n)

// 使用欧几里得算法计算gcd(m,n)

// 输入:两个不全为0的非负整数m,n

// 输出:m,n的最大公约数

while n≠0 do

r ← m mod n

m ← n

n ← r

注:(a,b) 是 a,b的最大公因数

(a,b)|c 是指 a,b的最大公因数 可以被c整除。

java实现:

package algorithm;

import java.io.BufferedReader;

import java.io.IOException;

import java.io.InputStreamReader;

public class GreatestCommonDivisor {

int a,b,temp = 0;

public static void main(String args[]) throws IOException {

GreatestCommonDivisor gcd = new GreatestCommonDivisor();

gcd.readNum();

gcd.MaxNum();

System.out.print(gcd.a+"和"+gcd.b+"的最大公约数是:");

while (gcd.b != 0) {

gcd.temp = gcd.b;

gcd.b = gcd.a % gcd.b;

gcd.a = gcd.temp;

}

System.out.println(gcd.temp);

}

//输入两个正整数,中间用空格分开.

public void readNum() throws IOException{

BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));

String str = buf.readLine();

for(int i = 0;istr.length();i++){

if(str.charAt(i)==' ' temp == 0){

a = Integer.parseInt(str.substring(temp,i));

temp = i;

b = Integer.parseInt(str.substring(temp+1,str.length()));

break;

}

}

}

public void MaxNum(){

if (a b) {

temp = b;

b = a;

a = temp;

}

}

}

java编程:用欧几里德辗转相除法求两个正整数的最大公约数

public class test {  

public static void main(String[] args) {  

// TODO Auto-generated method stub  

int res = gcd(8, 6);  

System.out.println(res);  

}  

private static int gcd(int i, int j) {  

int m, n, r;  

// 使mn  

if (i  j) {  

m = i;  

n = j;  

} else {  

m = j;  

n = i;  

}  

// 通过辗转除来求的最大公约数  

r = m % n;  

while (r != 0) {  

m = n;  

n = r;  

r = m % n;  

}  

// 返回最大公约数  

return n;  

}  

}


网站题目:java欧几里得算法代码 欧几里得算法 递归
网页链接:http://pwwzsj.com/article/ddjdhei.html