超长整数的存储与运算设计说明书.doc

计算机科学系课程设计任务书计算机科学系课程设计任务书 摘 要 计算机计算结果的精度，通常要受到计算机硬件环境的限制。在 C 语言和 VB 中 对于有符号的长整型数据的范围是-2147483648 到 2147483647 之间，用户一般是无法 改变的。但是，我们可以通过“软”的方式来解决这一困难，即通过程序设计的方法 进行超长整型数据的计算。 运算因子超出了整型能表示的范围，肯定不能直接用一个数的形式来表示。在 C 语言中，能表示多个数的数据类型有两种：数组和字符串。因此采用字符串读 入数据，用数组存储数据 。解决了高级程序 设计语言处理数据存储空间问题，实 现了超长整数的加减乘除求余运算。 超长整型数据的存储与运算设计对超长整数分别进行了存储与加减乘除求余运 算，达到了预期目标，最后对实现算法做了简要的分析和介绍。 关键词：超长整型数据；字符串；数组 Abstract Computer calculation results, the precision of computer hardware environment is usually to the limit. In C language and VB to have long integer data of symbols of integers range is 2147483648 - between the users to cant be changed. However, we can use the word “soft“ way to solve this difficult, namely through programming method for long integer data calculation. Computing factor beyond the scope of integer can say, must not be directly used a number of forms. In C, can say the number of data types is more than two kinds: arrays and string. Therefore, the use of input data using string array of data storage. Solve a high-level programming language processing data storage space, the problem of long integer arithmetic for more add, subtract, multiply and divide. Long integer data storage and operation of long integer separately designed for the storage and add, subtract, multiply and divide more computing, and finally reached the expected goal to realize algorithm provides a brief introduction and analysis. Keywords： long integer；string；array 西安文理学院计算机科学系 课程设计报告 目录 第一章 绪论.1 1.1 课程背景 .1 1.2 课程目的 .1 1.3 课程意义 .1 1.4 课程设计采取的基本原理和主要技术方法 .1 第二章 设计简介及设计方案论述.2 2.1 程序的主要功能 .2 2.2 程序设计的思想 .2 2.2.1 运算数据、结果的输入和存储.2 2.2.2 超长整数加法运算.2 2.2.3 超长整数减法运算.3 2.2.4 超长整数乘法运算3 2.2.5 超长整数的整除及求余运算4 第三章 详细设计.5 3.1 超长整型数据的输入 .5 3.2 超长整数的加法 .5 3.3 超长整数的减法 .6 3.4 超长整数的乘法 .6 3.5 超长整数的整除及求余 .7 第四章 设计结果及分析.10 4.1 设计概述 .10 4.2 设计约束 .10 4.3 运行流程 .10 总 结.11 致 谢.12 参考文献.13 附录.14 西安文理学院计算机科学系 课程设计报告 - 1 - 第一章 绪论 1.1 课程背景 随着现代社会计算机科学技术与经济的不断飞速发展，计算机在科学计算 与人们日常生活中的应用也越来越普及，利用计算机实现一些数据的存储与计 算也显得越来越重要，因而相对于科学计算精度的要求也越来越高。国民生产 总值的统计，中央银行货币的统计，国家粮食生产量的统计等超大数值统计都 需要有高精度的数据处理方式。在数学上，大数研究也需要对超长数值的运算 进行处理。由此可见，超长整形数据的设计的意义是重大而深远的。 1.2 课程目的 学习并掌握计算机对于整型数据的存储与运算方法及原理，并能够运用 C 语言来编写程序，实现超长整型数据的存储与运算，解决科学计算与实际生活 中的相关问题。 1.3 课程意义 1、掌握超长整数的计算基本方法并能应用。 2、掌握超长整数加法、超长整数减法、超长整数乘法。 3、掌握超长整数除法运算中被除数、除数、商和余数之间的关系。 4、分析总结常用超长整数算法特点，并能编写相应的程序。 5、在学习的过程中应强化“算法领先”的意识，根据实际情况对超长整数运算 进行优化的策略与方法。 1.4 课程设计采取的基本原理和主要技术方法 本程序是专门针对超长整型数据而开发的一个功能齐全、操作简单的存储 与运算程序。本程序实现以下基本功能：操作人员可以对超长整型数据进行存 储，还可以对所输入的数据进行准确的加减乘以及整除求余运算 本系统使用的是 VC6.0 来开发的，由于 VC 良好的面向对象功能，真正实现 了面向对象的设计。 西安文理学院计算机科学系 课程设计报告 - 2 - 第二章 设计简介及设计方案论述 2.1 程序的主要功能 超长整型数据的存储与运算的主要任务是用计算机对 C 语言和 VB 中对于超 出有符号的长整型数据范围-2147483648 到 2147483647 的数据进行存储与运算， 如加法、减法、乘法、整除以及求余运算，迅速准确地完成对超长整型数据的 计算功能，快速输出运算结果。 2.2 程序设计的思想 2.2.1 运算数据、结果的输入和存储 运算因子超出了整型、实型能表示的范围，肯定不能直接用一个数的形式 来表示。在 C 语言中，能表示多个数的数据类型有两种：数组和字符串。 数组：每个数组元素存储 1 位（在优化时，这里是一个重点！），有多少 位就需要多少个数组元素；用数组表示数的优点：每一位都是数的形式，可以 直接加减；运算时非常方便。用数组表示数的缺点：数组不能直接输入；输入 时每两位数之间必须有分隔符，不符合数值的输入习惯； 字符串：用字符串表示数的优点：能直接输入输出，输入时，每两位数之 间不必分隔符，符合数值的输入习惯；用字符串表示数的缺点：字符串中的每 一位是一个字符，不能直接进行运算，必须先将它转化为数值再进行运算；运 算时非常不方便； 综合以上所述，对上面两种数据结构取长补短：用字符串读入数据，用数 组存储数据： 2.2.2 超长整数加法运算 1、数据的接收和存储 采用字符串输入的方式，设参与运算的两个数分别为 A 和 B，利用字符串 函数把字符串转化为数值，将 A、B 中的每一位数字分别存储在 A、B 两个数组 中，最低位在第一个单元中。 西安文理学院计算机科学系 课程设计报告 - 3 - 2、确定和的位数 设 LA 为 A 的位数，LB 为 B 的位数，则两数之和的位数最大为较大加数位数 加 1，即如果 LALB，则和的位数最大为 LA+1。 3、进位处理 两数相加时，从低位到高位，各位数字分别相加，然后对相加后的数和 10 进 行整除和求余运算，整除之后的值为进位，而余数就等于所求数之和。不断重 复，直到最高位为止。 2.2.3 超长整数减法运算 1、数据的接收和存储 采用字符串输入的方式，设参与运算的两个数分别为 A 和 B，利用字符串函 数把字符串转化为数值，将 A、B 中的每一位数字分别存储在 A、B 两个数组中， 最低位在第一个单元中。 2、确定差的位数 设 LA 为 A 的位数，LB 为 B 的位数，则两数之差的位数最大为较大数的位数， 即如果 LALB，则差的位数最大为 LA。 3、借位处理 做减法运算时，要先判断是否需要借位，如果需要借位，从上一位借过一 个 10，上一位的数减去 1，处理完之后再相减。 2.2.4 超长整数乘法运算 1、数据的接收和存储 采用字符串输入的方式，设参与运算的两个数分别为 A 和 B，利用字符串函 数把字符串转化为数值，将 A、B 中的每一位数字分别存储在 A、B 两个数组中， 最低位在第一个单元中。 2、确定积的位数 设 LA 为 A 的位数，LB 为 B 的位数，乘积的位数最多为 LA+LB，最少为 LA+LB-1。所以，乘积的位数上限为 LA+LB。 3、算法 西安文理学院计算机科学系 课程设计报告 - 4 - 首先计算被乘数与乘数的个位数字的乘积，把结果保存到积数组中，然后 再用被乘数去乘以乘数的十位数字，把结果退一位加到积数组中。每加一次乘 积结果就进行一次进位处理，其方法与加法中的进位处理一样。 2.2.5 超长整数的整除及求余运算 1、数据的接收和存储 采用字符串输入的方式，设参与运算的两个数分别为 A 和 B，利用字符串函 数把字符串转化为数值，将 A、B 中的每一位数字分别存储在 A 和 B 数组中，最 低位在第一个单元中。 2、算法 可以用减法代替除法运算：不断比较 A1n与 B1n的大小，如果 A1n=B1n则商 C1n+1C1n，然后就是一个减法过程：A1n- B1nA1n。由于简单的减法速度太慢，故必须进行优化。设置一个位 置值 J，当 A1nB1n时。B1n左移B0n，j:=j+1，即令 B1n增大 10 倍。这样就减少了减法的次数。当 j0 且 A1n0|f) if(lenalenb) s=lena; else s=lenb; /*用 s 纪录结果的最大位数 */ for(i=0;i=0;i-) printf(“%d“,ci); /*输出结果*/ else jianfa(a,b,1); 西安文理学院计算机科学系 课程设计报告 - 6 - 3.3 超长整数的减法 void jianfa(int a,int b,int f) /*超长整数减法运算*/ int i,u=0,cMAX+1=0,s; if(da*db0|f) if(lenalenb) s=lena; else /*用 s 纪录结果的最大位数*/ s=lenb; for(i=s;ai=0;i-) if(ai1) s-; /*判断最后结果的位数*/ if(f if(da=0;i-) printf(“%d“,ci); else jiafa(a,b,1); 3.4 超长整数的乘法 void chengfa( int a, int b) /*超长整数乘法运算*/ 西安文理学院计算机科学系 课程设计报告 - 7 - int i, j, c2*MAX = 0,s; s = lena + lenb - 1; /*用 s 纪录结果的最大位数*/ for(i = 0; i = 0; i-) printf(“%d“,ci); /*输出结果*/ 3.5 超长整数的整除及求余 /比较两个用字符串存储的超长正整数的大小，若 ab，返回 1；a=b，返回 0；a lenB ? 1 : -1; else return strcmp(a,b); /超长正整数的减法，且被减数大于减数 void cha(char *beijian, char *jian, char *chas) int cBMAX = 0;/用来存储被减数的整型数组 int cJMAX = 0;/用来存储减数的整型数组 int cCMAX = 0;/用来存储两数之差的整型数组 int lenM = strlen(beijian), lenS = strlen(jian);/被减数和减数字符串的长度 int i; /逆序复制减数和被减数到整型数组（因为减法运算是从低位开始） ，保证 cB 大于 cJ for (i=0; i= cJi)/被减数大于减数，直接相减 cCi = cBi - cJi; else /否则要向前借位 cCi = cBi + 10 - cJi; -cBi+1; while (cCi-1 = 0) i-; int j = 0; int k; for (k=i-1; k=0; k-,j+)/逆序存储两数之差到字符串 chas chasj = cCk + 0; chasj = 0; /超长整型数据的整除，求余运算 void chufa(char *beichu, char *chu, char *shang, char *yu) int lenv=strlen(beichu),lens=strlen(chu); if(beichu0=-) da=-1; /判断数组的符号 for(int i=0;i= 0)/连减试商 s+; cha(yu, chu, yu); shangk+ = s + 0;/记录每一位得到的商值 if (strcmp(yu, “0“) = 0) strcpy(yu, “); /使余数的值为空，去掉多余的 0 shangk = 0; /去掉多余的 0 int j; for (i=0; shangi=0; i+) ; for (j=i; j #include #include #include #define MAX 101 void jianfa(int a,int b,int f); / 函数功能：利用字符串实现超长整数减法运算 int lena,lenb,da=1,db=1; /* 把 lena,lenb 设为全局变量,lena 纪录第一个超长整 型数组的位数,lenb 纪录第二个超长整型数组的位数*/ char b1MAX, b2MAX; /*纪录需要计算的两个超长整型数据 */ void input(int a1,int a2) /*函数 input 为输入函数,用来纪录两个待计算的超 长整型数据*/ int i,fa=1,fb=1; printf(“请输入第一个数:n“); scanf ( “%s“, b1); printf(“请输入第二个数：n“); /*输入两个超长整型数据*/ scanf(“%s“,b2); lena = strlen( b1 ); /*lena 纪录 b1 的位数*/ lenb = strlen( b2 ); /*lenb 纪录 b2 的位数*/ if(b10=-) lena-; da=-1;fa=0; /*判断数组的符号*/ if(b20=-) lenb-; db=-1;fb=0; for (i=0; i0|f) if(lenalenb) s=lena; else s=lenb; /*用 s 纪录结果的最大位数*/ for(i=0;i=0;i-) printf(“%d“,ci); /*输出结果*/ else jianfa(a,b,1); void jianfa(int a,int b,int f) /*超长整数减法运算*/ int i,u=0,cMAX+1=0,s; if(da*db0|f) if(lenalenb) s=lena; else /*用 s 纪录结果的最大位数*/ s=lenb; for(i=s;ai=0;i-) if(ai1) s-; /*判断最后结果的位数*/ if(f if(da=0;i-) printf(“%d“,ci); else jiafa(a,b,1); 西安文理学院计算机科学系 课程设计报告 - 16 - void chengfa( int a, int b) /*超长整数乘法运算*/ int i, j, c2*MAX = 0,s; s = lena + lenb - 1; /*用 s 纪录结果的最大位数*/ for(i = 0; i = 0; i-) printf(“%d“,ci); /*输出结果*/ /比较两个用字符串存储的超长正整数的大小，若 ab，返回 1；a=b，返回 0；a lenB ? 1 : -1; else return strcmp(a,b); /超长正整数的减法，且被减数大于减数 void cha(char *beijian, char *jian, char *chas) int cBMAX = 0;/用来存储被减数的整型数组 int cJMAX = 0;/用来存储减数的整型数组 int cCMAX = 0;/用来存储两数之差的整型数组 int lenM = strlen(beijian), lenS = strlen(jian);/被减数和减数字符串的长度 int i; /逆序复制减数和被减数到整型数组（因为减法运算是从低位开始） ，保证 cB 大于 cJ for (i=0; i= cJi)/被减数大于减数，直接相减 cCi = cBi - cJi; else /否则要向前借位 cCi = cBi + 10 - cJi; -cBi+1; w