高精度计算.ppt

高精度计算 Four 本讲主要内容 例题 ai2981大整数加法例题 ai2736大整数减法例题 ai2980大整数乘法例题 ai2737大整数除法例题 ai2952循环数 C C 中数的表示范围 int 2 31 2 31 1 即 2147483648 2147483647unsigned 0 2 32 1 即0 4294967295如何处理一个200位的整数 double 64位如何精确到小数点后100位 用数组来存放和表示 一个数组元素存放大整数的一位 例题 ai2981大整数加法问题描述求两个不超过200位的非负整数的和 输入数据有两行 每行是一个不超过200位的非负整数 没有多余的前导0 输出要求一行 即相加后的结果 结果里不能有多余的前导0 即如果结果是342 那么就不能输出为0342 输入样例2222222222222222222233333333333333333333输出样例55555555555555555555 例题 ai2981大整数加法解题思路1 用字符型或整型数组来存放大整数an 0 存放个位数 an 1 存放十位数 an 2 存放百位数 2 模拟小学生列竖式做加法 从个位开始逐位相加 超过或达到10则进位 用intan1 201 保存第一个数 用intan2 200 表示第二个数 然后逐位相加 相加的结果直接存放在an1中 要注意处理进位 include include defineMAX LEN201intan1 MAX LEN 10 intan2 MAX LEN 10 charszLine1 MAX LEN 10 charszLine2 MAX LEN 10 intAdd intnMaxLen int an1 int an2 将长度最多为nMaxLen的大整数an1和an2相加 结果放在an1 an1 0 an2 0 对应于个位 返回值为最高位数 intnHighestPos 0 for inti 0 i 10 看是否要进位an1 i 10 an1 i 1 进位 if an1 i nHighestPos i 记录最高位的位置 returnnHighestPos intmain scanf s szLine1 scanf s szLine2 库函数memset将地址an1开始的sizeof an1 字节内容置成0 sizeof an1 的值就是an1的长度 memset函数在string h中声明memset an1 0 sizeof an1 memset an2 0 sizeof an2 下面将szLine1中存储的字符串形式的整数转换到an1中去 an1 0 对应于个位inti j intnLen1 strlen szLine1 j 0 for i nLen1 1 i 0 i an1 j szLine1 i 0 j intnLen2 strlen szLine2 j 0 for i nLen2 1 i 0 i an2 j szLine2 i 0 intnHighestPos Add MAX LEN an1 an2 for i nHighestPos i 0 i printf d an1 i return0 例题 ai2736大整数减法问题描述求2个大的正整数相减的差 输入数据第1行是测试数据的组数n 每组测试数据占2行 第1行是被减数a 第2行是减数b a b 每组测试数据之间有一个空行 每行数据不超过100个字符 输出要求n行 每组测试数据有一行输出是相应的整数差 例题 ai2736大整数减法输入样例29999999999999999999999999999999999999999999999999954096567750978508956870567980689709345465465756767686784354353451输出样例99999999999999999999999900000000000005409656775097850895687056798068970934546546575676768678435435344 include include defineMAX LEN110intan1 MAX LEN intan2 MAX LEN charszLine1 MAX LEN charszLine2 MAX LEN intSubstract intnMaxLen int an1 int an2 两个最多nMaxLen位的大整数an1减去an2 an1保证大于an2intnStartPos 0 for inti 0 i nMaxLen i an1 i an2 i 逐位减if an1 i 0 看是否要借位an1 i 10 an1 i 1 借位 if an1 i nStartPos i 记录最高位的位置 returnnStartPos 返回值是结果里面最高位的位置 intmain intn scanf d 例题 ai2980大整数乘法问题描述求两个不超过200位的非负整数的积 输入数据有两行 每行是一个不超过200位的非负整数 没有多余的前导0 输出要求一行 即相乘后的结果 结果里不能有多余的前导0 即如果结果是342 那么就不能输出为0342 输入样例1234567890098765432100输出样例1219326311126352690000 解题思路用unsignedan1 200 和unsignedan2 200 分别存放两个乘数 用aResult 400 来存放积 计算的中间结果也都存在aResult中 aResult长度取400是因为两个200位的数相乘 积最多会有400位 an1 0 an2 0 aResult 0 都表示个位 一个数的第i位和另一个数的第j位相乘所得的数 一定是要累加到结果的第i j位上 这里i j都是从右往左 从0开始数 计算的过程基本上和小学生列竖式做乘法相同 为编程方便 并不急于处理进位 而将进位问题留待最后统一处理 现以835 49为例来说明程序的计算过程 先算835 9 5 9得到45个1 3 9得到27个10 8 9得到72个100 由于不急于处理进位 所以835 9算完后 aResult如下 接下来算5 4 此处5 4的结果代表20个10 因此要aResult 1 20 变为 再下来算3 4 此处3 4的结果代表12个100 因此要aResult 2 12 变为 最后算8 4 此处8 4的结果代表32个1000 因此要aResult 3 32 变为 835 49 乘法过程完毕 接下来从aResult 0 开始向高位逐位处理进位问题 835 49 aResult 0 留下5 把4加到aResult 1 上 aResult 1 变为51后 应留下1 把5加到aResult 2 上 最终使得aResult里的每个元素都是1位数 结果就算出来了 include include defineMAX LEN200unsignedan1 MAX LEN 10 unsignedan2 MAX LEN 10 unsignedaResult MAX LEN 2 10 charszLine1 MAX LEN 10 charszLine2 MAX LEN 10 intmain gets szLine1 gets函数读取一行gets szLine2 inti j memset an1 0 sizeof an1 memset an2 0 sizeof an2 memset aResult 0 sizeof aResult intnLen1 strlen szLine1 j 0 for i nLen1 1 i 0 i an1 j szLine1 i 0 intnLen2 strlen szLine2 j 0 for i nLen2 1 i 0 i an2 j szLine2 i 0 每一轮都用an2的一位 去和an1各位相乘 从an2的个位开始for i 0 i 10 aResult i 1 aResult i 10 aResult i 10 if aResult i nHighestPos i for i nHighestPos i 0 i printf d aResult i return0 求2个大的正整数相除的商Input第1行是测试数据的组数n 每组测试数据占2行 第1行是被除数 第2行是除数 每组测试数据之间有一个空行 每行数据不超过100个字符Outputn行 每组测试数据有一行输出是相应的整数商 例题 ai2737大整数除法 SampleInput324053373129633733590092604577420574392304964939303555957976607910827396462987192585318701752584429931160870372907079248971095012509790550883793197894100000000000000000000000000000000000000001000000000054096567750978508956870567980689709345465465756767686784354353451SampleOutput010000000000000000000000000000005409656775097850895687056798068970934546546575676768678435435345 例题 ai2737大整数除法求两个大的正整数相除的商基本的思想是反复做减法 看看从被除数里最多能减去多少个除数 商就是多少 一个一个减显然太慢 如何减得更快一些呢 以7546除以23为例来看一下 开始商为0 先减去23的100倍 就是2300 发现够减3次 余下646 于是商的值就增加300 然后用646减去230 发现够减2次 余下186 于是商的值增加20 最后用186减去23 够减8次 因此最终商就是328 所以本题的核心是要写一个大整数的减法函数 然后反复调用该函数进行减法操作 include include defineMAX LEN110intan1 MAX LEN intan2 MAX LEN inttmpAn2 MAX LEN intanResult MAX LEN charszLine1 MAX LEN charszLine2 MAX LEN charszNouse MAX LEN intSubstract intnMaxLen int an1 int an2 大整数an1减去an2 两者最多nMaxLen位 an1必须不小于an2 差放在an1里 返回差的最高非0位的位置 intnStartPos 0 for inti 0 i nMaxLen i an1 i an2 i 逐位相减if an1 i 0 看是否要进位an1 i 10 an1 i 1 借位 if an1 i nStartPos i 记录最高位的位置 returnnStartPos intLength intnMaxLen int an 求大整数的位数 0算0位 inti for i nMaxLen 1 an i 0 int Max intnMaxLen int an1 int an2 求大整数an1和an2里面大的那个 若an1 an2 返回an1 如果都是0 则返回NULL boolbBothZero true for inti nMaxLen 1 i 0 i if an1 i an2 i returnan1 elseif an1 i an2 i returnan2 elseif an1 i bBothZero false if bBothZero returnNULL elsereturnan1 intmain intn scanf d intnHighestPos 0 memset anResult 0 sizeof anResult intnShiftLen Length MAX LEN an1 Length MAX LEN an2 只要an1大于an2 就不停相减while Max MAX LEN an1 an2 an1 算出an1的10的nShiftLen次方倍ShiftLeft MAX LEN an2 tmpAn2 nShiftLen 重复减去an1的10的nShiftLen次方倍 看能减几次while Max MAX LEN an1 tmpAn2 an1 Substract MAX LEN an1 tmpAn2 记录商对应位anResult nShiftLen 记录结果最高位的位置if nHighestPos 0 高精度计算需要注意的几个问题 大整数的读入不能用数值型的读入方式用字符串的读入方式 再按字符分别转成数字计算过程中考虑进位和借位问题 先不急于处理 在计算结束时处理 输出时注意跳过高位时多余的0数组需要稍微大一些 避免运算时溢出 例题 ai2952循环数 问题描述当一个N位的整数X满足下列条件时 称其为循环数 X与任意一个整数Y 1 Y N 相乘时 都将产生一个X的 循环 即 分别将这两个整数 X和X Y 的第1位数字与最后1位数字连在一起 可以得到一个相同的数字循环 当然两个整数在该数字循环中的起始位置不同 例如 142857是一个循环数142857 1 142857142857 2 285714142857 3 428571142857 4 571428142857 5 714285142857 6 857142 输入写一个程序判断一个整数是否是循环数 输入文件是一个整数序列 每个整数长度为2 60 注意 每个整数前面的零被看作是该整数的一部分 在计算N时要统计 例如 01 是一个2位的整数 而 1 是一个1位的整数 输出对每个输入整数 输出一行 说明该整数是否是循环数 样例输入142857142856142858010588235294117647样例输出142857iscyclic142856isnotcyclic142858isnotcyclic01isnotcyclic0588235294117647iscyclic 解题思路 高精度的乘法 整数可能达60位X 1 Y1 X X 2 Y2 Y1 XX 3 Y3 Y2 X Yi是否是X的 循环 解题思路 Yi是否是X的 循环 穷举 N位整数 循环移