「欧几里得Java」欧几里得算法

博主：adminadmin 2022-12-29 16:18:11 650

本篇文章给大家谈谈欧几里得Java，以及欧几里得算法对应的知识点，希望对各位有所帮助，不要忘了收藏本站喔。

本文目录一览：

一道Java编程题

class  WangTi2

{

public static void main(String[] args) 

{   

long start = System.currentTimeMillis();//看一下要运行多长时间

shuanShu();

long end = System.currentTimeMillis();//看一下要运行多长时间

System.out.println("用时"+(end-start));

}

public static void shuanShu()

{

int[] arr = new int[100];

arr[0] = 1;

for(int x=0;x11213;x++)  //可以把11213改成100验证方法的正确性

{   //2^20=1048576 

int z = 0; 

/*

这个循环是记录乘2的结果

*/

for(int y =0;yarr.length;y++)

{

arr[y] = arr[y]1;

arr[y] = arr[y] + z;

if (arr[y]9)

{

arr[y] -= 10;

if(y!=arr.length-1)

z = 1;

}

else z = 0;

}

}

arr[0]--; //这个给最后一个位减1，这个值不会是负数。

System.out.println("这个数的最后100位是：");

for(int x=arr.length-1;x=0;x--)

{

System.out.print(arr[x]);

if(x%3==0x!=0)

System.out.print(",");

}

System.out.println();

}

}

思路是有的。定义数组，只存储最后100位。然后不停的乘2，大于9的向上一个数组加1。重复11213次。再把第一个数组减1。这样做是可以的。效率很低。求高人解答。。呵呵。

Java初级编程问题！！！

第一题答案

public class Hello{

public static void main(String args[]){

for(int i=9;++i10001;)

if((""+i).equals(new StringBuffer(""+i).reverse()+""))

System.out.print(i+" ");

}}

第二题答案

public class Hello{

public static void main(String args[]){

String s="";

for(int n=10,i=n;--i=0;

System.out.printf("%"+n+"s\b%s\n",s))s+="*";

}}

java 计算最小公倍数的问题

汗,这是欧几里得算法求最大公约数..

int r=m%n;

while(r!=0)

{ m=n;

n=r;

r=m%n;

}

这是欧几里得算法的实现...

欧几里德算法又称辗转相除法，用于计算两个整数a，b的最大公约数。其计算原理依赖于下面的定理：

定理：gcd(a,b) = gcd(b,a mod b)

证明：a可以表示成a = kb + r，则r = a mod b

假设d是a,b的一个公约数，则有

d|a, d|b，而r = a - kb，因此d|r

因此d是(b,a mod b)的公约数

假设d 是(b,a mod b)的公约数，则

d | b ， d |r ，但是a = kb +r

因此d也是(a,b)的公约数

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

java 密码学 扩展欧几里得

估计没有什么人会解释你的问题的。做加密运算本身就是需要很复杂的计算的。

我曾阅读过md5加密算法的程序，那可是3X3X3的矩阵运算。是真要用到大学的线性代数的，而且其运算还比较复杂。加密的狠麻烦的。

java代码如何实现a^-1(mod b)？

（1）用循环一个个试

（2）要快一点，试试用扩展欧几里得算法（就是利用辗转相除找最大公因数，算法过程中记录一些东西，就知道是否有逆，有逆直接可求出来），

密码学书上均有，你也可在网上找

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

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和欧几里得算法的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。

标签：