算法分析与设计求最大公约数问题实验报告.doc

算法设计与分析实验报告书实验名称： 算法设计与分析之实验一 - 求两个数的最大公约数 学 号： 2012210890 姓 名： 王朔 评语：成绩： 指导教师： 批阅时间： 年 月 日算法分析与设计实验报告 - 6 - 一 实验目的和要求（1） 复习上课所讲的内容；（2） 掌握并应用算法的数学分析和后验分析方法；（3） 理解这样一个观点：不同的算法能够解决相同的问题，这些算法的解题思路不同，复杂程度不同，解题效率也不同。（4） 至少设计出三个版本的求最大公约数算法；（5） 上机实现算法，并用测算三种算法的运行时间；（6） 通过分析对比，得出自己的结论。 二 实验内容 设计三种算法求两个自然数 m 和 n 的最大公约数,并分析每种算法运行所需时间.三 实验环境 PCWin7系统 , VISUALC+6.0 四 设计思想及实验步骤 1.欧几里得辗转相除算法：输入两个正整数m,n(mn)；求出两个数的最大值Max和最小值Min；计算Max除以Min所得的余数r；Max=Min,Min=r；若r0,则m,n的最大公约数等于Max；否则转到；输出最大公约数Max。2.蛮力法算法：输入两个正整数m，n；令常量factor = 1;循环变量i从2min(m,n);如果i是m和n的公因子,则执行; factor = factor*i; m = m/i; n = n/i;如果i不是m和n的公因子，则i = i +1;输出factor；3.欧几里得减法算法：输入两个正整数a,b；求出两个数的最大值Max和最小值Min；若Max等于Min,转到；把Max-Min的差赋予r;如果Minr,那么把Min赋给Max,把r赋给Min;否则把r赋给Max，执行；输出最大公约数Min。测试三种算法，在例举数的范围内产生随机数，且在每个范围内运行1000次，求出所需总时间，最后输出计算每种算法平均执行一次所需的时间。六 核心源代码/ 2012210890王朔.cpp : Defines the entry point for the console application./#include stdafx.h#include stdio.h#include stdlib.h#include time.h#include windows.hint CommFactor1(int m,int n);int CommFactor2(int m,int n);int CommFactor3(int m,int n);int main(int argc, char* argv) int a10 = 10000,20000,40000,80000,100000,200000,500000,1000000,2000000,4000000; LARGE_INTEGER BegainTime; LARGE_INTEGER EndTime; LARGE_INTEGER Frequency; QueryPerformanceFrequency(&Frequency); QueryPerformanceCounter(&BegainTime); srand(unsigned)time(NULL); for(int i=0;i10;i+) for(int j=0;j1000;j=j+1) double k = (rand()*0.1); long m = (long)(ai+k); k = (0.1*rand(); long n = (long)(ai-k);CommFactor1(m,n); QueryPerformanceCounter(&EndTime); printf(算法一总耗时: %.10f 秒n,(double)(EndTime.QuadPart-BegainTime.QuadPart)/(Frequency.QuadPart*10000); system(pause); return 0;int CommFactor1(int m, int n) int c = m%n;while(c!=0)m = n;n = c;c= m%n;return n;int CommFactor2(int m, int n) int i, factor = 1; for(i = 2; i= m & im)i = m;m = n;n = i;r = m%n; while (r!=0) m = m-n; if(nm) i = m; m = n; n = i; r = m%n; return n;七 实验结果及分析 三种算法 算法运行时间欧几里得辗转相除法时间（ms）蛮力法时间（ms）欧几里得减法时间（ms）平均使用时间（ms）0.0008929 3.9237605 0.0041045 八 实验体会（包括本实验中遇到的问题、具体的解决方法、还没有解决的问题、实验收获等） 此次实验初步了解了算法分析，三种算法虽然结果相同但是效率却不同。对于复杂度的求解，可以根据我的结果分析得到欧几里得辗转相除算法的是最优算法，欧几里得减法其次，最复杂的是蛮力法。 在实验中，对于使用产生随机数测试算法的问题有了新的认识和了解，并学会了使用时间测试函数.从这次实验中，我复习了C语言代码，同时也通过算法分析用三种方法求解出了最大公约数这个问题。从这个试验的结果我了解到了算法的优与劣的差别，虽然得到的是同样的结果，但是需要的时间和资源却相差很大