超长整型数据及存储与计算课程设计说明书

1、摘 要计算机的一个重要功能是进行科学计算，在科学研究和工程计算里经常会遇到一些很大的整数的计算问题，这些整数的计算没有办法利用普通的微机直接用现有程序设计语言中的整数类型进行存储和计算，这样就给研究工作带来了障碍。因此为解决超长整数的存储与运算设计，本人提出了自己的解决方案，采用字符串，数组对超长整数进行存储，即把处理数值改为处理字符串，因为字符串没有长度限制，且字符串中的每一个字符正好可以对应超长整数中的一位数字，把超长整数的加减乘除，转化为字符串的加减乘除。用数组对超长整数进行存储其优点是进行运算的时候比较方便。设计方案提出后，本文实现了这个超长整型数据的存储与运算程序，并对其进行了测试，

2、系统各项性能均达到了预期水平。本文的最后对该程序进行了详细的演示。关键词：超长整数；字符串；数组AbstractOne of the important functions of computer is scientific computing, in scientific research and engineering calculation. Often encountered some big integer calculation problem, the calculation of integers without method using common microcompute

3、rs directly by the integer programming language is existing types of storage and calculation, this research work to bring a barrier. So long integer solutions for the storage and operation, I put forward its own design solutions, using string array of long integers, store, the processing with numeri

4、cal instead, because the string string length, and not just in each character strings can be one of the corresponding ultra-long integer number, the long integers, add, subtract, multiply and divide into a string of add, subtract, multiply and divide. Use of long integer array stores. The advantages

5、 of computing is easier.After the design, this paper realized the long integer data storage and operation procedures, and analyses the testing system, various performance can achieve the desired level. Based on this program at the end of the detailed presentation.Keywords： long integer；string；array目

6、录第一章 绪论11.1 课题背景11.2 课题简介11.3 编写目的11.4 课程意义1第二章 设计简介及设计方案论述22.1程序分析22.2 程序设计2数据的接收与存储22.2.2 计算结果位数的确定22.2.3 进位处理和借位处理32.2.4 商和余数的求法4第三章 详细设计53.1 超长整型数据的接收与存储53.2 超长整数加法运算53.3 超长整数减法运算63.4 超长整数乘法运算63.5 超长整数的整除、求余运算7第四章 设计结果及分析104.1基本界面104.2运行过程104.3数据存储运算范围10总 结11致 谢12参考文献13附录14第一章 绪论1.1 课题背景随着计算机在全球

7、范围内日益普及，当今社会正快速向信息化社会前进，由于计算机具有运算速度快，计算精度高的特点，许多过去由人来完成的烦琐、复杂的数学计算，现在都可以由计算机来代替，人可以从计算中解放出来，做更具有创造性的工作。1.2 课题简介在C语言和VB中对于有符号的长整型数据的范围是-2147483648到2147483647之间，本设计是对超过这个范围的整数（以下简称超长整数）设计其存储方法和运算。（1）请设计单个超长整数的绝对值最大值是10101-1,两个超长整数运算后的结果值的绝对值最大不超过（10101-1）×（10101-1）。（2）分别编写对两个超长整数进行加、减、乘、整除、求余运算的函

8、数。（3）程序运行时可以对从键盘输入的两个超长整数进行以上五种运算。（4）使用C或VB编写程序。1.3 编写目的利用程序设计的方法去实现计算要求精度高，希望计算的数的位数可达几十位甚至几百位，但受硬件限制的超长整数的存储与计算问题。1.4 课程意义 1、掌握超长整数的计算基本方法并能应用。2、掌握超长整数加法、超长整数减法、超长整数乘法。3、掌握超长整数除法及运算中被除数、除数、商和余数之间的关系。4、分析总结常用超长整数算法特点，并能编写相应的程序。5、在学习的过程中应强化“算法领先”的意识，根据实际情况对超长整数运算进行优化的策略与方法。第二章 设计简介及设计方案论述2.1程序分析所谓的超

9、长整数运算,是指参与运算的整数(加数,减数,因子）范围大大超出了标准数据类型（整型）能表示的范围的运算。例如，求两个100位的数的和。这时，就要用到超长整数算法了。在计算机上进行超长整数计算，首先要处理好以下几个基本问题：1、 数据的接收与存储； 2、计算结果位数的确定；3、 进位处理和借位处理； 4、商和余数的求法；2.2 程序设计2.2.1数据的接收与存储 要在计算机上进行超长整型数据的计算，首先就应该有精确的输入，即计算机要精确地接收和存储数据。通常： 、当输入的数值在计算机允许的范围内时，可以用数值型变量来接收数据。 、当输入的数据超过计算机允许

10、显示的精度范围时，采用字符来接收数据。 、分离各位数字。 接收数据子模块(字符型变量接收数据)： int i , la , lb ; scanf ( "%s", c1); /*输入两个超长整型数据*/ scanf("%s",c2);la = strlen( c1 ); /*la纪录c1的位数*/ lb = strlen( c2 ); /*lb纪录c2的位数*/ for (i=0; i<la; i+) a1i=c1la-1-i-'0' /*把字符形数据c1,c2转为整数形数据,同样用数组纪录*/ for (i=0;

11、 i<lb; i+) a2i=c2lb-1-i-'0' 2.2.2 计算结果位数的确定   1、两数之和的位数最大为较大的数的位数加1。   2、乘积的位数最大为两个因子的位数之和。  2.2.3 进位处理和借位处理 1、加法的进位处理   两数相加时，从低位到高位，各位数字分别相加，然后对相加后的数和10进行整除和求余运算，整除之后的值为进位，而余数就等于所求数之和。不断重复，直到最高位为止。具体算法为： for(i=0;i<d;i+) ci=ai+bi+ci; ci+1=(int)c

12、i/10; /*ci+1代表进位*/ ci=(int)ci%10; /*超长整数加法运算过程*/    2、乘法的进位处理首先计算被乘数与乘数的个位数字的乘积，把结果保存到积数组中，然后再用被乘数去乘以乘数的十位数字，把结果退一位加到积数组中。每加一次乘积结果就进行一次进位处理，其方法与加法中的进位处理一样。for(i = 0; i < la; i+) /*超长整数乘法运算过程*/ for(j = 0;j < lb; j+) ci+j = ai * bj + ci+j; ci+j+1 = ci+j / 10 + ci+j+1; ci+j = ci+j % 10;

13、    3、减法的借位处理 做减法运算时，要先判断是否需要借位，如果需要借位，从上一位借过一个10，上一位的数减去1，处理完之后再相减。for(i=0;i<d;i+) if(ai<bi) ai+1-; ai+=10; ci=ai-bi; 2.2.4 商和余数的求法按照竖式计算的方式，设置一个临时的被除数，如果大于除数，则两数相减，临时商加1，直到临时被除数小于除数，此时把临时商写入商的相应位置，然后临时被除数*10加上被除数的下一位，如此循环，直至临时被除数小于除数，则此时临时被除数即就是余数。：char temp2 = "0"/临时数组依次

14、存储被除数的每一位数int i, s, k;strcpy(x, ""); /先使余数的值为空for (i=0,k=0; ui!='0' i+) s = 0; temp0 = ui; strcat(x, temp); /接上被除数的一位数，改变当前余数 while (Compare(x, v) >= 0) /连减试商 s+; isub(x, v, x); /isub()为一个自定义的整数减法函数 wk+ = s + '0'/记录每一位得到的商值第三章 详细设计3.1 超长整型数据的接收与存储void input(int a1,int a2

15、) /*函数input为输入函数,用来纪录两个待计算的超长整型数据,以数组首地址为参数.以实现返回两个超长整型数据*/ int i,a=1,b=1; printf("请输入第一个数:n"); scanf ( "%s", c1); printf("请输入第二个数：n"); /*输入两个超长整型数据*/ scanf("%s",c2);la = strlen( c1 ); /*la纪录c1的位数*/ lb = strlen( c2 ); /*lb纪录c2的位数*/ if(c10='-') la-; ra=

16、-1;a=0; /*判断数组的符号*/ if(c20='-') lb-; rb=-1;b=0; for (i=0; i<la; i+,a+) a1i=c1la-a-'0' /*把字符型数据c1,c2转为整数型数据,同样用数组纪录*/ for (i=0; i<lb; i+,b+) a2i=c2lb-b-'0' 3.2 超长整数加法运算void add(int a,int b,int p) /*超长整数加法运算*/ int i,cMAX+1=0,d; if(ra*rb>0|p) if(la>lb) d=la; else d=l

17、b; /*用d纪录结果的最大位数*/ for(i=0;i<d;i+) ci=ai+bi+ci; ci+1=(int)ci/10; /*ci+1代表进位*/ ci=(int)ci%10; /*超长整数加法运算过程*/ if(cd) d+; /*判断最后结果的位数*/ if(ra<0&&p|ra<0) printf("-"); for(i=d-1;i>=0;i-) printf("%d",ci); /* 输出结果*/ else sub(a,b,1);3.3 超长整数减法运算void sub(int a,int b,in

18、t p) /*超长整数减法运算*/ int i,h=0,cMAX+1=0,d; if(ra*rb>0|p) if(la>lb) d=la; else /*用d纪录结果的最大位数*/ d=lb; for(i=d;ai<=bi&&i>=0;i-) if(ai<bi) h=1; /*h纪录结果符号*/ if(!h) /*超长整数减法运算过程*/ for(i=0;i<d;i+) if(ai<bi) ai+1-; ai+=10; ci=ai-bi; else /*当a<b时的处理*/ for(i=0;i<d;i+) if(bi<

19、ai) bi+1-; bi+=10; ci=bi-ai; while(!cd-1&&d>1) d-; /*判断最后结果的位数*/ if(p&&(ra>0&&h|ra<0&&!h)|ra>0&&(rb>0&&h|h&&!p) printf("-"); if(ra<0&&rb<0&&!h) printf("-"); /*如果h为真是输出负*/ for(i=d-1;i>=

20、0;i-) printf("%d",ci); else add(a,b,1);3.4 超长整数乘法运算void mult( int a, int b) /*超长整数乘法运算*/ int i, j, c2*MAX = 0,d; d = la + lb - 1; /*用d纪录结果的最大位数*/ for(i = 0; i < la; i+) /*超长整数乘法运算过程*/ for(j = 0;j < lb; j+) ci+j = ai * bj + ci+j; ci+j+1 = ci+j / 10 + ci+j+1; ci+j = ci+j % 10; while(!c

21、d) d-; /*判断最后结果的位数*/ if(ra*rb<0) printf("-"); for(i = d; i >= 0; i-) printf("%d",ci); /*输出结果*/ 3.5 超长整数的整除、求余运算/比较两个用字符串存储的超长正整数的大小，若a>b，返回1；a=b，返回0；a<b，返回-1int Compare(const char *a, const char *b)int lA = strlen(a);int lB = strlen(b);if (a0='-') lA-;if (b0=&

22、#39;-') lB-;if (lA != lB) return lA > lB ? 1 : -1;else return strcmp(a,b);/超长正整数的减法，且被减数大于减数void isub(char *m, char *s, char *d)int cMMAX = 0;/用来存储被减数的整型数组int cSMAX = 0;/用来存储减数的整型数组int cDMAX = 0;/用来存储两数之差的整型数组int lM = strlen(m), lS = strlen(s);/被减数和减数字符串的长度int i;/逆序复制减数和被减数到整型数组（因为减法运算是从低位开始）

23、，保证cM大于cS for (i=0; i<lM; i+) cMi = mlM-1-i - '0' for (i=0; i<lS; i+) cSi = slS-1-i - '0'for (i=0; i<lM; i+)/减法运算过程 if (cMi >= cSi)/被减数大于减数，直接相减 cDi = cMi - cSi; else /否则要向前借位 cDi = cMi + 10 - cSi; -cMi+1; while (cDi-1 = 0) i-;int j = 0;int k;for (k=i-1; k>=0; k-,j+)/逆

24、序存储两数之差到字符串d dj = cDk + '0'dj = '0'/超长整型数据整除，求余计算void div(char *u, char *v, char *w, char *x)int lu=strlen(u),lv=strlen(v);if(u0='-')ra=-1; /判断数组的符号 for(int i=0;i<lu;i+) ui=ui+1; lu-;if(v0='-')rb=-1; for(int i=0;i<lv;i+) vi=vi+1; lv-;if (Compare(u, v) = 0)/被除数等于

25、除数 strcpy(w, "1"); strcpy(x, "0"); return ;if (strcmp(v, "0") = 0 | Compare(u, v) < 0)/被除数小于除数 strcpy(w, "0"); strcpy(x, u); return ;char temp2 = "0"/临时数组依次存储被除数的每一位数int i, s, k;strcpy(x, ""); /先使余数的值为空for (i=0,k=0; ui!='0' i+) s

26、 = 0; temp0 = ui; strcat(x, temp);/接上被除数的一位数，改变当前余数 while (Compare(x, v) >= 0)/连减试商 s+; isub(x, v, x); wk+ = s + '0'/记录每一位得到的商值 if (strcmp(x, "0") = 0) strcpy(x, ""); /使余数的值为空，去掉多余的0wk = '0' /去掉多余的0int j;for (i=0; wi='0' i+) ;for (j=i; j<=k; j+) wj-i

27、 = wj;第四章 设计结果及分析4.1基本界面4.2运行过程由于此程序涉及的运算比较多，而且要兼顾正负数的运算，所以代码中子函数较多，重复率高，所以程序运行时速度会比较慢。输入所要计算的两个超长整数后，程序会自动进行运算，准确的求出两数之和，两数之差，两数之积，两数之商以及余数，并输出显示在屏幕上，但并不能对运算符进行选择。4.3数据存储运算范围当所输入位数在101范围以内的整数时，无论正负，程序都会给出正确的运算结果当所输入的数据位数超过101时，程序将会停止运行。总 结此次课程设计是我们从走向未来工程师重要的一步。从最初的选题到完成设计。其间，查找资料，老师指导，与同学交流，反复修改设计

28、模块，每一个过程都是对自己能力的一次检验和充实。通过这次实践，我了解了超长整数的存储与运算问题，锻炼了工程设计实践能力，培养了自己独立设计能力。此次课程设计是对我专业知识和专业基础知识一次实际检验和巩固，同时也是做毕业设计前的一次热身。 课程设计收获很多，比如学会了查找相关资料相关标准，分析数据，提高了自己的独立思考与动手能力，懂得了许多经验公式的获得是前人不懈努力的结果。同时，仍有很多课题需要后辈去努力去完善。 但是此次设计也暴露出自己专业基础的很多不足之处。比如缺乏综合应用专业知识的能力，对材料的不了解，等等。这次实践是对自己大学这两年所学的一次大检阅，使我明白自己知识还很浅薄，以后更应该

29、努力学习，使自己成为一个对社会有所贡献的人,为IT工业添上自己的微薄之力！致 谢本论文是在张岗亭老师的亲自指导下完成的。老师勤奋严谨的治学态度、积极向上的进取精神和敏锐的洞察力，给我留下了深刻的印象，并将激励我不断前行。在这里，向老师致以崇高的敬意和衷心的感谢。在论文写作的过程中还得到了我班其他同学的帮助，在此表示衷心的感谢。衷心感谢学校给予的机会，感谢院系领导和老师的关心。感谢我们小组的其他的成员，无论是在编程序和写论文的阶段，他们给予了我极大的帮助，提供了许多宝贵的资料，提高了我得动手实践的能力，丰富了我的论文内容。最后还要感谢所有软件工程二班的同学和老师，是大家共同为整个集体创造了积极进

30、取、奋发向上的实习环境和氛围，使我们能够顺利完成整个课程设计。参考文献1 谭浩强C程序设计（第三版）M北京：清华大学出版社， 2010.2 严蔚敏吴伟民数据结构 M 北京： 高等教育出版社，2004.3 吴金平Visual C+6.0编程与实践M北京：中国水利水电出版社，2004.4 杨路明C/C+程序设计教程M湖南：湖南科技出版社，2001.5 David J. Kruglinski,Scot Wingo,et al.Visual C+6.0技术内幕M.北京:希望电子出版社,1999.附录#include <stdio.h>#include <string.h>#in

31、clude <math.h>#include<stdlib.h>#define MAX 101void sub(int a,int b,int p); / 函数功能：利用字符串实现超长整数减法运算int la,lb,ra=1,rb=1; /* 把la,lb设为全局变量,la纪录第一个超长整型数组的位数,lb纪录第二个超长整型数组的位数*/char c1MAX, c2MAX; /*纪录需要计算的两个超长整型数据 */void input(int a1,int a2) /*函数input为输入函数,用来纪录两个待计算的超长整型数据,以数组首地址为参数.以实现返回两个超长整型

32、数据*/ int i,a=1,b=1; printf("请输入第一个数:n"); scanf ( "%s", c1); printf("请输入第二个数：n"); /*输入两个超长整型数据*/ scanf("%s",c2);la = strlen( c1 ); /*la纪录c1的位数*/ lb = strlen( c2 ); /*lb纪录c2的位数*/ if(c10='-') la-; ra=-1;a=0; /*判断数组的符号*/ if(c20='-') lb-; rb=-1;b=0;

33、 for (i=0; i<la; i+,a+) a1i=c1la-a-'0' /*把字符型数据c1,c2转为整数型数据,同样用数组纪录*/ for (i=0; i<lb; i+,b+) a2i=c2lb-b-'0' void add(int a,int b,int p) /*超长整数加法运算*/ int i,cMAX+1=0,d; if(ra*rb>0|p) if(la>lb) d=la; else d=lb; /*用d纪录结果的最大位数*/ for(i=0;i<d;i+) ci=ai+bi+ci; ci+1=(int)ci/10;

34、 /*ci+1代表进位*/ ci=(int)ci%10; /*超长整数加法运算过程*/ if(cd) d+; /*判断最后结果的位数*/ if(ra<0&&p|ra<0) printf("-"); for(i=d-1;i>=0;i-) printf("%d",ci); /*输出结果*/ else sub(a,b,1); void sub(int a,int b,int p) /*超长整数减法运算*/ int i,h=0,cMAX+1=0,d; if(ra*rb>0|p) if(la>lb) d=la; els

35、e /*用d纪录结果的最大位数*/ d=lb; for(i=d;ai<=bi&&i>=0;i-) if(ai<bi) h=1; /*h纪录结果符号*/ if(!h) /*超长整数减法运算过程*/ for(i=0;i<d;i+) if(ai<bi) ai+1-; ai+=10; ci=ai-bi; else /*当a<b时的处理*/ for(i=0;i<d;i+) if(bi<ai) bi+1-; bi+=10; ci=bi-ai; while(!cd-1&&d>1) d-; /*判断最后结果的位数*/ if(

36、p&&(ra>0&&h|ra<0&&!h)|ra>0&&(rb>0&&h|h&&!p) printf("-"); if(ra<0&&rb<0&&!h) printf("-"); /*如果h为真是输出负号*/ for(i=d-1;i>=0;i-) printf("%d",ci); else add(a,b,1);void mult( int a, int b) /*超长

37、整数乘法运算*/ int i, j, c2*MAX = 0,d; d = la + lb - 1; /*用d纪录结果的最大位数*/ for(i = 0; i < la; i+) /*超长整数乘法运算过程*/ for(j = 0;j < lb; j+) ci+j = ai * bj + ci+j; ci+j+1 = ci+j / 10 + ci+j+1; ci+j = ci+j % 10; while(!cd) d-; /*判断最后结果的位数*/ if(ra*rb<0) printf("-"); for(i = d; i >= 0; i-) print

38、f("%d",ci); /*输出结果*/ /比较两个用字符串存储的超长正整数的大小，若a>b，返回1；a=b，返回0；a<b，返回-1int Compare(const char *a, const char *b)int lA = strlen(a);int lB = strlen(b);if (a0='-') lA-;if (b0='-') lB-;if (lA != lB) return lA > lB ? 1 : -1;else return strcmp(a,b);/超长正整数的减法，且被减数大于减数void is

39、ub(char *m, char *s, char *d)int cMMAX = 0;/用来存储被减数的整型数组int cSMAX = 0;/用来存储减数的整型数组int cDMAX = 0;/用来存储两数之差的整型数组int lM = strlen(m), lS = strlen(s);/被减数和减数字符串的长度int i;/逆序复制减数和被减数到整型数组（因为减法运算是从低位开始），保证cM大于cS for (i=0; i<lM; i+) cMi = mlM-1-i - '0' for (i=0; i<lS; i+) cSi = slS-1-i - '0'for (i=0; i<lM; i+)/减法运算过程 if (cMi >= cSi)/被减数大于减数，直接相减 cDi = cMi - cSi; else /否则要向前借位 cDi = cMi + 10 - cSi; -cMi+1; while (cDi-1 = 0) i-;int j = 0;int k;for (k=i-1; k>=0; k-,j+)/逆序