matlab最大公约数 三种算法

算法设计与分析 
                                      11信本 余启盛 118632011004
一、上机目的及内容
1.上机内容
求两个自然数m和n的最大公约数。
2.上机目的
（1）复习数据结构课程的相关知识，实现课程间的平滑过渡；
（2）掌握并应用算法的数学分析和后验分析方法；
（3）理解这样一个观点：不同的算法能够解决相同的问题，这些算法的解题思路不同，复杂程度不同，解题效率也不同。
二、实验原理及基本技术路线图
（1）至少设计出三个版本的求最大公约数算法；
（2）对所设计的算法采用大O符号进行时间复杂性分析；
（3）上机实现算法，并用计数法和计时法分别测算算法的运行时间；
（4）通过分析对比，得出自己的结论。
三、所用仪器、材料（设备名称、型号、规格等或使用软件）
1台PC及VISUAL C++6.0软件 matlab .2008
四、实验方法、步骤（或：程序代码或操作过程）   
实验采用三种方法求最大公约数
1、连续整数检测法。
2、欧几里得算法
3、蛮力法 （短除法）
根据实现提示写代码并分析代码的时间复杂度：
算法一：连续整数检测法。
CommFactor1
输入：两个自然数m和nprintf输出格式matlab
输出：m和n的最大公约数
1. 判断m和n哪个数小，t=min（m，n）
2.如果m%t==0&&n%t==0 ，结束
2.1 如果t不是m和n的公因子，则 t=t-1;
   
3. 输出t ;
    根据代码考虑最坏情况他们的最大公约数是1，循环做了t-1次，最好情况是只做了1次，可以得出O（n）=n/2;
算法二：欧几里德算法
  CommFactor2
输入：两个自然数m和n
输出：m和n的最大公约数
1. r = m % n;
2. 循环直到 r 等于0
      2.1  m = n;
      2.2  n = r;
      2.3  r = m % n;
3. 输出 n ;
根据代码辗转相除得到欧几里得的:  O(n)= log n

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。