算法设计报告

1、J I A N G S U U N I V E R S I T Y算法设计与分析课程设计设计分析测试报告 题目： 求两个数的最大公因数专业班级： J软件工程1 姓 名： 高阳 学 号： 4121169020 指导教师：苟建平 2014年 12月程序算法设计说明书一、 前言1. 问题描述最大公因数。编写一个完整的程序，计算任意两个整数a, b 的最大公因数，其中0a, b10100。（要求：禁止网上下载大数类实现；10 分钟内输出结果）2. 程序编制环境相关说明系统：WINDOWS 8.1编制环境：visual studio 2013二、 程序主要算法设计分析说明算法设计思路：用取模来加速计算，

2、但大数不能用数值类型来存储，得用字符串或数组来运算，我下面是用字符串来实现的。用字符串来进行计算，从低位到高位计算。当数很大时，因为辗转相除法是用减法来做的，数太大，所需时间过长，不满足10分钟内输出结果，所以算法需要加速。所以假设更大的那个数的长度是len1，更小的是len2，取模，关键算法就是把小的数扩大10*（len1-len2-1）倍，相减之后相当于一下子减了小数10*（len1-len2-1）次。三、 程序模块说明1. 总体设计说明程序采用自己定义的a来存取第一个输入的数。定义一个b来记录第二个输入的数。11为a长度。12为b长度比较11和12。lena存放a的的数长度。lenb存放

3、b的数的长度。用ca一一存放a的的字符。用经过比较处理的b作为结果输出。2.模块说明：采用3个函数，Compare函数，来比较a，b里存放数的大小，长度来确定a和b的顺序（字符多的放a）。Subtract函数来实现相减的功能。Main函数里实现输入和输出，以及比较。时间复杂度为O（n）。4、 总结（含主函数设计说明）这次课程设计的题目有点复杂，一开始看到这个题目时，还不知道要怎么下手解决。后来在网上搜索了一下求最大公因数问题及算法。发现将数转换为字符来算就简单了。算法解决了，接下来具体用什么数据结构，用数组最简单。确定两个数组，程序就基本定下来了，算法解决了，接下来具体用什么数据结构实现也是个

4、问题。最后还是觉得直接用数组最简洁。确定了用char数组，以及比较的方法。为实现程序循环，开始就用了while，后由用户自己输入数字。总结这次课程设计，虽然程序的实现并不难，也不复杂。但是实现程序的算法却难倒了我。这也让我深刻地体会到了算法的力量。在以后的学习中，我一定会注意自己的薄弱环节，好好补充知识。五、 时间复杂度：O（n）程序及算法测试报告一、 前言1. 测试目的及采用的主要测试方法目的：测试该程序能否成功求出两数的最大公因数，以及速率。测试方法：用不同的数据测试，判断是否有误。代码：using System;using System.Collections.Generic;using

5、 System.Linq;using System.Text;namespace 大数最大公因数 class Program static void Main(string args) string a, b; while (true)/控制程序循环 Console.WriteLine("Please input 0 to exit!");/开关 Console.WriteLine("输入第一个数: "); a = Console.ReadLine();/a记录第一个数 if (a = "0") break; Console.Writ

6、eLine("输入第二个数： "); b = Console.ReadLine();/b记录第二个数 Compare(ref a, ref b);/比较ab是否一样 while (a != "0") Compare(ref a, ref b); string bb = b; int l1 = a.Length, l2 = b.Length;/记录a，b的长度 if (l1 - l2 > 1)/若a大于b for (int i = 0; i < l1 - l2 - 1; i+) bb += "0" while (a.Leng

7、th > bb.Length) Subtract(ref a, ref bb); Subtract(ref a, ref b); Console.WriteLine("The greatest common divisorb is:n0", b); Console.Read(); static void Compare(ref string a, ref string b) int lena = a.Length;/a长度 int lenb = b.Length;/b长度 if (lena > lenb) return; else if (lena < l

8、enb) string temp = a; a = b; b = temp; return; else int i = 0, j = 0; while (true) if (ai > bi) return; else if (ai < bi) string temp = a; a = b; b = temp; return; else i+; j+; if (i = a.Length) return; static void Subtract(ref string a, ref string b) S Compare(ref a, ref b); char ca=a.ToCharA

9、rray();/把输入的a一一放入char数组里 char cc=new chara.Length;/定义一个长度为a长度的cc数组 int i = a.Length - 1, j = b.Length - 1; while (j >= 0) if (cai >= bj) cci = Convert.ToChar(cai - bj + 48);/转换长度 else cci = Convert.ToChar(cai + 10 - bj + 48); cai - 1 = Convert.ToChar(cai - 1 - 1); i-; j-; while (i >= 0)/i为长

10、度 if (!(cai >= '0' && cai <= '9') cci = Convert.ToChar(cai + 10); cai - 1 = Convert.ToChar(cai - 1 - 1); else cci = cai; i-; i = 0; while (i<cc.Length) if (cci = '0') i+; else break; if (i = cc.Length) a = "0" else a = new string(cc, i, cc.Length - i); 2. 测试环境说明系统：WINDOW