算法设计报告.docx
- 文档编号:2861667
- 上传时间:2023-05-04
- 格式:DOCX
- 页数:10
- 大小:49.15KB
算法设计报告.docx
《算法设计报告.docx》由会员分享,可在线阅读,更多相关《算法设计报告.docx(10页珍藏版)》请在冰点文库上搜索。
算法设计报告
JIANGSUUNIVERSITY
算法设计与分析课程设计
设计分析测试报告
题目:
求两个数的最大公因数
专业班级:
J软件工程1
姓名:
高阳
学号:
4121169020
指导教师:
苟建平
2014年12月
程序算法设计说明书
一、前言
1.问题描述
最大公因数。
编写一个完整的程序,计算任意两个整数a,b的最大公因数,其中0≤a,b≤10100。
(要求:
禁止网上下载大数类实现;10分钟内输出结果)
2.程序编制环境相关说明
系统:
WINDOWS8.1
编制环境:
visualstudio2013
二、程序主要算法设计分析说明
算法设计思路:
用取模来加速计算,但大数不能用数值类型来存储,得用字符串或数组来运算,我下面是用字符串来实现的。
用字符串来进行计算,从低位到高位计算。
当数很大时,因为辗转相除法是用减法来做的,数太大,所需时间过长,不满足10分钟内输出结果,所以算法需要加速。
所以假设更大的那个数的长度是len1,更小的是len2,取模,关键算法就是把小的数扩大10*(len1-len2-1)倍,相减之后相当于一下子减了小数10*(len1-len2-1)次。
三、程序模块说明
1.总体设计说明
程序采用自己定义的a来存取第一个输入的数。
定义一个b来记录第二个输入的数。
11为a长度。
12为b长度
比较11和12。
lena存放a的的数长度。
lenb存放b的数的长度。
用ca[]一一存放a的的字符。
用经过比较处理的b作为结果输出。
2.模块说明:
采用3个函数,
Compare函数,来比较a,b里存放数的大小,长度来确定a和b的顺序(字符多的放a)。
Subtract函数来实现相减的功能。
Main函数里实现输入和输出,以及比较。
时间复杂度为O(n)。
4、总结(含主函数设计说明)
这次课程设计的题目有点复杂,一开始看到这个题目时,还不知道要怎么下手解决。
后来在网上搜索了一下求最大公因数问题及算法。
发现将数转换为字符来算就简单了。
算法解决了,接下来具体用什么数据结构,用数组最简单。
确定两个数组,程序就基本定下来了,算法解决了,接下来具体用什么数据结构实现也是个问题。
最后还是觉得直接用数组最简洁。
确定了用char数组,以及比较的方法。
为实现程序循环,开始就用了while,后由用户自己输入数字。
总结这次课程设计,虽然程序的实现并不难,也不复杂。
但是实现程序的算法却难倒了我。
这也让我深刻地体会到了算法的力量。
在以后的学习中,我一定会注意自己的薄弱环节,好好补充知识。
五、时间复杂度:
O(n)
程序及算法测试报告
一、前言
1.测试目的及采用的主要测试方法
目的:
测试该程序能否成功求出两数的最大公因数,以及速率。
测试方法:
用不同的数据测试,判断是否有误。
代码:
usingSystem;
usingSystem.Collections.Generic;
usingSystem.Linq;
usingSystem.Text;
namespace大数最大公因数
{
classProgram
{
staticvoidMain(string[]args)
{
stringa,b;
while(true)//控制程序循环
{
Console.WriteLine("Pleaseinput0toexit!
");//开关
Console.WriteLine("输入第一个数:
");
a=Console.ReadLine();//a记录第一个数
if(a=="0")
break;
Console.WriteLine("输入第二个数:
");
b=Console.ReadLine();//b记录第二个数
Compare(refa,refb);//比较ab是否一样
while(a!
="0")
{
Compare(refa,refb);
stringbb=b;
intl1=a.Length,l2=b.Length;//记录a,b的长度
if(l1-l2>1)//若a大于b
{
for(inti=0;i bb+="0"; while(a.Length>bb.Length) Subtract(refa,refbb); } Subtract(refa,refb); } Console.WriteLine("Thegreatestcommondivisorbis: \n{0}",b); } Console.Read(); } staticvoidCompare(refstringa,refstringb) { intlena=a.Length;//a长度 intlenb=b.Length;//b长度 if(lena>lenb) return; elseif(lena { stringtemp=a; a=b; b=temp; return; } else { inti=0,j=0; while(true) { if(a[i]>b[i]) return; elseif(a[i] { stringtemp=a; a=b; b=temp; return; } else { i++; j++; if(i==a.Length) return; } } } } staticvoidSubtract(refstringa,refstringb) {S Compare(refa,refb); char[]ca=a.ToCharArray();//把输入的a一一放入char数组里 char[]cc=newchar[a.Length];//定义一个长度为a长度的cc数组 inti=a.Length-1,j=b.Length-1; while(j>=0) { if(ca[i]>=b[j]) cc[i]=Convert.ToChar(ca[i]-b[j]+48);/转换长度 else { cc[i]=Convert.ToChar(ca[i]+10-b[j]+48); ca[i-1]=Convert.ToChar(ca[i-1]-1); } i--; j--; } while(i>=0)//i为长度 { if(! (ca[i]>='0'&&ca[i]<='9')) { cc[i]=Convert.ToChar(ca[i]+10); ca[i-1]=Convert.ToChar(ca[i-1]-1); } else cc[i]=ca[i]; i--; } i=0; while(i { if(cc[i]=='0') i++; else break; } if(i==cc.Length) a="0"; else a=newstring(cc,i,cc.Length-i); } } } 2.测试环境说明 系统: WINDOWS8.1 测试环境: visualstudio2013 二、测试用例说明 1.测试用例1 目的判断是否能求出两数最大公因数 输入123456789987654321 预期输出9 实际输出9 测试结果 2.测试用例2 目的算法速率 输入100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000和2 预期输出 实际输出2 测试结果 二、测试结果分析 测试结果显示,结果准确,速率也符合要求。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 设计 报告