算法设计与分析基础
上机实验报告
应用数学学院
二零一六年六月
实验一 欧几里得算法
一、实验性质 设计
二、实验学时 14学时
三、实验目的1、掌握欧几里得算法。
2、掌握编程语言实现算法的一般流程。
四、实验要求
1、用java语言编写出欧几里得算法。
2、计算两个数的最大公约数。
五、实验内容
1、如果n=0，返回m的值作为结果，同时过程结束；否则，进入第二步。
2、m除以n，将余数赋给r。
3、将n的值赋给m，将r的值赋给n，返回第一步。
六、实验报告
1、伪代码（课本中第3页）：
算法 Euclid（m, n）
//使用欧几里得算法计算gcd(m, n)
//输入：两个不全为0的非负整数m, n
//输出：m, n的最大公约数
while n ≠ 0 do
r ← m mod n
m ← n
n ← r
return m
2、算法程序代码：
import java.io.IOException;
import java.io.InputStream;
import java.util.Scanner;
public class E {
public static void main(String[] args) {
System.out.println("请输入两个不全为0的非负整数");
Scanner m1 = new Scanner(System.in);
try {
int m = m1.nextInt();
int n = m1.nextInt();
int r = 0;
while (n != 0) {
r = m % n;
m = n;
n = r;
}
System.out.println("m,n的最大公约数为："+m);
} catch (Exception E) { }
}
}
3、运行结果（截图）
图（1）
图（2）
4、算法分析：
每经过一次循环，参加运算的两个算子中的后一个都会变得更小，而且绝对不会变成负数。最终第二个算子的值最终会变成0，此时，算法终止。