《算法分析与设计求最大公约数问题实验报告》由会员分享，可在线阅读，更多相关《算法分析与设计求最大公约数问题实验报告（8页珍藏版）》请在金锄头文库上搜索。
1、算法设计与分析实验报告书实验名称： 算法设计与分析之实验一 - 求两个数的最大公约数 学 号： 姓 名： 王朔 评语：成绩： 指导教师： 批阅时间： 年 月 日农村精神文明建设是新农村建设的重要任务，是全面建设小康社会的重要内容。根据市文明委相关文件精神要求，现就在全镇范围内深入开展以“乡风文明”和“村容整洁”为主题的“四创”活动several group number, then with b a, =c,c is is methyl b two vertical box between of accurate size. Per-23 measurement, such as procee
2、ds of c values are equal and equal to the design value, then the vertical installation accurate. For example a, b, and c valueswhile on horizontal vertical errors for measurement, General in iron angle code bit at measurement level points grid errors, specific method is from baseline to methyl verti
3、cal box center line distance for a, to b vertical box distance for b, list can measured算法分析与设计实验报告 - 5 - 一 实验目的和要求（1） 复习上课所讲的内容；（2） 掌握并应用算法的数学分析和后验分析方法；（3） 理解这样一个观点：不同的算法能够解决相同的问题，这些算法的解题思路不同，复杂程度不同，解题效率也不同。（4） 至少设计出三个版本的求最大公约数算法；（5） 上机实现算法，并用测算三种算法的运行时间；（6） 通过分析对比，得出自己的结论。 二 实验内容 设计三种算法求两个自然数 m 和 n
4、 的最大公约数,并分析每种算法运行所需时间.三 实验环境 PCWin7系统 , VISUALC+6.0 四 设计思想及实验步骤 1.欧几里得辗转相除算法：输入两个正整数m,n(mn)；求出两个数的最大值Max和最小值Min；计算Max除以Min所得的余数r；Max=Min,Min=r；若r0,则m,n的最大公约数等于Max；否则转到；输出最大公约数Max。2.蛮力法算法：输入两个正整数m，n；令常量factor = 1;循环变量i从2min(m,n);如果i是m和n的公因子,则执行; factor = factor*i; m = m/i; n = n/i;如果i不是m和n的公因子，则i = i
5、 +1;输出factor；3.欧几里得减法算法：输入两个正整数a,b；求出两个数的最大值Max和最小值Min；若Max等于Min,转到；把Max-Min的差赋予r;如果Minr,那么把Min赋给Max,把r赋给Min;否则把r赋给Max，执行；输出最大公约数Min。测试三种算法，在例举数的范围内产生随机数，且在每个范围内运行1000次，求出所需总时间，最后输出计算每种算法平均执行一次所需的时间。六 核心源代码/ 王朔.cpp : Defines the entry point for the console application./#include stdafx.h#include stdi
6、o.h#include stdlib.h#include time.h#include windows.hint CommFactor1(int m,int n);int CommFactor2(int m,int n);int CommFactor3(int m,int n);int main(int argc, char* argv) int a10 = 10000,20000,40000,80000,; LARGE_INTEGER BegainTime; LARGE_INTEGER EndTime; LARGE_INTEGER Frequency; QueryPerformanceFre
7、quency(&Frequency); QueryPerformanceCounter(&BegainTime); srand(unsigned)time(NULL); for(int i=0;i10;i+) for(int j=0;j1000;j=j+1) double k = (rand()*0.1); long m = (long)(ai+k); k = (0.1*rand(); long n = (long)(ai-k);CommFactor1(m,n); QueryPerformanceCounter(&EndTime); printf(算法一总耗时: %.10f 秒n,(doubl
8、e)(EndTime.QuadPart-BegainTime.QuadPart)/(Frequency.QuadPart*10000); system(pause); return 0;int CommFactor1(int m, int n) int c = m%n;while(c!=0)m = n;n = c;c= m%n;return n;int CommFactor2(int m, int n) int i, factor = 1; for(i = 2; i= m & im)i = m;m = n;n = i;r = m%n; while (r!=0) m = m-n; if(nm)
9、i = m; m = n; n = i; r = m%n; return n;七 实验结果及分析 三种算法 算法运行时间欧几里得辗转相除法时间（ms）蛮力法时间（ms）欧几里得减法时间（ms）平均使用时间（ms）0. 3. 0. 八 实验体会（包括本实验中遇到的问题、具体的解决方法、还没有解决的问题、实验收获等） 此次实验初步了解了算法分析，三种算法虽然结果相同但是效率却不同。对于复杂度的求解，可以根据我的结果分析得到欧几里得辗转相除算法的是最优算法，欧几里得减法其次，最复杂的是蛮力法。 在实验中，对于使用产生随机数测试算法的问题有了新的认识和了解，并学会了使用时间测试函数.从这次实验中，我复习了C语言代码，同时也通过算法分析用三种方法求解出了最大公约数这个问题。从这个试验的结果我了解到了算法的优与劣的差别，虽然得到的是同样的结果，但是需要的时间和资源却相差很大，这提示我们在以后写算法的时候要找出最优算法。可见算法分析与设计课程的对计编程的人来说是多么的重要，在以后写程序过程中要时刻提醒自己找最优算法，当然得先学会O(n)的分析。在以后的学习中我要学会多实践、多分析，在不停的改正错误中提高自己。
