欧几里得算法实验报告.doc

《欧几里得算法实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法设计与分析基础上机实验报告应用数学学院二零一六年六月实验一欧几里得算法一、实验性质设计二、实验学时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

2、,n//输出：m,n的最大公约数whilen≠0dor←mmodnm←nn←rreturnm2、算法程序代码：importjava.io.IOException;importjava.io.InputStream;importjava.util.Scanner;publicclassE{publicstaticvoidmain(String[]args){System.out.println("请输入两个不全为0的非负整数");Scannerm1=newScanner(System.in);try{intm=m1.nextInt();intn=m1

3、.nextInt();intr=0;while(n!=0){r=m%n;m=n;n=r;}System.out.println("m,n的最大公约数为："+m);}catch(ExceptionE){}}}3、运行结果（截图）图（1）图（2）4、算法分析：每经过一次循环，参加运算的两个算子中的后一个都会变得更小，而且绝对不会变成负数。最终第二个算子的值最终会变成0，此时，算法终止。