算法设计报告Word文档格式.docx
- 文档编号:5261698
- 上传时间:2023-05-04
- 格式:DOCX
- 页数:10
- 大小:49.15KB
算法设计报告Word文档格式.docx
《算法设计报告Word文档格式.docx》由会员分享,可在线阅读,更多相关《算法设计报告Word文档格式.docx(10页珍藏版)》请在冰点文库上搜索。
编写一个完整的程序,计算任意两个整数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!
"
);
//开关
输入第一个数:
"
a=Console.ReadLine();
//a记录第一个数
if(a=="
0"
)
break;
输入第二个数:
b=Console.ReadLine();
//b记录第二个数
Compare(refa,refb);
//比较ab是否一样
while(a!
="
stringbb=b;
intl1=a.Length,l2=b.Length;
//记录a,b的长度
if(l1-l2>
1)//若a大于b
for(inti=0;
i<
l1-l2-1;
i++)
bb+="
;
while(a.Length>
bb.Length)
Subtract(refa,refbb);
}
Subtract(refa,refb);
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;
else
inti=0,j=0;
while(true)
if(a[i]>
b[i])
elseif(a[i]<
stringtemp=a;
i++;
j++;
if(i==a.Length)
staticvoidSubtract(refstringa,refstringb)
{S
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);
/转换长度
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);
cc[i]=ca[i];
i=0;
while(i<
cc.Length)
if(cc[i]=='
if(i==cc.Length)
a="
a=newstring(cc,i,cc.Length-i);
}
2.测试环境说明
测试环境:
二、测试用例说明
1.测试用例1
目的判断是否能求出两数最大公因数
输入123456789987654321
预期输出9
实际输出9
测试结果
2.测试用例2
目的算法速率
输入100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000和2
预期输出
实际输出2
二、测试结果分析
测试结果显示,结果准确,速率也符合要求。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 设计 报告