C语言 大数四则运算.ppt

超大数的四则运算 各类型的范围 int 16位 32768 32767 注 现在大多数的编译器的int型是32位的也就是说跟long型的大小一样 longlong或 int64 64位 9223372036854775808 9223372036854775807float 32位 精确到小数点后6 7位double 64位 精确到小数点后15 16位 注 平时做题时都把浮点型数据定义为double型避免精度不够出错 请计算 1 2的1000次幂2 2的10000次幂3 123456789012345678912345678903453434534534535345434543乘上93874293874928734928734028034820938479288374892733453453534 主要内容 数字存储的实现 大数计算的因数和结果精度一般是少则数十位 多则几万位 在C C 语言中定义的类型中精度最多只有二十多位 一般我们称这种基本数据类型无法表示的整数为大整数 如何表示和存放大整数呢 基本的思想就是 用数组存放和表示大整数 一个数组元素 存放大整数中的一位 比如 1664434318 下标 加法运算的实现 加数 被加数 初始化进位为0 各对应位相加后再加上进位数 1 进位为1 0 3 进位为1 5 4 进位为1 2 由低位向高位相加计算 直至所有运算结束 理中注意问题 判断最后数组的长度 去掉前导零 大数加法 voidAdd chars1 chars2 参数为两个字符串数组 intnum1 M num2 M inti j len1 strlen s1 len2 strlen s2 for i len1 1 j 0 i 0 i num1 0 保存的是低位num1 j s1 i 0 for i len2 1 j 0 i 0 i num2 j s2 i 0 for i 0 i9 num1 i 10 num1 i 1 for i M 1 i 0 减法运算的实现 算法也是从低位开始减 先要判断减数和被减数那一个位数长 减数位数长是正常减 被减数位数长 则被减数减减数 最后还要加上负号 两数位数长度相等时 最好比那一个数字大 否则负号处理会很繁琐 处理每一项时要 如果前一位相减有借位 就先减去上一位的借位 无则不减 再去判断是否能够减开被减数 如果减不开 就要借位后再去减 同时置借位为1 否则置借位为0 减法运算的实现 减数 被减数 初始化借位为0 各对应位相减后再减上借位数 1 借位为1 9 2 借位为1 6 3 借位为0 0 4 借位为0 2 由低位向高位相加计算 直至所有运算结束 处理中注意问题 乘法运算的实现 首先说一下乘法计算的算法 从低位向高位乘 在竖式计算中 我们是将乘数第一位与被乘数的每一位相乘 记录结果 之后 用第二位相乘 记录结果并且左移一位 以此类推 直到计算完最后一位 再将各项结果相加 得出最后结果 计算的过程基本上和小学生列竖式做乘法相同 为编程方便 并不急于处理进位 而将进位问题留待最后统一处理 ans i j a i b j 现以835 49为例来说明程序的计算过 先算835 9 5 9得到45个1 3 9得到27个10 8 9得到72个100 由于不急于处理进位 所以835 9算完后 aResult如下 接下来算4 5 此处4 5的结果代表20个10 因此要aResult 1 20 变为 再下来算4 3 此处4 3的结果代表12个100 因此要aResult 2 12 变为 最后算4 8 此处4 8的结果代表32个1000 因此要aResult 3 32 变为 乘法过程完毕 接下来从aResult 0 开始向高位逐位处理进位问题 aResult 0 留下5 把4加到aResult 1 上 aResult 1 变为51后 应留下1 把5加到aResult 2 上 最终使得aResult里的每个元素都是1位数 结果就算出来了 总结一个规律 即一个数的第i位和另一个数的第j位相乘所得的数 一定是要累加到结果的第i j位上 这里i j都是从右往左 从0开始数 ans i j a i b j 处理中注意问题 大数乘法 voidMulti charstr1 charstr2 intlen1 len2 i j inta MAX 10 b MAX 10 c MAX 2 10 memset a 0 sizeof a memset b 0 sizeof b memset c 0 sizeof c len1 strlen str1 for j 0 i len1 1 i 0 i 把数字倒过来a j str1 i 0 len2 strlen str2 for j 0 i len2 1 i 0 i 倒转第二个整数b j str2 i 0 for i 0 i len2 i 用第二个数乘以第一个数 每次一位for j 0 j len1 j c i j b i a j 先乘起来 后面统一进位 for i 0 i 10 c i 1 c i 10 c i 10 for i MAX 2 c i 0 除法运算的实现 首先说一下我们所要的结果 当除数除不开被子除数时 不用除到小数 当除数小于被除数时 除数作为余数既可 不用再向下除了 基本思路 基本的思想是反复做减法 看看从被除数里最多能减去多少个除数 商就是多少 一个一个减显然太慢 如何减得更快一些呢 以7546除以23为例来看一下 开始商为0 先减去23的100倍 就是2300 发现够减3次 余下646 于是商的值就增加300 然后用646减去230