1.算法求最大公约数实验报告格式下载_Word模板_21

1.算法求最大公约数实验报告格式昆明理工大学信息工程与自动化学院学生实验报告 ( 2012 — 2013 学年第 1 学期 ) 课程名称:算法设计与分析开课实验室:信自楼机房442 2012 年10月 18日年级、专业、计算机科学号 201010405109 姓名刘哲成绩班学与技术实验项目名称求最大公约数指导教师吴霖教该同学是否了解实验原理: A.了解? B.基本了解? C.不了解? 该同学的实验能力: A.强 ? B.中等 ? C.差 ? 师该同学的实验是否达到要求: A.达到? B.基本达到? C.未达到? 实验报告是否规范: A.规范? B.基本规范? C.不规范? 评实验过程是否详细记录: A.详细? B.一般 ? C.没有 ? 语教师签名: 年月日一、上机目的及内容 1.上机内容求两个自然数m和n的最大公约数。 2.上机目的 (1)复习数据结构课程的相关知识，实现课程间的平滑过渡; (2)掌握并应用算法的数学分析和后验分析方法 ; (3)理解这样一个观点:不同的算法能够解决相同的问题，这些算法的解题思路不同，复杂程度不同，解题效率也不同。二、实验原理及基本技术路线图(方框原理图或程序流程图) (1)至少设计出三个版本的求最大公约数算法; 第一种方法:连续整数检测法 1. t=min{m,n}; 2. m除以t,如果余数是0，则执行步骤3，否则，执行第4步; 3. n除以t，如果余数为0，返回t的值作为结果，否则，执行第4步; 4. t=t-1，转第2步 -1- 开始 T=min{m,n} T=t-1 m%t=0? t=t-1 N Y N n%t=0? Y 结束第二种方法:欧几里得算法 1. r=m%n; 2. 循环直到r=0 2.1 m=n; 2.2 n=r; 2.3 r=m%n; 3. 输出n; -2- 开始输入m和n r=m%n Y r=0 N m=n n=r 输出n 结束第三种方法:分解质因数法 1( 将m分解质因数 2( 将n分解质因数 3( 提取m和n中的公共质因数 4( 将m和n中的公共质因数相乘，乘积作为结果输出 -3- 开始输入m，n，h1，h2 fenjie(m, h1); fenjie(n, h2); 从m和n中提取公共质因数公共质因数相乘结束 (2)对所设计的算法采用大O符号进行时间复杂性分析; 第一种方法:连续整数检测法根据代码考虑最坏情况他们的最大公约数是1，循环做了t-1次，最好情况是只做了1次，可以得出O(n)=n/2; 第二种方法:欧几里得算法 n根据代码辗转相除得到欧几里得的O(n)= log 第三种方法:分解质因数法根据代码分解质因子算法O(n)=n2+n/2 (3)上机实现算法，并用计数法和计时法分别测算算法的运行时间; 《由于我没想出算法运行时间怎么计时，我就问了下学长怎么求仅供参考,但程序我已经自己调通了》为了计算每种算法运行的次数所用的时间，我将代码稍加改动添加代码如下: 其中计数器采用的是没做一次循环就加1; 计时器是记住开始时间和结束时间，用结束时间减开始时间。 #include"iostream.h" -4- #include"stdio.h" #include"stdlib.h" #include"time.h" #define N 100 int w,w2,w3;//用于计数 int f1(int m,int n) { int t; if(m>n)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 a[N],b[N],c[N]; while(i1) { k=k*c[h]*c[h-1]; h=h-2; w3++; } if(h==1) { k=k*c[1]; 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(" 方法一最大公约数为: %d\n",k); k=f2(m,n); printf(" 方法二最大公约数为: %d\n",k); k=f3(m,n); printf(" 方法三最大公约数为: %d\n",k); -7- printf("\n--------------------\n"); printf("\n计数器显示结果:\n\n\n"); 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 (i<1000000) { f1(m,n); i++; } finish=clock(); usetime= finish-start; printf(" 方法一用时%.f*10^(-6) 豪秒\n", usetime); i=0; start= clock(); while (i<1000000) { f2(m,n); i++; } finish=clock(); usetime= finish-start; printf(" 方法二用时%.f*10^(-6) 豪秒\n", usetime); i=0; start= clock(); while (i<1000000) { f3(m,n); i++; } finish=clock(); usetime= finish-start; printf(" 方法三用时%.f*10^(-6) 豪秒\n", usetime); -8- } (4)通过分析对比，得出自己的结论。三、所用仪器、材料(设备名称、型号、规格等或使用软件) 1台PC及VISUAL C++6.0软件四、实验方法、步骤(或:程序代码或操作过程) 第一种方法:连续整数检测法 #include int min(int m,int n) { int k; if(m int fun(int m,int n) { int r=m%n; while(r!=0) { m=n; n=r; r=m%n; } return n; } void main() { int a,b; -10- printf("input a,b\n"); scanf("%d,%d",&a,&b); printf("%d",fun(a,b)); } 第三种方法:分解质因数法 #include #define MAX_ARRAY_LENGTH 10 void fenjie(int m, int output[]) { int i=0; for(int a=2;a<=m;) { if(m%a==0) { output[i]=a; m=m/a; i++; a=2; } else { a++; } } } void initArray(int array[], int n) { for (int i=0; i

                    本文档为【1&#46;算法求最大公约数实验报告格式】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

1&#46;算法求最大公约数实验报告格式

你可能还喜欢

1.算法求最大公约数实验报告格式