参证材料--算法设计实验标准版11112.doc

四 川 理 工 学 院课 程 设 计 书 学院 理学院 专业 信息与计算科学09级2班 题目 求最大公约数 学生 杨雪娥 09071030238 谭 芸 09071030236 杨玉俊 09071030224 甄 坤 09071030231 杨宏飞 09071030223 王 晨 09071030217 吕俊村 09071030215 实验项目求最大公约数一、 实验题目键盘输入两个任意的自然数m和n，编出一种方案求出m和n的最大公约数二、 实验目的（1） 复习数据结构课程的相关知识，实现课程间的平滑过渡；（2） 掌握并应用算法的数学分析和后验分析方法；（3）理解这样一个观点：不同的算法能够解决相同的问题，这些算法的解题思路不同，复杂程度不同，解题效率不同。三、 实验要求( 1 ) 至少设计出3个版本的求最大公约数的算法；( 2 ) 对所设计的算法采用大O符号进行时间复杂性分析；( 3 ) 上机实现算法，并用计数法和计时法分别测算算法的运行时间；( 4 ) 通过分析对比，得出自己的结论。四、问题分析设m和n是两个自然数，m和n的最大公约数记为gcd(m,n),是能够同时被m和n整除的最大整数。对此问题我们采取三种方案进行求解：1.第一种方案（1）连续整数检测伪代码：1. t=minm,n;2. m除以t，如果余数为0，则执行步骤3，否则，执行第四步；3. n除以t，如果余数为0，返回t的值作为结果，否则，执行第四步；4. t=t-1,转第四步；例如，要计算gcd(66,12)，首先令t=12，因为66除以12余数不为0，将t减1，而12除以11余数不为0，再将t减1，重复上述过程，直到t=6，此时12除以6的余数为0并且66除以6的余数为0，则gcd(66,12)=6。2.第二种方案（1）欧几里得算法伪代码：1. r=m%n；2. 循环直到r=0；2.1 m=n；2.2 n=r;2.3 r=m%n；3. 输出 n；例如，要计算gcd(66,12)，因为66除以12的余数为6，再将12除以6，余数为0，则gcd(66,12)=6。3.第三种方案（1）分解质因数伪代码1. 将m分解质因数；2. 将n分解质因数；3. 提取m和n中的公共质因数；4. 将m和n中的公共质因数相乘，乘积作为结果输出；例如，要计算gcd(66,12), 首先分解质因数66=2*3*11,12=2*2*3，然后提取二者的公共质因数2*3，则gcd(66,12)=2*3=6。五、程序流程图连续整数检测算法流程图如图1所示欧几里得算法流程图如图2所示六、源程序连续整数检测：#include int f1(int m,int n)int t;if(mn)t=n;else t=m;while(t) if(m%t=0&n%t=0)break;else t=t-1;return t; void main() int a,b; coutab; couta和b的最大公约数是： ; coutf1(a,b)endl;欧几里得算法：#includeint f2(int m,int n)int r;r=m%n;while(r!=0)m=n; n=r; r=m%n;return n;void main() int a,b; coutab; couta和b的最大公约数是： ; coutf2(a,b)endl;分解质因数法：#includeint f3(int m,int n)int i=2,j=0,h=0;int aN,bN,cN;while(in)if(n%i=0)j+;aj=i;n=n/i;else i+;j+;aj=n;i=1;int u;u=j;while(i=j) /printf(%d ,ai); i+;i=2;j=0; while(im)if(m%i=0)j+;bj=i;m=m/i;else i+;j+;bj=m;i=1;while(i=j) /printf(%d ,bi); i+;int k=1;for(i=1;i=j;i+)for(k=1;k1)k=k*ch*ch-1;h=h-2;if(h=1)k=k*c1;return k;else return k;void main() int a,b; coutab; couta和b的最大公约数是： ; coutCommonFactor(a,b)n)t=n;else t=m;while(t) if(m%t=0&n%t=0)break;else t=t-1;return t;根据代码考虑最坏情况他们的最大公约数是1，循环做了t-1次，最好情况是只做了1次，可以得出O（n）=n/2;（2） 欧几里得算法的时间复杂度 int f2(int m,int n)int r;r=m%n;while(r!=0)m=n; n=r; r=m%n;return n;根据代码辗转相除得到欧几里得的O(n)= log n（3） 分解质因数法的时间复杂度 int f3(int m,int n)int i=2,j=0,h=0;int aN,bN,cN;while(in)if(n%i=0)j+;aj=i;n=n/i;else i+;j+;aj=n;i=1;int u;u=j;while(i=j) /printf(%d ,ai); i+;i=2;j=0; while(im)if(m%i=0)j+;bj=i;m=m/i;else i+;j+;bj=m;i=1;while(i=j) /printf(%d ,bi); i+;int k=1;for(i=1;i=j;i+)for(k=1;k1)k=k*ch*ch-1;h=h-2;if(h=1)k=k*c1;return k;else return k;根据代码分解质因子算法O(n)=n2+n/2九、算法计时和计数分析为了计算每种算法运行的次数所用的时间，将代码稍加改动添加代码如下：其中计数器采用的是没做一次循环就加1；计时器是记住开始时间和结束时间，用结束时间减开始时间。#includeiostream.h#includestdio.h#includestdlib.h#includetime.h#define N 100int w,w2,w3;/用于计数int f1(int m,int n)int t;if(mn)t=n;else t=m;while(t) if(m%t=0&n%t=0)break;else t=t-1;w+;return t;int f2(int m,int n)int r;r=m%n;w2=1;while(r!=0)m=n; n=r; r=m%n;w2+;return n;int f3(int m,int n)int i=2,j=0,h=0;int aN,bN,cN;while(in)if(n%i=0)j+;aj=i;n=n/i;w3+;else i+;w3+;j+;aj=n;i=1;int u;u=j;while(i=j) /printf(%d ,ai); i+; w3+;/printf(n);i=2;j=0; while(im)if(m%i=0)j+;bj=i;m=m/i;w3+;else i+;w3+;j+;bj=m;i=1;while(i=j) /printf(%d ,bi); i+; w3+;int k=1;for(i=1;i=j;i+)for(k=1;k1)k=k*ch*ch-1;h=h-2;w3+;if(h=1)k=k*c1;return k;else return k;int main(void) int m,n;printf( 请输入m,n :n);scanf(%d%d,&m,&n);int k;k=f1(m,n); printf( 方法一最大公约数为： %dn,k);k=f2(m,n);printf( 方法二最大公约数为： %dn,k);k=f3(m,n);printf( 方法三最大公约数为： %dn,k);printf(n-n);printf(n计数器显示结果：nnn); printf(方法一： %d n,w2); printf(方法二： %d n,w); printf(方法三： %d n,w3);printf(n-n);float a,i; clock_t start,finish; double usetime;i=0; start= clock(); while (i1000000)f1(m,n);i+;finish=clock(); usetime= finish-start; printf( 方法一用时%.f*10(-6) 豪秒n, usetime);i=0; start= clock(); while (i1000000)f2(m,n);i+;finish=clock(); usetime= finish-start; printf( 方法二用时%.f*10(-6) 豪秒n, usetime); i=0; start= clock(); while (i1000000)f3(m,n);i+;finish=clock(); usetime= finish-start; printf( 方法三用时%.f*10(-6) 豪秒n, usetime); 十、实验过程原始记录( 测试数据、图表、计算等)三种算法得到结果验证结果：计数器：我想到的是做一次循环就加一计算算法运行时间结果：在计算时间过程中因为计算机的运算速度很快，所以我利用了循环把时间精确得到10-6毫秒十一、实验结果、分析和结论（误差分析与数据处理、成果总结等。其中，绘制曲线图时必须用计算纸或程序运行结果、改进、收获）在本次实验中代码是我们组共同完成的，一开始我们感觉这个代码最多半小时就可以完成，但是第三个算法的时候我们分析了好久才写出来，在计算三种方法运行时间的时候，我们一开始只精确到毫秒（ms），计算结果都是零，后面我们写了一个循环调试才发现是我们的精确度还在不够，所以我们想到了计算算法执行了1000000次之后所用的时间，然后再求平均每次执行的时间。结果分析：从前面的复杂度O(n)的出欧几里得算法的是最优算法，连续整除法其次，最复杂的是分解质因数算法，再从代码运行的计数器和计算的时间来看结果恰好和前面的复杂度得到的结果一致，所以的出结论：欧几里得算