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

大数模板

发布时间：2020-12-14 02:12:17 所属栏目：大数据 来源：网络整理
导读：链接：http://www.voidcn.com/article/p-xjnjfxxq-vd.html 分别使用C++中的运算符重载的方法来实现大数之间的数学运算，包括加法、减法、乘法、除法、n次方、取模、大小比较、赋值以及输入流、输出流的重载。。 ???????? 并且使用这个大数模板，顺利AC了HDOJ

链接：http://www.voidcn.com/article/p-xjnjfxxq-vd.html


分别使用C++中的运算符重载的方法来实现大数之间的数学运算，包括加法、减法、乘法、除法、n次方、取模、大小比较、赋值以及输入流、输出流的重载。。

???????? 并且使用这个大数模板，顺利AC了HDOJ上的1134这个题目的Catalan数计数问题。。http://acm.hdu.edu.cn/showproblem.php?pid=1134

大数模板的代码如下：

[cpp]?view plaincopy
  1. #include<iostream>???
  2. #include<string>???
  3. #include<iomanip>???
  4. #include<algorithm>???
  5. using?namespace?std;???
  6. ??
  7. #define?MAXN?9999??
  8. #define?MAXSIZE?10??
  9. #define?DLEN?4??
  10. class?BigNum??
  11. {???
  12. private:???
  13. ????int?a[500];????//可以控制大数的位数???
  14. ????int?len;???????//大数长度??
  15. public:???
  16. ????BigNum(){?len?=?1;memset(a,sizeof(a));?}???//构造函数??
  17. ????BigNum(const?int);???????//将一个int类型的变量转化为大数??
  18. ????BigNum(char*);?????//将一个字符串类型的变量转化为大数??
  19. const?BigNum?&);??//拷贝构造函数??
  20. ????BigNum?&operator=(const?BigNum?&);???//重载赋值运算符，大数之间进行赋值运算??
  21. ????friend?istream&?operator>>(istream&,??BigNum&);???//重载输入运算符??
  22. ????friend?ostream&?operator<<(ostream&,0); background-color:inherit">//重载输出运算符??
  23. ??
  24. ????BigNum?operator+(const?BigNum?&)?const;???//重载加法运算符，两个大数之间的相加运算???
  25. ????BigNum?operator-(//重载减法运算符，两个大数之间的相减运算???
  26. ????BigNum?operator*(//重载乘法运算符，两个大数之间的相乘运算???
  27. ????BigNum?operator/(int???&)?const;????//重载除法运算符，大数对一个整数进行相除运算??
  28. ????BigNum?operator^(int??&)?//大数的n次方运算??
  29. int????operator%(//大数对一个int类型的变量进行取模运算??????
  30. bool???operator>(const?BigNum?&?T)//大数和另一个大数的大小比较??
  31. int?&?t)const;??????//大数和一个int类型的变量的大小比较??
  32. void?print();???????//输出大数??
  33. };???
  34. BigNum::BigNum(int?b)????? {???
  35. int?c,d?=?b;??
  36. ????len?=?0;??
  37. ????memset(a,153); font-weight:bold; background-color:inherit">sizeof(a));??
  38. while(d?>?MAXN)??
  39. ????{??
  40. ????????c?=?d?-?(d?/?(MAXN?+?1))?*?(MAXN?+?1);???
  41. ????????d?=?d?/?(MAXN?+?1);??
  42. ????????a[len++]?=?c;??
  43. ????}??
  44. ????a[len++]?=?d;??
  45. }??
  46. BigNum::BigNum(char*s)????? {??
  47. int?t,k,index,l,i;??
  48. ????l=strlen(s);?????
  49. ????len=l/DLEN;??
  50. if(l%DLEN)??
  51. ????????len++;??
  52. ????index=0;??
  53. for(i=l-1;i>=0;i-=DLEN)??
  54. ????{??
  55. ????????t=0;??
  56. ????????k=i-DLEN+1;??
  57. ????????if(k<0)??
  58. ????????????k=0;??
  59. for(int?j=k;j<=i;j++)??
  60. ????????????t=t*10+s[j]-'0';??
  61. ????????a[index++]=t;??
  62. ????}??
  63. const?BigNum?&?T)?:?len(T.len)??//拷贝构造函数??
  64. int?i;???
  65. sizeof(a));???
  66. for(i?=?0?;?i?<?len?;?i++)??
  67. ????????a[i]?=?T.a[i];???
  68. }???
  69. BigNum?&?BigNum::operator=(const?BigNum?&?n)???//重载赋值运算符，大数之间进行赋值运算??
  70. {??
  71. int?i;??
  72. ????len?=?n.len;??
  73. for(i?=?0?;?i?<?len?;?i++)???
  74. ????????a[i]?=?n.a[i];???
  75. return?*this;???
  76. istream&?operator>>(istream?&?in,??BigNum?&?b)???char?ch[MAXSIZE*4];??
  77. int?i?=?-1;??
  78. ????in>>ch;??
  79. int?l=strlen(ch);??
  80. int?count=0,sum=0;??
  81. for(i=l-1;i>=0;)??
  82. ????????sum?=?0;??
  83. ????????int?t=1;??
  84. int?j=0;j<4&&i>=0;j++,i--,t*=10)??
  85. ????????{??
  86. ????????????sum+=(ch[i]-'0')*t;??
  87. ????????}??
  88. ????????b.a[count]=sum;??
  89. ????????count++;??
  90. ????b.len?=count++;??
  91. return?in;??
  92. ostream&?operator<<(ostream&?out,??BigNum&?b)???//重载输出运算符??
  93. int?i;????
  94. ????cout?<<?b.a[b.len?-?1];???
  95. for(i?=?b.len?-?2?;?i?>=?0?;?i--)??
  96. ????{???
  97. ????????cout.width(DLEN);???
  98. ????????cout.fill('0');???
  99. ????????cout?<<?b.a[i];???
  100. ????}???
  101. return?out;??
  102. BigNum?BigNum::operator+(const?BigNum?&?T)?const???//两个大数之间的相加运算??
  103. ????BigNum?t(*this);??
  104. int?i,big;??????//位数?????
  105. ????big?=?T.len?>?len???T.len?:?len;???
  106. for(i?=?0?;?i?<?big?;?i++)???
  107. ????????t.a[i]?+=T.a[i];???
  108. if(t.a[i]?>?MAXN)???
  109. ????????{???
  110. ????????????t.a[i?+?1]++;???
  111. ????????????t.a[i]?-=MAXN+1;???
  112. ????????}???
  113. ????}???
  114. if(t.a[big]?!=?0)??
  115. ????????t.len?=?big?+?1;???
  116. else??
  117. ????????t.len?=?big;?????
  118. return?t;??
  119. }??
  120. BigNum?BigNum::operator-(//两个大数之间的相减运算???
  121. {????
  122. bool?flag;??
  123. ????BigNum?t1,t2;??
  124. if(*this>T)??
  125. ????????t1=*this;??
  126. ????????t2=T;??
  127. ????????flag=0;??
  128. else??
  129. ????????t1=T;??
  130. ????????t2=*this;??
  131. ????????flag=1;??
  132. ????big=t1.len;??
  133. for(i?=?0?;?i?<?big?;?i++)??
  134. if(t1.a[i]?<?t2.a[i])??
  135. ????????????j?=?i?+?1;???
  136. ????????????while(t1.a[j]?==?0)??
  137. ????????????????j++;???
  138. ????????????t1.a[j--]--;???
  139. ????????????while(j?>?i)??
  140. ????????????????t1.a[j--]?+=?MAXN;??
  141. ????????????t1.a[i]?+=?MAXN?+?1?-?t2.a[i];???
  142. ????????}???
  143. ????????????t1.a[i]?-=?t2.a[i];??
  144. ????t1.len?=?big;??
  145. while(t1.a[len?-?1]?==?0?&&?t1.len?>?1)??
  146. ????????t1.len--;???
  147. ????????big--;??
  148. if(flag)??
  149. ????????t1.a[big-1]=0-t1.a[big-1];??
  150. return?t1;???
  151. }???
  152. BigNum?BigNum::operator*(//两个大数之间的相乘运算???
  153. ????BigNum?ret;???
  154. int?temp,temp1;?????
  155. ????????up?=?0;???
  156. for(j?=?0?;?j?<?T.len?;?j++)??
  157. ????????????temp?=?a[i]?*?T.a[j]?+?ret.a[i?+?j]?+?up;???
  158. if(temp?>?MAXN)??
  159. ????????????{???
  160. ????????????????temp1?=?temp?-?temp?/?(MAXN?+?1)?*?(MAXN?+?1);???
  161. ????????????????up?=?temp?/?(MAXN?+?1);???
  162. ????????????????ret.a[i?+?j]?=?temp1;???
  163. ????????????}???
  164. ????????????????up?=?0;???
  165. ????????????????ret.a[i?+?j]?=?temp;???
  166. ????????????}???
  167. ????????if(up?!=?0)???
  168. ????????????ret.a[i?+?j]?=?up;???
  169. ????ret.len?=?i?+?j;???
  170. while(ret.a[ret.len?-?1]?==?0?&&?ret.len?>?1)??
  171. ????????ret.len--;???
  172. return?ret;???
  173. BigNum?BigNum::operator/(int?&?b)?//大数对一个整数进行相除运算??
  174. ????BigNum?ret;???
  175. for(i?=?len?-?1?;?i?>=?0?;?i--)??
  176. ????????ret.a[i]?=?(a[i]?+?down?*?(MAXN?+?1))?/?b;???
  177. ????????down?=?a[i]?+?down?*?(MAXN?+?1)?-?ret.a[i]?*?b;???
  178. ????ret.len?=?len;???
  179. int?BigNum::operator?%(const????//大数对一个int类型的变量进行取模运算??????
  180. for?(i?=?len-1;?i>=0;?i--)??
  181. ????????d?=?((d?*?(MAXN+1))%?b?+?a[i])%?b;????
  182. return?d;??
  183. BigNum?BigNum::operator^(int?&?n)?//大数的n次方运算??
  184. ????BigNum?t,ret(1);??
  185. int?i;??
  186. if(n<0)??
  187. ????????exit(-1);??
  188. if(n==0)??
  189. return?1;??
  190. if(n==1)??
  191. int?m=n;??
  192. while(m>1)??
  193. ????????t=*for(?i=1;i<<1<=m;i<<=1)??
  194. ????????????t=t*t;??
  195. ????????m-=i;??
  196. ????????ret=ret*t;??
  197. if(m==1)??
  198. ????????????ret=ret*(*this);??
  199. return?ret;??
  200. bool?BigNum::operator>(int?ln;???
  201. if(len?>?T.len)??
  202. return?true;???
  203. else?if(len?==?T.len)??
  204. ????{???
  205. ????????ln?=?len?-?1;???
  206. while(a[ln]?==?T.a[ln]?&&?ln?>=?0)??
  207. ????????????ln--;???
  208. if(ln?>=?0?&&?a[ln]?>?T.a[ln])??
  209. true;???
  210. false;???
  211. false;???
  212. bool?BigNum::operator?>(int?&?t)?//大数和一个int类型的变量的大小比较??
  213. ????BigNum?b(t);??
  214. this>b;??
  215. void?BigNum::print()????//输出大数??
  216. int?i;?????
  217. ????cout?<<?a[len?-?1];???
  218. for(i?=?len?-?2?;?i?>=?0?;?i--)??
  219. ????????cout?<<?a[i];???
  220. ????cout?<<?endl;??
  221. int?main(void)??
  222. ????BigNum?x[101];??????//定义大数的对象数组??
  223. ????x[0]=1;??
  224. for(i=1;i<101;i++)??
  225. ????????x[i]=x[i-1]*(4*i-2)/(i+1);??
  226. while(scanf("%d",&n)==1?&&?n!=-1)??
  227. ????????x[n].print();??
  228. }??

（编辑：李大同）

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

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

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

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