超长整数及存储与运算设计说明书.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 can t 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 2 课程目的 学习并掌握计算机对于整型数据的存储与运算方法及原理 并能够运用 C 语言来编写程序 实现超长整型数据的存储与运算 解决科学计算与实际生活 中的相关问题 1 3 课程意义 1 掌握超长整数的计算基本方法并能应用 2 掌握超长整数加法 超长整数减法 超长整数乘法 3 掌握超长整数除法运算中被除数 除数 商和余数之间的关系 4 分析总结常用超长整数算法特点 并能编写相应的程序 5 在学习的过程中应强化 算法领先 的意识 根据实际情况对超长整数运算 进行优化的策略与方法 1 4 课程设计采取的基本原理和主要技术方法 本程序是专门针对超长整型数据而开发的一个功能齐全 操作简单的存储 与运算程序 本程序实现以下基本功能 操作人员可以对超长整型数据进行存 储 还可以对所输入的数据进行准确的加减乘以及整除求余运算 本系统使用的是 VC6 0 来开发的 由于 VC 良好的面向对象功能 真正实现 了面向对象的设计 第二章 设计简介及设计方案论述 2 1 程序的主要功能 超长整型数据的存储与运算的主要任务是用计算机对 C 语言和 VB 中对于超 出有符号的长整型数据范围 2147483648 到 2147483647 的数据进行存储与运算 如加法 减法 乘法 整除以及求余运算 迅速准确地完成对超长整型数据的 计算功能 快速输出运算结果 2 2 程序设计的思想 2 2 1 运算数据 结果的输入和存储 运算因子超出了整型 实型能表示的范围 肯定不能直接用一个数的形式 来表示 在 C 语言中 能表示多个数的数据类型有两种 数组和字符串 数组 每个数组元素存储 1 位 在优化时 这里是一个重点 有多少 位就需要多少个数组元素 用数组表示数的优点 每一位都是数的形式 可以 直接加减 运算时非常方便 用数组表示数的缺点 数组不能直接输入 输入 时每两位数之间必须有分隔符 不符合数值的输入习惯 字符串 用字符串表示数的优点 能直接输入输出 输入时 每两位数之 间不必分隔符 符合数值的输入习惯 用字符串表示数的缺点 字符串中的每 一位是一个字符 不能直接进行运算 必须先将它转化为数值再进行运算 运 算时非常不方便 综合以上所述 对上面两种数据结构取长补短 用字符串读入数据 用数 组存储数据 2 2 2 超长整数加法运算 1 数据的接收和存储 采用字符串输入的方式 设参与运算的两个数分别为 A 和 B 利用字符串 函数把字符串转化为数值 将 A B 中的每一位数字分别存储在 A B 两个数组 中 最低位在第一个单元中 2 确定和的位数 设 LA 为 A 的位数 LB 为 B 的位数 则两数之和的位数最大为较大加数位数 加 1 即如果 LA LB 则和的位数最大为 LA 1 3 进位处理 两数相加时 从低位到高位 各位数字分别相加 然后对相加后的数和 10 进 行整除和求余运算 整除之后的值为进位 而余数就等于所求数之和 不断重 复 直到最高位为止 2 2 3 超长整数减法运算 1 数据的接收和存储 采用字符串输入的方式 设参与运算的两个数分别为 A 和 B 利用字符串函 数把字符串转化为数值 将 A B 中的每一位数字分别存储在 A B 两个数组中 最低位在第一个单元中 2 确定差的位数 设 LA 为 A 的位数 LB 为 B 的位数 则两数之差的位数最大为较大数的位数 即如果 LA LB 则差的位数最大为 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 算法 首先计算被乘数与乘数的个位数字的乘积 把结果保存到积数组中 然后 再用被乘数去乘以乘数的十位数字 把结果退一位加到积数组中 每加一次乘 积结果就进行一次进位处理 其方法与加法中的进位处理一样 2 2 5 超长整数的整除及求余运算 1 数据的接收和存储 采用字符串输入的方式 设参与运算的两个数分别为 A 和 B 利用字符串函 数把字符串转化为数值 将 A B 中的每一位数字分别存储在 A 和 B 数组中 最 低位在第一个单元中 2 算法 可以用减法代替除法运算 不断比较 A 1 n 与 B 1 n 的大小 如果 A 1 n B 1 n 则商 C 1 n 1 C 1 n 然后就是一个减法过程 A 1 n B 1 n A 1 n 由于简单的减法速度太慢 故必须进行优化 设置一个位 置值 J 当 A 1 n B 1 n 时 B 1 n 左移 B 0 n j j 1 即令 B 1 n 增大 10 倍 这样就减少了减法的次数 当 j 0 且 A 1 n B 0 n 时 B 0 n 右移 B 0 n j j 1 即令 B 1 n 缩小 10 倍 第三章 详细设计 3 1 超长整型数据的输入 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 b1 0 lena da 1 fa 0 判断数组的符号 if b2 0 lenb db 1 fb 0 for i 0 i lena i fa a1 i b1 lena fa 0 把字符形数据 b1 转为整 数形数据 同样用数组纪录 for i 0 i0 f if lena lenb s lena else s lenb 用 s 纪录结果的最大位数 for i 0 i s i c i a i b i c i c i 1 int c i 10 c i 1 代表进位 c i int c i 10 超长整数加法运算过程 if c s s 判断最后结果的位数 if da 0i printf d c i 输出结果 else jianfa a b 1 3 3 超长整数的减法 void jianfa int a int b int f 超长整数减法运算 int i u 0 c MAX 1 0 s if da db 0 f if lena lenb s lena else 用 s 纪录结果的最大位数 s lenb for i s a i 0 i if a i b i u 1 u 纪录结果符号 if u 超长整数减法运算过程 for i 0 i s i if a i b i a i 1 a i 10 c i a i b i else 当 a b 时的处理 for i 0 i s i if b i 1 s 判断最后结果的位数 if f if da 0i printf d c i else jiafa a b 1 3 4 超长整数的乘法 void chengfa int a int b 超长整数乘法运算 int i j c 2 MAX 0 s s lena lenb 1 用 s 纪录结果的最大位数 for i 0 i lena i 超长整数乘法运算过程 for j 0 j lenb j c i j a i b j c i j c i j 1 c i j 10 c i j 1 c i j c i j 10 while c s s 判断最后结果的位数 if da db 0 i printf d c i 输出结果 3 5 超长整数的 整除及求余 比较两个用字符串存储的超长正整数的大小 若 a b 返回 1 a b 返回 0 a lenB 1 1 else return strcmp a b 超长正整数的减法 且被减数大于减数 void cha char beijian char jian char chas int cB MAX 0 用来存储被减数的整型数组 int cJ MAX 0 用来存储减数的整型数组 int cC MAX 0 用来存储两数之差的整型数组 int lenM strlen beijian lenS strlen jian 被减数和减数字符串的长度 int i 逆序复制减数和被减数到整型数组 因为减法运算是从低位开始 保证 cB 大于 cJ for i 0 i lenM i cB i beijian lenM 1 i 0 for i 0 i lenS i cJ i jian lenS 1 i 0 for i 0 i cJ i 被减数大于减数 直接相减 cC i cB i cJ i else 否则要向前借位 cC i cB i 10 cJ i cB i 1 while cC i 1 0 i int j 0 int k for k i 1 k 0 k j 逆序存储两数之差到字符串 chas chas j cC k 0 chas j 0 超长整型数据的整除 求余运算 void chufa char beichu char chu char shang char yu int lenv strlen beichu lens strlen chu if beichu 0 da 1 判断数组的符号 for int i 0 i lenv i beichu i beichu i 1 lenv if chu 0 db 1 for int i 0 i lens i chu i chu i 1 lens if Compare beichu chu 0 被除数等于除数 strcpy shang 1 strcpy yu 0 return if strcmp chu 0 0 Compare beichu chu 0 连减试商 s cha yu chu yu shang k s 0 记录每一位得到的商值 if strcmp yu 0 0 strcpy yu 使余数的值为空 去掉多余的 0 shang k 0 去掉多余的 0 int j for i 0 shang i 0 i for j i j k j shang j i shang j 第四章 设计结果及分析 4 1 设计概述 在不大于 10101 1 的整数范围内进行存储与运算 有必要对数据的正负性进 行判断 因而程序在总体上应包含正整数与负整数的存储与运算 正负性的判 断与运算是本程序体系结构设计的核心 同样对数据的整除求余运算也同样是 本设计的一个难点 因为在整除求余运算中采用的是竖式计算的方法 当中还 调用了减法的子函数 无论是设计还是运算都比较复杂 4 2 设计约束 本程序必须实现对在 10101 1 范围内的所有超长整数的存储与运算 超出这 个数据范围则程序停止运行 4 3 运行流程 1 输入数据 2 数据存储 3 条件判断 4 进行运算 5 输出结果 总 结 此次课程设计对于我个人来说具有很重大的意义 我学到了很多关于数据 存储与运算方面的知识 掌握了一些课程设计的方法与思想 了解了毕业设计 的一些制作流程 同时这也是我第一次参加团队项目设计 它不仅锻炼了我的 思维以及程序开发能力 也使我充分认识到了团队合作的重要性 为我以后的 求学之路打下了深厚的基础 在此次编程开发过程中我深刻地体会到了自学能力的重要性 毕竟平时在 课堂上学到的东西都是有限的 而且也只是一味的去接受 并不能主动地去思考 其实在真正的设计实践过程中还需要我们不断的去努力去学习 才能使该程序完 成预期的目标 在本次课程设计中我花费了大量的时间借助图书和网络查阅了 很多的相关资料 并和身边的同学进行了反复的讨论与研究 经过不断的思考和 改进 初步完成了超长整型数据的存储与运算的设计目标 用于解决实际问题 由于我自身的学识有限 加之时间比较仓促 使得此程序可能存在某些不 足之处 真诚的欢迎老师 同学提出宝贵的意见 我将认真听取 改正努力提 高自己 致 谢 在课程设计完成之际 我首先要向指导老师张岗亭表示最真挚的谢意 张 老师认真负责的工作态度 严谨的治学精神和深厚的理论水平都使我收益匪浅 无论在理论上还是在实践中 都给予了我们很大的帮助 使我得到不少的提高 这对于我们以后的工作和学习都是一种巨大的帮助 感谢他耐心的辅导 感谢系里给予的这次课程设计实践机会 感谢院系领导们和老师们的关心 与帮助 同时还要感谢 08 级软件工程 2 班所有同学给予我的帮助 感谢我们这 个小组的协同合作 正是有了这些帮助才使得我能够顺利的完成这次的课程设 计 参考文献 1 吴金平 Visual C 6 0 编程与实践 M 北京 中国水利水电出版社 2004 2 官章权 Visual C 6 0 高级编程范例 M 北京 电子工业出版社 2002 3 王萍 C 面向对象程序设计 M 北京 清华大学出版社 2002 4 杨路明等 C C 程序设计教程 M 湖南 湖南科技出版社 2001 5 谭浩强 C 程序设计 第三版 M 北京 清华大学出版社 2010 6 严蔚敏 吴伟民 数据结构 M 北京 高等教育出版社 2004 附录 include 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 b1 MAX b2 MAX 纪录需要计算的两个超长整型数据 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 b1 0 lena da 1 fa 0 判断数组的符号 if b2 0 lenb db 1 fb 0 for i 0 i lena i fa a1 i b1 lena fa 0 把字符形数据 b1 转 为整数形数据 同样用数组纪录 for i 0 i0 f if lena lenb s lena else s lenb 用 s 纪录结果的最大位数 for i 0 i s i c i a i b i c i c i 1 int c i 10 c i 1 代表进位 c i int c i 10 超长整数加法运算过程 if c s s 判断最后结果的位数 if da 0i printf d c i 输出结果 else jianfa a b 1 void jianfa int a int b int f 超长整数减法运算 int i u 0 c MAX 1 0 s if da db 0 f if lena lenb s lena else 用 s 纪录结果的最大位数 s lenb for i s a i 0 i if a i b i u 1 u 纪录结果符号 if u 超长整数减法运算过程 for i 0 i s i if a i b i a i 1 a i 10 c i a i b i else 当 a b 时的处理 for i 0 i s i if b i 1 s 判断最后结果的位数 if f if da 0i printf d c i else jiafa a b 1 void chengfa int a int b 超长整数乘法运算 int i j c 2 MAX 0 s s lena lenb 1 用 s 纪录结果的最大位数 for i 0 i lena i 超长整数乘法运算过程 for j 0 j lenb j c i j a i b j c i j c i j 1 c i j 10 c i j 1 c i j c i j 10 while c s s 判断最后结果的位数 if da db 0 i printf d c i 输出结果 比较两个用字符串存储的超长正整数的大小 若 a b 返回 1 a b 返回 0 a lenB 1 1 else return strcmp a b 超长正整数的减法 且被减数大于减数 void cha char beijian char jian char chas int cB MAX 0 用来存储被减数的整型数组 int cJ MAX 0 用来存储减数的整型数组 int cC MAX 0 用来存储两数之差的整型数组 int lenM strlen beijian lenS strlen jian 被减数和减数字符串的长度 int i 逆序复制减数和被减数到整型数组 因为减法运算是从低位开始 保证 cB 大于 cJ for i 0 i lenM i cB i beijian lenM 1 i 0 for i 0 i lenS i cJ i jian lenS 1 i 0 for i 0 i cJ i 被减数大于减数 直接相减 cC i cB i cJ i else 否则要向前借位 cC i cB i 10 cJ i cB i 1 while cC i 1 0 i int j 0 int k for k i 1 k 0 k j 逆序存储两数之差到字符串 chas chas j cC k 0 chas j 0 超长整型数据的整除 求余运算 void chufa char beichu char chu char shang char yu int lenv strlen beichu lens strlen chu if beichu 0 da 1 判断数组的符号 for int i 0 i lenv i beichu i beichu i 1 lenv if chu 0 db 1 for int i 0 i lens i chu i chu i 1 lens if Compare beichu chu 0 被除数等于除数 strcpy shang 1 strcpy yu 0 return if strcmp chu 0 0 Compare beichu chu 0 连减试商 s cha yu chu yu shang k s 0 记录每一位得到的商值 if strcmp yu 0 0 strcpy yu 使余数的值为空 去掉多余的 0 shang k 0 去掉多余的 0 int j for i 0 shang i 0 i for j i j k j shang j i shang j void main int a MAX 0 b MAX 0 input a b printf n 两者之和 n b1 b2 jiafa a b 0 printf n 两者之差 n b1 b2 jianfa a b 0 printf n 两者之积 n b1 b2 chengfa a b printf n getchar char c MAX 0 d MAX 0 chufa b1 b2 c d puts 两者之商 if da db 0 puts c puts 余数 puts d system pause