加入收藏 | 设为首页 | 会员中心 | 我要投稿 李大同 （https://www.lidatong.com.cn/）- 科技、建站、经验、云计算、5G、大数据,站长网!
当前位置： 首页 > 大数据 > 正文

7、大数，高精度计算---大数除法

发布时间：2020-12-14 03:32:14 所属栏目：大数据 来源：网络整理
导读：大数是算法语言中的数据类型无法表示的数，其位数超过最大数据类型所能表示的范围，所以，在处理大数问题时首先要考虑的是怎样存储大数，然后是在这种存储方式下其处理的实现方法。 一般情况下大数的存储是采用字符数组来存储，即将大数当作一个字符串来存储

大数是算法语言中的数据类型无法表示的数，其位数超过最大数据类型所能表示的范围，所以，在处理大数问题时首先要考虑的是怎样存储大数，然后是在这种存储方式下其处理的实现方法。

一般情况下大数的存储是采用字符数组来存储，即将大数当作一个字符串来存储，而对其处理是按其处理规则在数组中模拟实现。

?四 大数除法。

?

大数除法，应该算是四则运算里面最难的一种了。不同于一般的模拟，除法操作步数模仿手工除法，而是利用减法操作实现的。

其基本思想是反复做除法，看从被除数里面最多能减去多少个除数，商就是多少。

逐个减显然太慢，要判断一次最多能减少多少个整的10的n次方。

以7546除23为例。

先减去23的100倍，就是2300，可以减3次，余下646。?? 此时商就是300；

然后646减去23的10倍，就是230，可以减2次，余下186。此时商就是320；

然后186减去23，可以减8次，此时商就是328.

?

根据这个思想，不难写出下面的代码。

还是那句话，可能算法效率不是很高。但是常规解题思路一般就是这样了。

如果以后有能力，有时间了。? 我会试着去优化。

?

ps：大数系列学习资源来自 <c程序设计竞赛实训教程>一书和一些大牛的博客。

?

[cpp]? view plain copy
  1. #include<stdio.h>??
  2. #include<string.h>??
  3. #include<stdlib.h>??
  4. #define?MaxLen?200??
  5. //函数SubStract功能：??
  6. //用长度为len1的大整数p1减去长度为len2的大整数p2??
  7. //?结果存在p1中，返回值代表结果的长度??
  8. //不够减?返回-1?正好够?返回0??
  9. int?SubStract(?int?*p1,?int?*p2,87); background-color:inherit; font-weight:bold">int?len1,87); background-color:inherit; font-weight:bold">int?len2?)??
  10. {??
  11. ????int?i;??
  12. ????if(?len1?<?len2?)??
  13. ????????return?-1;??
  14. if(?len1?==?len2?)??
  15. ????{????????????????????????//判断p1?>?p2??
  16. ????????for(?i=len1-1;?i>=0;?i--?)??
  17. ????????{??
  18. ????????????if(?p1[i]?>?p2[i]?)???//若大，则满足条件，可做减法??
  19. ????????????????break;??
  20. else?if(?p1[i]?<?p2[i]?)?//否则返回-1??
  21. ????????}??
  22. ????}??
  23. for(?i=0;?i<=len1-1;?i++?)??//从低位开始做减法??
  24. ????{??
  25. ????????p1[i]?-=?p2[i];??
  26. if(?p1[i]?<?0?)??????????//若p1<0，则需要借位??
  27. ????????{??
  28. ????????????p1[i]?+=?10;?????????//借1当10??
  29. ????????????p1[i+1]--;???????????//高位减1??
  30. ????????}??
  31. ????}??
  32. ????for(?i=len1-1;?i>=0;?i--?)???????//查找结果的最高位??
  33. if(?p1[i]?)??????????????????//最高位第一个不为0??
  34. ????????????return?(i+1);???????//得到位数并返回??
  35. return?0;??????????????????//两数相等的时候返回0??
  36. }??
  37. int?main()??
  38. {??
  39. ????int?n,?k,?i,?j;?????????????//n:测试数据组数??
  40. //大数位数??
  41. int?nTimes;?????????????????//两大数相差位数??
  42. int?nTemp;??????????????????//Subtract函数返回值??
  43. int?num_a[MaxLen];??????????//被除数??
  44. int?num_b[MaxLen];??????????//除数??
  45. int?num_c[MaxLen];??????????//商??
  46. char?str1[MaxLen?+?1];??????//读入的第一个大数??
  47. char?str2[MaxLen?+?1];??????//读入的第二个大数??
  48. ??
  49. ????scanf("%d",&n);??
  50. while?(?n-->0?)??
  51. ????{??
  52. ????????scanf("%s",?str1);????????//以字符串形式读入大数??
  53. ????????scanf("%s",?str2);??
  54. for?(?i=0;?i<MaxLen;?i++?)???//初始化清零操作??
  55. ????????????num_a[i]?=?0;??
  56. ????????????num_b[i]?=?0;??
  57. ????????????num_c[i]?=?0;??
  58. ??
  59. ????????len1?=?strlen(str1);??//获得大数的位数??
  60. ????????len2?=?strlen(str2);??
  61. for(?j=0,?i=len1-1;?i>=0;?j++,?i--?)??
  62. ????????????num_a[j]?=?str1[i]?-?'0';??//将字符串转换成对应的整数,颠倒存储??
  63. ????????????num_b[j]?=?str2[i]?-?'0';??
  64. if(?len1?<?len2?)???//如果被除数小于除数，结果为0??
  65. ????????????printf("0n");??
  66. continue;???//利用continue直接跳出本次循环。?进入下一组测试??
  67. ????????nTimes?=?len1?-?len2;????//相差位数??
  68. for?(?i=len1-1;?i>=0;?i--?)????//将除数扩大，使得除数和被除数位数相等??
  69. if?(?i>=nTimes?)??
  70. ????????????????num_b[i]?=?num_b[i-nTimes];??
  71. else?????????????????????//低位置0??
  72. ????????????????num_b[i]?=?0;??
  73. ????????len2?=?len1;??
  74. for(?j=0;?j<=nTimes;?j++?)??????//重复调用，同时记录减成功的次数，即为商??
  75. while((nTemp?=?SubStract(num_a,num_b?+?j,len1,len2?-?j))?>=?0)??
  76. ????????????{??
  77. ????????????????len1?=?nTemp;??????//结果长度??
  78. ????????????????num_c[nTimes-j]++;//每成功减一次，将商的相应位加1??
  79. ????????????}??
  80. ????????//输出结果??
  81. for(?i=MaxLen-1;?num_c[i]==0?&&?i>=0;?i--?);//跳过高位0??
  82. if(?i>=0?)??
  83. for(?;?i>=0;?i--?)??
  84. ????????????????printf("%d",?num_c[i]);??
  85. else??
  86. ????????????printf("0");??
  87. ????????printf("n");??
  88. return?0;??
  89. }??

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!
    相关内容
      推荐文章
        站长推荐
        热点阅读

          【免责声明】本站内容转载自互联网，其发布内容言论不代表本站观点，如果其链接、内容的侵犯您的权益，烦请提交相关链接至邮箱bqsm@foxmail.com我们将及时予以处理。

          建议您使用1920×1080分辨率、谷歌浏览器Google Chrome、Microsoft Edge以获得本站的最佳浏览效果

          Copygight © 2008-2022 https://www.lidatong.com.cn/ All Rights Reserved. 李大同