昆明理工大学 算法 实验一 求最大公约数

} finish=clock(); usetime= finish-start; printf(\方法三用时%.f*10^(-6) 豪秒\\n\ }

五、实验过程原始记录( 测试数据、图表、计算等)

1.连续整数检测

2.欧几里得算法

3.分解质因数

4.计数法和计时法分别测算算法的运行时间 -9-

六、实验结果、分析和结论（误差分析与数据处理、成果总结等。其中，绘制曲线图时必须用计算纸或程序运行结果、改进、收获）

第一种，连续整数检测法。根据代买考虑最坏情况他们的最大公约数是1，循环做了t-1次，最好情况是只做一次，所以O(n)=n/2。

第二种，欧几里得算法。根据代码辗转相除得到欧几里得的O(n)=log n。 第三种，分解质因数法。根据代码分解质成因子算法O(n)=n^2+n/2。

结果分析：从前面的复杂度O(n)的出欧几里得算法的是最优算法，连续整除法其次，最复杂的是分解质因数算法，再从代码运行的计数器和计算的时间来看结果恰好和前面的复杂度得到的结果一致，所以的出结论：欧几里得算法最优。

通过对三种计算最大公约数方法的比较，了解了算法设计的初步概念，并对求公约数问题有了更深的认识。了解到了算法的优与劣的差别，虽然得到的是同样的结果，但是需要的时间和资源却相差很大，这提示我们在以后写算法的时候要找出最优算法。也告诉了我们，算法对于一个程序的重要性，我们要对这门课产生足够的重视。

注：教师必须按照上述各项内容严格要求，认真批改和评定学生成绩。

-10-