算法设计与分析-1.docx

南昌航空大学实验报告 年 月 日课程名称： 算法设计与分析 实验名称： 求最大公约数 班级： 11201221 姓名： 林平君 同组人： 指导教师评定： 签名： 一 实验目的1. 对问题进行分析，将其抽象，并设计出算法。2. 将算法用程序代码实现。3. 分析算法实现的效率。二 实验要求1. 熟悉求解最大公约数的几种算法。2. 熟练掌握一门程序设计语言。3. 能将算法用程序语言实现。三 算法效率分析4. 蛮力法5. 最优效率：C_best(n)=16. 最差效率：C_worst(n)=n7. 平均效率：C_avg(n)=n/28. Euclid算法9. 最优效率：C_best(n)=110. 最差算法：C_worst(n)=n11. 平均算法：C_avg(n)=log2(n)四 源代码蛮力法：using System;using System.Collections.Generic;using System.Linq;using System.Text;/课程：算法设计与分析基础/算法名称：蛮力法求解公约数/时间：2014年2月18日namespace 蛮力法 class Program static void Main(string args) /输入两个整形数 int m, n; Console.WriteLine(请输入两个整数); Console.WriteLine(第一个数：); m = int.Parse(Console.ReadLine(); Console.WriteLine(第二个数：); n = int.Parse(Console.ReadLine(); int min = judgemin(m, n); int max = judgemax(m, n); if (min = 0) Console.WriteLine(公约数为： + max); else for (int i = min; i 0; i-) if (max % i = 0 & min % i = 0) Console.WriteLine(最大公约数是： + i); break; Console.ReadKey(); /判断两者中小的值 static public int judgemin(int m, int n) if (m n) return n; else return m; /判断两者中大的值 static public int judgemax(int m, int n) if (m n) return m; else return n; Euclid：using System;using System.Collections.Generic;using System.Linq;using System.Text;/课程：算法设计与分析基础/算法名称：欧几里得求解最大公约数/时间2014年2月18日namespace Euclid2 class Program static void Main(string args) /Input two int number int m, n; Console.WriteLine(第一个数：); m = int.Parse(Console.ReadLine(); Console.WriteLine(第二个数：); n = int.Parse(Console.ReadLine(); int min, max, temp; min = Program.judgemin(m, n); max = Program.judgemax(m, n); while (min != 0) temp = max % min; max = min; min = temp; Console.WriteLine(最大公约数是：+max); Console.ReadKey(); /判断两个值得最小值 static public int judgemin(int m, int n) if (m n) return n; else return m; /判断两个值得最大值 static public int judgema