大数运算器程序设计文档

1、 韶关学院计算机科学学院数据结构课程设计题 目：大数运算器学生姓名：学 号：专 业：班 级： 指导教师姓名及职称： 讲师 起止时间： 年 月 年 月1.需求分析1.1课题背景及意义大数运算，顾名思义，就是很大的数值的数进行一系列的运算。随着社会的发展，数据出现了指数般爆炸性增长，而在天文学，数学，遗传学等传统学科，所研究的数字往往几百位甚至上千位，要求的精度也很高。但是在计算机中，由于字长的限制，计算机所能表示的范围是有限的，当我们对比较小的数进行运算时，这样的数值并没有超出计算机的表示范围，所以可以运算。但是当我们在实际的应用中进行大量的数据处理时，会发现参与运算的数往往超过计算机的基本数据

2、类型的表示范围，比如在天文学时常运用到的“光年”这一单位，如果求距地球几十光年的星球航天器所要到达的时间，计算机将无法对其进行运算。由于编程语言提供的基本数值数据类型表示的数值范围有限，不能满足较大规模的高精度数值计算，因此需要利用其他方法实现高精度数值的计算，于是产生了大数运算。大数运算主要有加、减、乘三种方法。既然在计算机中无法直接表示，那么大数到底如何进行运算呢，学习过数据结构的都知道线性表，将大数拆分然后存储在线性表中，不失为一个很好的办法。1.2课题要求基本要求： 实现一个大整数（要求允许绝对值232）的运算程序。要求程序读入操作数A和B，选择相应的加、减法或乘法运算符，然后计算结果

3、并输出到屏幕上。选做内容：（1）实现整除运算； （2）求出运算时间； （3）实现乘方运算； （4）图形化操作界面。1.2.1程序规定格式（1）输入的形式：正数的不同输入符号位，输入数为整型数，数位理论上为无限位。（2）程序所能达到的功能：能进行理论上无限位的数值之间所有整型数的四则运算。（3）输出的形式：整型数据1.2.2测试的数据(1)正确的输入以下是对两个大数进行加减乘运算所得的正确结果：大数A：999888777666555444333222111000大数B：111222333444555666777888999000正确的运算结果：A+B：1111111111111111111111

4、111110000A-B：888666444221999777555333112000A*B：111209963037098814851876554444456814851901296370456889000000以下是对两个大数进行除法运算所得的正确结果：大数A：999888777666555444333222111000大数B：1234567890正确的运算结果A/B：809909917280090157158(2)错误的输入数A：999999999999.9数B：3错误的结果：33333333333332概要设计2.1问题解决的思路概述 首先是确定结构化程序设计的流程图，利用字符串来进行

5、比较数的大小，把程序主要分为五个部分：实现加法的模块，实现减法的模块，实现乘法的模块，实现除法的模块，实现求余的模块，通过函数的嵌套调用来实现其功能，并通过编写main主函数来实现大整数的正确输入与正确输出，最后通过调试程序来修改不足和优化程序界面。2.2相关函数的的介绍与说明int sign=1; /sign 为符号位inline int compare(string str1,string str2)/定义比较两个函数大小string ADD_INT(string str1,string str2) /加法string:size_type L1,L2;/定义L1，L2的类型int int1

6、=0,int2=0; /int2 记录进位string:size_type tempint;/自定义tempintstring MUL_INT(string str1,string str2)/高精度乘法string DIVIDE_INT(string str1,string str2,int flag) /除法，flag=1时,返回商; flag=0时,返回余数string quotient,residue; /定义商和余数string tempstr/字符串变量string DIV_INT(string str1,string str2) return DIVIDE_INT(str1,st

7、r2,1);/除法,返回商string MOD_INT(string str1,string str2) return DIVIDE_INT(str1,str2,0);/除法,返回余数printf()/显示内容2.3主程序的流程图3调试分析4用户使用说明程序运行操作步骤：(1) 运行66666.exe应用程序后出现主界面；(2) 首先，按下数字键输入数A，按下回车键。在输入数的过程中，如果发现输入的某个数错误了，可按“退格”键从后往前一个个删除掉；（3）输入将要运算的运算符，如“加”是“+”，“减”是“-”，“乘”是“*”，“除”是“/”,“求余”是“%”；（4)输入数B，按下回车键，结果就会

8、显示在屏幕上。5测试结果 图1程序主界面 图2加法测试结果 图3减法测试结果 图4乘法测试结果 图5除法测试结果参考文献1严蔚敏，李冬梅，吴伟民 .数据结构(C语言版) M.北京:人民邮电出版社，2011.2谭浩强 .C+面向对象程序设计(第二版) M.北京：中国铁道出版社，2009.附录:程序源码#include #include using namespace std;inline int compare(string str1,string str2) /相等返回0，大于返回1，小于返回-1 if (str1.size()str2.size() return 1; /长度长的整数大于长度

9、小的整数 else if (str1.size()str2.size() return -1; else return pare(str2); /若长度相等，则头到尾按位比较string SUB_INT(string str1,string str2);string ADD_INT(string str1,string str2) /高精度加法 int sign=1; /sign 为符号位 string str; if (str10=-) if (str20=-) sign=-1; str=ADD_INT(str1.erase(0,1),str2.erase(0,1); else str=SU

10、B_INT(str2,str1.erase(0,1); else if (str20=-) str=SUB_INT(str1,str2.erase(0,1); else /把两个整数对齐，短整数前面加0补齐 string:size_type L1,L2; int i; L1=str1.size(); L2=str2.size(); if (L1L2) for (i=1;i=L2-L1;i+) str1=0+str1; else for (i=1;i=0;i-) int1=(int(str1i)-0+int(str2i)-0+int2)%10; int2=(int(str1i)-0+int(st

11、r2i)-0+int2)/10; str=char(int1+0)+str; if (int2!=0) str=char(int2+0)+str; /运算后处理符号位 if (sign=-1)&(str0!=0) str=-+str; return str;string SUB_INT(string str1,string str2) /高精度减法 int sign=1; /sign 为符号位 string str; int i,j; if (str20=-) str=ADD_INT(str1,str2.erase(0,1); else int res=compare(str1,str2);

12、if (res=0) return 0; if (res=0;i-) if (str1i+tempint=0;i-) str=str1i+str; /去除结果中多余的前导0 str.erase(0,str.find_first_not_of(0); if (str.empty() str=0; if (sign=-1) & (str0!=0) str =-+str; return str;string MUL_INT(string str1,string str2) /高精度乘法 int sign=1; /sign 为符号位 string str; if (str10=-) sign*=-1;

13、 str1 =str1.erase(0,1); if (str20=-) sign*=-1; str2 =str2.erase(0,1); int i,j; string:size_type L1,L2; L1=str1.size(); L2=str2.size(); for (i=L2-1;i=0;i-) /模拟手工乘法竖式 string tempstr; int int1=0,int2=0,int3=int(str2i)-0; if (int3!=0) for (j=1;j=0;j-) int1=(int3*(int(str1j)-0)+int2)%10; int2=(int3*(int(

14、str1j)-0)+int2)/10; tempstr=char(int1+0)+tempstr; if (int2!=0) tempstr=char(int2+0)+tempstr; str=ADD_INT(str,tempstr); /去除结果中的前导0 str.erase(0,str.find_first_not_of(0); if (str.empty() str=0; if (sign=-1) & (str0!=0) str=-+str; return str;string DIVIDE_INT(string str1,string str2,int flag) /高精度除法。fla

15、g=1时,返回商; flag=0时,返回余数 string quotient,residue; /定义商和余数 int sign1=1,sign2=1; if (str2 = 0) /判断除数是否为0 quotient= ERROR!; residue = ERROR!; if (flag=1) return quotient; else return residue ; if (str1=0) /判断被除数是否为0 quotient=0; residue =0; if (str10=-) str1 = str1.erase(0,1); sign1 *= -1; sign2 = -1; if

16、(str20=-) str2 = str2.erase(0,1); sign1 *= -1; int res=compare(str1,str2); if (res0) quotient=0; residue =str1; else if (res = 0) quotient=1; residue =0; else string:size_type L1,L2; L1=str1.size(); L2=str2.size(); string tempstr; tempstr.append(str1,0,L2-1); for (int i=L2-1;i=0;ch-) /试商 string str; str=str+ch; if (compar