算法分析与设计求最大公约数问题实验报告

《算法分析与设计求最大公约数问题实验报告》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法设计与分析实验报告书实验名称：算法设计与分析之实验一------求两个数的最大公约数学号：2012210890姓名：王朔评语：成绩：指导教师：批阅时间：年月日《算法分析与设计》实验报告-6-一实验目的和要求（1）复习上课所讲的内容；（2）掌握并应用算法的数学分析和后验分析方法；（3）理解这样一个观点：不同的算法能够解决相同的问题，这些算法的解题思路不同，复杂程度不同，解题效率也不同。（4）至少设计出三个版本的求最大公约数算法；  （5）上机实现算法，并用测算三种算法的运行时间；（6）通过分析对比

2、，得出自己的结论。二实验内容设计三种算法求两个自然数m和n的最大公约数,并分析每种算法运行所需时间.三实验环境PCWin7系统,VISUALC++6.0四设计思想及实验步骤1.欧几里得辗转相除算法：①输入两个正整数m,n(m>n)；②求出两个数的最大值Max和最小值Min；③计算Max除以Min所得的余数r；④Max=Min,Min=r；⑤若r＝0,则m,n的最大公约数等于Max；否则转到②；⑥输出最大公约数Max。2.蛮力法算法：①输入两个正整数m，n；②令常量factor=1;循环变量i从2~m

3、in(m,n);③如果i是m和n的公因子,则执行④;④factor=factor*i;m=m/i;n=n/i;⑤如果i不是m和n的公因子，则i=i+1;《算法分析与设计》实验报告-6-⑥输出factor；3.欧几里得减法算法：①输入两个正整数a,b；②求出两个数的最大值Max和最小值Min；③若Max等于Min,转到⑥；④把Max-Min的差赋予r;⑤如果Min>r,那么把Min赋给Max,把r赋给Min;否则把r赋给Max，执行③；⑥输出最大公约数Min。测试三种算法，在例举数的范围内产生随机数，

4、且在每个范围内运行1000次，求出所需总时间，最后输出计算每种算法平均执行一次所需的时间。六核心源代码//2012210890王朔.cpp:Definestheentrypointfortheconsoleapplication.//#include"stdafx.h"#include"stdio.h"#include"stdlib.h"#include"time.h"#include"windows.h"intCommFactor1(intm,intn);intCommFactor2(intm,i

5、ntn);intCommFactor3(intm,intn);《算法分析与设计》实验报告-6-intmain(intargc,char*argv[]){inta[10]={10000,20000,40000,80000,100000,200000,500000,1000000,2000000,4000000};LARGE_INTEGERBegainTime;LARGE_INTEGEREndTime;LARGE_INTEGERFrequency;QueryPerformanceFrequency(&F

6、requency);QueryPerformanceCounter(&BegainTime);srand((unsigned)time(NULL));for(inti=0;i<10;i++){for(intj=0;j<1000;j=j+1){doublek=(rand()*0.1);longm=(long)(a[i]+k);k=(0.1*rand());longn=(long)(a[i]-k);CommFactor1(m,n);}}QueryPerformanceCounter(&EndTime);

7、printf("算法一总耗时:%.10f秒",(double)(EndTime.QuadPart-BegainTime.QuadPart)/(Frequency.QuadPart*10000));《算法分析与设计》实验报告-6-system("pause");return0;}intCommFactor1(intm,intn){intc=m%n;while(c!=0){m=n;n=c;c=m%n;}returnn;}intCommFactor2(intm,intn){inti,factor=1;

8、for(i=2;i<=m&&i<=n;i++){while(m%i==0&&n%i==0){factor=factor*i;m=m/i;n=n/i;}}returnfactor;}《算法分析与设计》实验报告-6-intCommFactor3(intm,intn){inti,r;if(n>m){i=m;m=n;n=i;}r=m%n;while(r!=0){m=m-n;if(n>m){i=m;m=n;n=i;}r=m%n;}returnn;}七实验结果及分析三种算法算法运