Java教程
大数算法的总结
目录：
-
前言
-
大数加法
-
大数减法
-
大数乘法
-
大数除法
-
大数阶乘位数
-
大数阶乘求解
-
总结
一.前言.
众所周知，计算机数据类型的长度是有限的，因此在处理较大的数据时候会发生数据溢出，此时聪明的我们需要想办法处理这批数据，那么我们如何处理呢？答案是用数组存储数据，再做批量处理。
不知道你们是否观察过用递归求阶乘，当n为13时(数据类型为int型),数据明显不对，有朋友可能就说了如果是longlong型数据呢？longlong型数据肯定可以求出13以上，但是100以上呢？是不是又越界了？这里我参考了其他博主的文章写了一下大数算法的有关内容。
二.正文
一.大数加法
所谓大数加法，就是在我们计算机数据无法存储的大数据时进行的加法运算。那我们如何实现大数加法呢，我们可以用数组，链表等结构来分段存储大数据，这里我采用 数组进行大数运算的描写。假如我们输入123456789123456 + 123这两个数据时，如果要发生相加的运算，那么第一个数字怎么存储呢？答案是用数组来存，准确点说是字符数组，我们把这两个当成一个字符串输入到一个字符数组中，然后再进行倒序处理，为什么要倒序处理呢？比如说123456789123456 + 123，这里我们把6和3相加，5和2相加，4和3相加，但是在程序中是否表达不便呢？还有一个优点是我们可以很方便的进行进位处理，所以我们采用倒序处理。那怎么倒序呢，用整形数组从下表0开始存字符数组从后往前推的字符-‘0’（这里解释一下减字符0是为了从字符转成相应的数字，如果不了解可以去查找Ascii码表）。两个数组依次进行这个操作后，那么用一个sum数组进行相加即可。具体代码实现如下：
#include "bits/stdc++.h"
#include "cstring"
using namespace std;
char s1[600],s2[600];
int a[600],b[600];
int sum[1200];
int main()
{
int i,j,res;
int length1,length2;
int len;
cin >> s1;
cin >> s2;
length1 = strlen(s1);
length2 = strlen(s2);
j = 0;
for(i = length1 - 1 ;i >= 0;i--)
a[j++] = s1[i] - '0';//倒转
j = 0;
for(i = length2 - 1;i >= 0;i--)
b[j++] = s2[i] - '0';//倒转
if(length1 > length2)
len = length1;//遍历到最长的那个数字
else
len = length2;
res=0;//存进位
for(i = 0;i < len;i++)
{
sum[i] = (a[i] + b[i] + res) % 10;
res = (a[i] + b[i] + res)/10;
}
if(res)//如果此时还存在进位
{
sum[i] = res;
i++;
}
for(j = i - 1;j >= 0;j--)
cout << sum[j];//从后往前打印
cout << endl;
return 0;
}
二.大数减法
大数减法采用大数加法的思路存储数据，处理数据时从低位开始往高位减，例如123456 - 123 逆转后就是654321 - 321，这时候6 - 3,5- 2,4-1，然后其他的可以直接赋给minus数组了，如果被减数相应位数小于减数相应位数的话，我们采用借位的方式。例如1234-345,4-5<0，往前借位，借位后前一位-1,也就是3-1，（这里我默认是逆转过后的数组）。如果被减数小于减数呢？我们怎么判断呢？这时候我们只需要判断如果被减数的长度小于减数的长度，那么我们可以直接输出一个负号，然后再用减数-被减数。有人又问了，那如果两个数位数相等，且被减数小于减数呢？此时我们只需要把逆转后的数组从前往后遍历，如果发现被减数位数小于减数位数的话，我就可以判断出来了。直接输出一个负号，然后用减数减去被减数，总的来说思路就是如果被减数大于减数，那么可以直接减去就行；如果被减数小于减数，就直接输出一个负号，然后用减数减去被减数。例如123456 - 789 ，123456是被减数，789是减数，别搞混了啊。接下来贴出我的代码实现（代码有点长，有能力的小伙伴可以自行实现）：
#include "bits/stdc++.h"
using namespace std;
char s1[100],s2[100];
int length1,length2;
int a1[100],b2[100];
int i,j;
int len;
int minus1[200];
int main()
{
cin >> s1 >>s2;
length1 = strlen(s1);
length2 = strlen(s2);
j=0;//从头开始添加a1数组
for(i = length1 - 1;i >= 0;i--)
{
a1[j++] = s1[i] - '0';//倒置
}
j=0;//从头开始添加b数组
for(i = length2 - 1;i >= 0;i--)
{
b2[j++] = s2[i] - '0';
}
len = (length1 > length2)?length1 : length2;//len为两个字符串最长的那个
if(length1 - length2 > 0)//第一个数组减第二个
{
for(i = 0;i < len;i++)
{
if(a1[i] >= b2[i])//如果大于的话直接减
minus1[i] = a1[i] - b2[i];
else
{
minus1[i] = a1[i] + 10 -b2[i];
a1[i+1] = a1[i+1] -1;
}
}
for(j = len -1;j >= 0;j--)//因为两个数长度不一样，所以相减一定不为0,否则一定要保留最后一个0
if(minus1[j] == 0)
len--;//进行删0操作
else
break;
}
else if(length1 - length2 < 0)//第二个数组减第一个
{
cout << "-";//输出负号
for(i = 0;i < len;i++)
{
if(b2[i] >= a1[i])//如果大于的话直接减
minus1[i] = b2[i] - a1[i];
else
{
minus1[i] = b2[i] + 10 -a1[i];
b2[i+1] = b2[i+1] -1;
}
}
for(j = len -1;j >= 0;j--)//因为两个数长度不一样，所以相减一定不为0,否则一定要保留最后一个0列如99-100
if(minus1[j] == 0)
len--;//进行删0操作
else
break;
}
else//如果相等则判断谁大谁小
{
for(i = len - 1;i >= 0;i--)
{
if(a1[i] == b2[i])
continue;
else if(a1[i] > b2[i])
break;
else
break;
}
if(a1[i] > b2[i])
{
for(i = 0;i < len;i++)
{
if(a1[i] >= b2[i])//如果大于的话直接减
minus1[i] = a1[i] - b2[i];
else
{
minus1[i] = a1[i] + 10 -b2[i];
a1[i+1] = a1[i+1] -1;
}
}
for(j = len -1;j >= 0;j--)//因为两个数长度不一样，所以相减一定不为0,否则一定要保留最后一个0
if(minus1[j] == 0)
len--;//进行删0操作
else
break;
}
else if(a1[i] < b2[i])
{
cout << "-";//输出负号
for(i = 0;i < len;i++)
{
if(b2[i] >= a1[i])//如果大于的话直接减
minus1[i] = b2[i] - a1[i];
else
{
minus1[i] = b2[i] + 10 -a1[i];
b2[i+1] = b2[i+1] -1;
}
}
for(j = len -1;j >= 0;j--)//因为两个数长度不一样，所以相减一定不为0,否则一定要保留最后一个0列如99-100
if(minus1[j] == 0)
len--;//进行删0操作
else
break;
}
else
{
printf("0");
return 0;
}
}
for(j = len-1;j >= 0;j--)
cout << minus1[j];
cout << endl;
return 0;
}
三.大数乘法
不知道小伙伴们是否了解过计算器的原理，我曾有幸在图书馆了解过一本有关计算器原理的书，里面就介绍了一下计算器的四则运算，所谓乘法就是多次加法，小学时候我们还不懂乘法的时候计算5*3，就会把5加上三次，其实这个就是乘法的原理，多次累加。那我们如何用程序实现它呢，比如说123 * 45 我们逆转后为321 *54 ，3*5就是15个1,3*4就是12个十， 2*5就是10个十，2*4就是8个一百，然后1*5就是五个一百，1*4就是4个1千，然后将结果进位即可。具体代码实现如下：
#include "bits/stdc++.h"
#include "cstring"
using namespace std;
char s1[100],s2[100];
int a1[100],b2[100];
int multi[200];
int main()
{
int i,j;
cin >> s1;
cin >> s2;
j = 0;
for(i = strlen(s1) - 1;i >= 0; i--)
a1[j++] = s1[i] - '0';
j = 0;
for(i = strlen(s2) - 1; i >= 0; i--)
b2[j++] = s2[i] - '0';//翻转数字
for(i = 0;i < strlen(s1); i++)
for(j = 0;j < strlen(s2); j++)
{
multi[i + j] = multi[i + j] + a1[i] * b2[j];//先不计算进位
}
for(i = 0;i < strlen(s1) + strlen(s2); i++)//两数相乘最大位数为两数位数相加
if(multi[i] >= 10)
{
multi[i + 1] += multi[i] / 10;//注意数组要提前开大一点，否则会越界
multi[i] = multi[i] % 10;
}
for(i = strlen(s1) + strlen(s2) - 1;i >= 1; i--)//删除多余0的操作
if(multi[i] != 0)
break;
while(i >= 0)
{
cout << multi[i--];
}
cout << endl;
return 0;
}
四.大数除法
#include "bits/stdc++.h"
#include "cstring"
using namespace std;
char s1[100],s2[100];
int a1[100],b1[100];
int len1,len2,len;//len计算len1和len2之间差的长度
int z[100];
int temp;
int subtraction(int length1,int length2)
{
int i;
for(i = 0;i < length2;i++)
{
if(a1[i] >= b1[i])
{
a1[i] -= b1[i];
}
else
{
a1[i] = a1[i] + 10 -b1[i];//如果这个数小于的话，则要进位进行减
a1[i + 1] -= 1;//借位之后减1
}
}
for(i = length1;i > 0 && !a1[i];i--);//消除被除数的前缀 必须为length1开始
return i + 1;//i每次都会进行判断，所以要加1
}
int judge(int length1,int length2)
{
int i;
if(length1 < length2)
return -1;//小于返回-1
else
{
for(i = len1 - 1;i >= 0;i--)
{
if(a1[i] == b1[i])
continue;
if(a1[i] < b1[i])//小于则返回-1
return -1;
if(a1[i] > b1[i])//大于则返回1
return 1;
}
}
return 0;//如果相等就返回0
}
int main()
{
int i,j;
cin >> s1;
cin >> s2;
len1 = strlen(s1);
len2 = strlen(s2);
if(len1 < len2)
{
cout << "consult: 0";
cout << "mod : ";
puts(s2);
}
else
{
for(i = len1 - 1,j = 0;i >= 0;i--)
{
a1[j++] = s1[i] - '0'; //反转数组 调试成功
}
for(i = len2 - 1,j = 0;i >= 0;i--)
{
b1[j++] = s2[i] - '0'; //反转数组 调试成功
}
len = len1 - len2;
for(i = len1 -1 ;i >= 0;i--)
if(i >= len)
b1[i] = b1[i-len];
else
b1[i] = 0;
len2 = len1;//同步字符位数 调试成功
for(j = 0;j <= len;j++)//这一步主要是处理每一位上的
{
z[len - j] = 0;
while((temp = judge(len1,len2)) >= 0)
{
z[len - j]++;//如果满足则可以加1次
len1 = subtraction(len1,len2);
cout << len1 << " " << j << endl;
cout << a1[0] << " " << a1[1] << endl;
}
if(temp < 0 && b1[0] == 0)//除数减1 如果前缀不为0的话可以结束了
{
for(i = 0;i < len2 - 1;i++)
{
b1[i] = b1[i + 1];
}
b1[len2 - 1] = 0;
len2--;//减小除数位数
}
}
}
for(i = len;i > 0;i--)
{
if(z[i])
break;//消除商的前缀0
}
cout << "consult:";
while(i >= 0)
cout << z[i--];
cout << endl;
cout << "mod:";
for(i = len1 - 1;i > 0;i--)
{
if(a1[i])
break;//消除商的前缀0
}
if(len1 == 0)
i = len1;
while(i >= 0)
cout << a1[i--];
cout << endl;
return 0;
}
五.大数阶乘位数
不知道小伙伴是否碰到过用int型求阶乘时，会发现数据明显不对，比如说求13的阶乘，我们发现打印13的阶乘为
然而我们可以百度搜索阶乘计算器后可以得出
那么时哪里出错了呢，答案是数据类型长度不够。所以我们应该改变策略，用数组存储数据，再批量处理。接下来我们先介绍两个计算阶乘位数的算法。1.用对数函数求解阶乘位数
2.用Stirling公式求解位数。再介绍如何进行阶乘的计算。
1.对数函数求位数
lg1+lg2+lg3+lgn，由对数函数特性可知，lga+lgb等于lga*b,这时候我们发现真数a*b就可以替换成我们的1和2-n。但此时为什么不会越界呢，因为lg函数返回的是一个double型，所以我们用一个double型的数去存这个值就行，这个值是较小的，所以不会发生数据溢出的情况。需要注意的是我们的位数初始化为1，输出的时候应该把位数取整后输出。具体代码如下：
#include "bits/stdc++.h"
#include "cmath"
using namespace std;
int main()
{
double sum = 0;
int i;
for(i = 1;i <= 200;i++)
sum += log10(i);//计算阶乘的位数 利用log10的特性进行判断
cout << (int)(sum + 1) << endl;//sum刚开始为1位数
return 0;
}
2.Stirling公式求位数
Stirling公式证明过程复杂，我只是个记公式的小菜鸡，请移步大佬的blog进行思考，这里给出链接如下https://www.cnblogs.com/jokerjason/p/9525590.html，这里我贴出代码实现
#include "bits/stdc++.h"
#include "cmath"
using namespace std;
const double e = 2.7182818284;//小数越多精度越高
const double Pi = 3.1415926535;
int main()
{
int res = 0;
int n;
cin >> n;
res = 0.5 * log10(2 * Pi * n) + n * log10(n/e);
cout << res + 1;
return 0;
}
六.大数阶乘求解
阶乘求解得思路就是用一个数组存储，然后每次进来一个乘数，把每个数组元素都乘以这个乘数，如果发现了高位要溢出了，那么我们可以增加一位存高位，然后就是处理进位问题了，我们依然是从低位开始向高位遍历，如果大于10的话我们就往前进位，这里我才用的是一个数组元素存6位的方式，读者可以采用1位存法实现大数阶乘。具体代码如下：
#include "stdio.h"
int main()
{
int i = 1,high = 0,tag = 0;//tag为低位，high为高位，i为阶乘值
int a[1000] = {0};//计算精确度为7000位
a[high] = 1;//把第一次运算赋初值为1
while(i <= 100)
{
for(tag = 0;tag <= high; tag++)
a[tag] *= i;
if(a[high] >= 1000000)
high += 1;
for(tag = 0;tag <= high; tag++)
{
if(a[tag] >= 1000000)
{
a[tag + 1] += a[tag] / 1000000;
a[tag] = a[tag] % 1000000;
}
}
i++;
}
tag = high;
while(high >= 0)
{
if(high == tag)
printf("%d",a[high]);
else
printf("%06d",a[high]);//这是一个输出小技巧，左边补0，如果是-06d的话是右边补零
high--;
}
return 0;
}
七.总结
第一次发表博客，写的不好的地方请及时指出，我会修改的！另外学习是一件很充实又很快乐的事情，一起加油吧！
-
ShardingSphere 如何完美驾驭分布式事务与 XA 协议？11-16
-
ShardingSphere如何轻松驾驭Seata柔性分布式事务？11-16
-
Maven资料入门指南11-16
-
Maven资料入门教程11-16
-
MyBatis Plus资料：新手入门教程与实践指南11-16
-
MyBatis-Plus资料入门教程：快速上手指南11-16
-
Mybatis资料入门教程：新手必看指南11-16
-
MyBatis资料详解：新手入门与初级实战指南11-16
-
MyBatisPlus资料：初学者入门指南与实用教程11-16
-
MybatisPlus资料详解：初学者入门指南11-16
-
MyBatisX资料：新手入门与初级教程11-16
-
RESTful接口资料详解：新手入门指南11-16
-
RESTful接口资料详解：新手入门教程11-16
-
Spring Boot资料：新手入门与初级教程11-16
-
Springboot资料：新手入门与初级教程11-16
