最大公约数三种办法-计数器-流程图

1、-1-昆明理工大学信息工程与自动化学院学生实验报告）1学期2013学年 第（2012 日10月18 开课实验室：2012 年课程名称：算法设计与分析442 信自楼机房实验项目名称n m% i =0 丫 n n %i=0 i=i+1 丫丫r=0 n m=n n=r 求最大公约数开始开始指导教师吴晟教 师评 语该同学是否了解实验原理：a. 了解口 c.不了解口b.基本了解口a.强口 c.差该同学的实验能力： b.中等口未达到口该同学的实验是否达到要求：达到口a. c. b. 基本达到口c.不规范口实验报告是否规范： b.基本规范口a.规范口没有 c. 一般详细口a. 实验过程是否详细记录： b.教

2、师签名：日年月输入 m 和 n c=（ mn?m:n ）n m 输入和r=m% n 一、 上机目的及内容1.上机内容的最大公约数。 n 求两个自然数m 和 上机目的 2.）复习数据结构课程的相关知识，实现课程间的平滑过渡；（1 ）掌握并应用算法的数学分析和后验分析方法；（ 2）理解这样一个观点：不同的算法能够解决相同的问题，这些算法的解题思路不同，复杂程度不 3 （同，解题效率也不同。二、实验原理及基本技术路线图（方框原理图或程序流程图）1 ）至少设计岀三个版本的求最大公约数算法；（符号进行时间复杂性分析；2）对所设计的算法采用大0（ 3 ）上机实现算法，并用计数法和计时法分别测算算法的运行时

3、间；（）通过分析对比，得岀自己的结论。（4连续整数检测算法流程图: / k=i 输出结束时间复杂度t(n)=0 (iog2(n) -2- 欧几里得算法流程图 :连续整数检测算法n 输出结束:t( n)=0( n/2)时间复杂度欧几里得算法-3- 分解因式算法图开始输入y n a10,b10,s,t=2,i=0,all,i1,i2; m=m/t; ai=t,.i+ y all=all*ai1 n t+ n y s=n%t y y s=0 n n n 和 m m=1| n=1 s=m%t s=om=all n=n/t ;bi=t; i+; all=1 for(i2=0;i2i;i2+) al匸 a

4、ll*bi2; n=all y all=1 / 利用循环，求岀公共质因数for(int s1=0;s1i1;s1+) for(i nt s2=0;s2i2;s2+) if(as1=bs2) all=all*as1; -4- couvvallvve ndl; 结束分解因式时间复杂度：t(n)= 0(n/2) + o (log2(n) 三、所用仪器、材料( 设备名称、型号、规格等或使用软件) 1 台 pc 及 visual c+6.0 软件四、实验方法、步骤( 或：程序代码或操作过程) #include stdio.h #include #include #include #include int

5、 jishiqi_0(); int jishiqi_1(); int jishiqi_2(); int jishiqi_3(); float now,t0,t1,t2,t3; using namespace std; int m,n,c,k; / - int jishiqi_0()/ 输入时延长的多余时间int i,j; for(i=1;i=10000;i+) for(j=1;j=20000;j+); t0=(clock() -now)/clocks_per_sec; return 0; / - -5- int jishiqi_1()/ 分解因式算法所用时间int i,j; for(i=1;i

6、=10000;i+) for(j=1;j=20000;j+); t1=(clock() -now)/clocks_per_sec -t0; 牰湩晴尨分解因式算法所用时间为：%f msn,t1);return 0; / - int jishiqi_2()/ 欧几里得算法所用时间int i,j; for(i=1;i=10000;i+) for(j=1;j=20000;j+); t3=(clock() -now)/clocks_per_sec -t0-t1-t2; 牰湩晴尨欧几里得算法所用时间为：%f msn,t3);return 0; / - int jishiqi_3()/ 连续检测算法所用时间

7、int i,j; for(i=1;i=10000;i+) for(j=1;jn?m:n); for(int i=1;i=c;i+) if(m%i=0&n%i=0) k=i; else continue; return k; / - int oj(int m ,int n)/ 欧几里得算法jishiqi_2(); int r; r=m%n; while(r!=0) m=n; n=r; r=m%n; return n; / - 分解质因数法int fj(int m,int n)/ jishiqi_1(); if(m=1|n=1) 1endl; 潣瑵 ?最大公约数为：int a10,b10,

8、s,t=2,i=0,all,m1,n1,i1,i2; m1=m; n1=n; -7- coutm=; while(1) s=m1%t; / 求 m1 除以 t( t 为 2)的余数 s if(s=0) /如果 s 为 0，说明可以整除，则进行下面操作，记录m1=m1/t; ai=t; /把 t 摆在数组a 中coutt; i+; t=2; all=1; for(i1=0;i1i;i1+) all=all*ai1; if(m=all) break; /判断该整数的质因数是否全部求出cout*; else t+; i=0; / 把 i 重置为 0，进行整数n 的求质因数coutendl; cout

9、n=; while(1) s=n1%t; if(s=0) n1=n1/t; bi=t; coutt; i+; t=2; all=1; for(i2=0;i2i;i2+) all=all*bi2; if(n=all) break; cout*; else t+; coutendl; all=1; for(int s1=0;s1i1;s1+) / 利用循环，求出公共质因数t 为质因数其中之一for(int s2=0;s2i2;s2+) if(as1=bs2) -8- all=all*as1; bs2=0; /已经配对的质因数被清0，避免出现重复性的错误！break; 潣瑵 ?最大公约数为：alle

10、ndl; return 0; / - int main()/ 主函数char c; while(1) cout=endl; cout 求 最 大 公 约 数 的 程 序endl; cout 1、分解质因数法连续整数检测法欧几里得算法endl;cout=c; switch(c) case 1: 潣瑵 ?请分别输入两个整数mn; fj(m,n); 潣瑵 ?最大公约数为：lx(m,n)endl; 潣瑵 ?最大公约数为：oj(m,n)endl; break; default: 潣瑵 ?请重新输入！endl; break; return 0; -9- 五、实验过程原始记录(测试数据、图表、计算等)请给岀各个操作步骤的截图和说明；-10- -11- 六：实验结果、分析和结论( 误差分析与数据处理、成果总结等。其中，绘制曲线图时必须用计算纸或程序运行结果、改进、收获) 得出:我们从前面的时间复杂度t(n) )log2(n)0(n/2) + o ?( 0(n/2)olog2(n) (欧几里得算法的是最优算法，其次是连续整除法，最复杂的是分解质因数算法。再从代码运行的计数器和计算的时间来看结果恰好和前面的复杂度得到的结果一致，所以得出结论-12-欧几里得算法最优。通过对三种计算最大公约数方法的比较解了算法设计的初步概念并对求公约数问题有了更深的认识。了解到了算法