实验一：三法求最大公约数实验报告电子版(已交)

1、实验报告单闹卅劣二紆犯孚氏hubei university of education隧（驾）计算机学院一、空無©的（1）复习数据结构课程的相关知识，实现课程间的平滑过渡；（2）掌握并应用算法的数学分析和后验分析方法；（3）理解这样一个观点：不同的算法能够解决相同的问题，这些算法的解题思路不同，复杂 程度彳、同,解题效率也彳、同。机房三、x血理（或爰求）（1）至少设计出三个版本的求最大公约数算法;（2）对所设计的算法采用大0符号进行时间复杂性分析；（3）上机实现算法，并用计数法和计时法分别测算算法的运行时间;（4）通过分析对比，得出自己的结论。源程序：#include<stdio

2、. h> includetime. h> #include<stdlib.h> int max(int m, int n) int r;辻(m>n)r=n;elsereturn r;void menu()int a;void algorithmone(); void algorithmtwoo ; void algorithmthree (); printf (请选择算法:rt); printf (z，l.算法一n"); printf (z，2.算法二n"); printf ("3.算法三n"); scanf ("

3、%d： &a); getchar ();switch(a)case 1:algorithmoneo ;break; case 2:algorithmtwoo ;break; case 3:algorithmthree():break;default:printf ("请输入 1, 2, 3 中的一个！ n");void algorithmone ()算法一clock_t start, finish;int m, n, r;char key;printff求两个数的最大公约数，请输入这两个数：")； scanf ("%d %d", &am

4、p;m, &n);getchar ();start=clock();r=max (m, n);while(r>0)if(m%r=0)if(n%r=0)printff算法一求出的最大公约数为%d,r); finish=clock();break;elser=rl;elser=rl;printf (z，算法一所需的时间是:ld 秒n", (finish-start);printf c是否返回主菜单? (y/n):");key=getchar();switch(key)case ' y' : menu (); break:case ' y&#

5、39;:menu();break;case 'n' :break;case ' n' :break;defauit:printf(error!n);void algorithmtwo ()/算法二clock_t start, finish;int m, n, r;char key;printff求两个数的最大公约数，请输入这两个数："); scanf ("%d %d", &m, &n);start二clock ();while(r=m%n)!=0)r=m%n;辻(r=0)printff算法二求出的最大公约数为d,n)

6、; finish=clock ();break;printf (z，算法二所需的时间是:ld 秒n", (finish-start); getchar ();printf f是否返回主菜单? (y/n):");key=getchar();switch(key)case ' y' :menu():break;case 'y' : menu (); break:case 'n' :break;case ' n' :break;default:printf ("error! n，z);/提取公共质数void

7、 commonzhishu(int arraym, int arrayn)int i, j, k=0, common3, d=0;for(i=0;i<3;i+)for(j=0;j<3;j+)if(arraymi=arraynj)commonk=arraymi ;k=k+l;for(k=0;k<3;k+)for (d=k+l;d<3;d+)if(commonk=commond)commond=l;printf (z，算法三结果dn", common 0 *common 1 *common2);void algorithmthree()/算法三clock_t st

8、art, finish;int m, n, mr, nr, i;float count;char key;mr=2;nr=2;printff求两个数的最大公约数，请输入这两个数：")； scanf ("%d %d”，&m, &n);int arraym3, arrayn3;i=0;start二clock();wh订e(m!=l)/将两数分解辻(count= (float) (m%mr) =0. 0)arraymi=mr;i+；m=m/mr;elsemr+;for(i=0;i<3;i+)printf (z，%d arraymi);printf("

9、;n");i=0;while(n!=l)if (count= (float) (n%nr) =0. 0)arrayni=nr;i卄；n=n/nr;elsenr+;for(i=0;i<3;i+)printf (z，%d arrayni);printf("n");commonzhishu(arraym, arrayn);finish二clock。；printf (z，算法三所需的时间是:ld 秒n", (finish-start); getchar ();printf r是否返回主菜单? (y/n):");key二getcharo ;swit

10、ch(key)case ' y :menu();break;case 'y，: menu (); break;case 1n" :break;case: break:defauit:printf("error!n");void main()int a;printf ("请选择算法:n");printf (，zl.算法一十);printf ("2.算法二n");printf (z，3.算法三n");scanf ("%d", &a);getchar ();switch(a)c

11、ase 1:algorithmone();break;case 2:algorithmtwo();break;case 3:algorithmthree();break;default: printf ("请输入 1, 2, 3 中的一个! n");n、佗录与处理（鼓绘如尿、谡屋分朽、倨果分朽）=i回asses法一所需迪财间是汉秒 否返回主采m?<sr/n>：y 选择算法：k卞个人资科作业学期算法设计与分折ppdebugpplmr3 鼻送二杂两个数的最大公约数，请输入这两个数：34算法二邛大台约礬为丄口肘间是:0秒星否返回主菜单? <y/n>：y 當选疑算法：1 算法一3 具注二3求两个数的最大公约数，请输入这两个数：343 -858993460 -8589934602 2 -858993460算法三结果-858993460 晉洼三所需的附间是：8秒 是否返回圭菜单? <y/n>：_ 丰：i 分析结论：复杂度：欧儿里得算法的是故优算法，连续整除法其次，最复朵的是分解质因数算法，再从代 码运行的