C++ 高精度乘法.ppt

高精度问题 高精度运算 所谓的高精度运算 是指参与运算的数 加数 减数 因子 范围大大超出了标准数据类型 整型 实型 能表示的范围的运算 这个时候只能用数组来表示参与运算的数字 那么他们的运算也就不能简单的直接进行了 高精度加法1553 Description输入两个整数x y 输出它们的和 Input输入两个整数x y 0 x y 10 100 Output输出它们的和SampleInput123234SampleOutput357 高精度加法 高精度运算主要解决以下三个问题 1 加数 减数 运算结果的输入和存储2 运算过程3 结果输出 高精度加法 数字的输入和存储1 运算因子超出了整型 实型能表示的范围 肯定不能直接用一个数的形式来表示 能表示多个数的数据类型有两种 数组和字符串 1 数组 每个数组元素存储1位 在优化时 这里是一个重点 有多少位就需要多少个数组元素 用数组表示数的优点 每一位都是数的形式 可以直接加减 运算时非常方便用数组表示数的缺点 数组不能直接输入 输入时每两位数之间必须有分隔符 不符合数值的输入习惯 2 字符串 字符串的最大长度是255 可以表示255位 用字符串表示数的优点 能直接输入输出 输入时 每两位数之间不必分隔符 符合数值的输入习惯 用字符串表示数的缺点 字符串中的每一位是一个字符 不能直接进行运算 必须先将它转化为数值再进行运算 运算时非常不方便 3 因此 综合以上所述 对上面两种数据结构取长补短 用字符串读入数据 用数组存储数据 高精度加法 数据输入和存储Strings1 s2 Inta 101 0 b 101 0 Cin s1 s2 Inti j 0 For i s1 length i 0 i j a i s1 j 0 For i s2 length j 0 i 0 i j b i s2 j 0 用数组a b分别存储s1 s2并且将其字符转换为数值 不过存储时是倒序存放 高精度加法 运算过程 1 运算顺序 两个数靠右对齐 从低位向高位运算 先计算低位再计算高位 2 运算规则 同一位的两个数相加再加上从低位来的进位 成为该位的和 这个和去掉向高位的进位就成为该位的值 如上例 8 2 10 向前一位进1 本位的值是0 可借助MOD DIV运算完成这一步 3 最后一位的进位 如果完成两个数的相加后 进位位值不为0 则应添加一位 4 如果两个加数位数不一样多 则按位数多的一个进行计算 高精度加法 运算过程 intc 1000 0 For i 1 i max s1 length s2 length i c i a i b i 10 c i c i 1 a i b i 10 进位 因为存放s1 s2两个数到数组a b中时 我们是倒序存放也就是个位存放在a 1 和b 1 中 因此我们从a 1 和b 1 开始每位求和其实已经完成了按位对齐的这一步 高精度加法 输出结果 按数组c中的实际使用的位数倒序输出 if c i 1 i i 1 判断最高位相加之后是否还向上进位For i 1 i cout c i 高精度乘法 1 高精度 单精度For i 1 i s1 length i c i a i b b为乘数 求出每位上的乘积For i 1 i s1 length i c i 1 c i 10 c i 1 求出进位c i c i 10 求出每位上数 高精度乘法 2 高精度 高精度 i 1 3 j 1 2 高精度乘法 2 高精度 高精度For i 1 i s1 length i for j 1 j s2 length j c j i 1 a i b j For i 1 i s1 length s2 length 1 i c i 1 c i 10 c i c i 10 高精度除法 1 高精度 单精度 模拟自然除法 每一位除以数b求商 反复减去b 记录下循环的次数 当该位数值小于数b时 责循环次数即为该位上的商 然后将余数乘上10加下一