大数算法综述
目录：
前言
大数加法
大数减法
大数乘法
大数除法
大数阶乘位数
大数阶乘求解
总结
一.前言.
众所周知，计算机数据类型的长度是有限的，因此在处理大数据时会发生数据溢出。这时，我们足够聪明，找到了处理这批数据的方法。那我们该怎么处理呢？答案是将数据存储在数组中，然后进行批处理。
不知道大家有没有观察过如何用递归求阶乘。当n为13(数据类型为int)时，数据明显错误。可能有朋友说过，如果是龙龙数据，龙龙数据肯定能找出13个以上，但如果是100个以上，是不是又出格了？在这里，我参考了其他博主的文章，写的是大数算法。
二.正文
一.大数加法
所谓大数加法，就是我们的计算机数据无法存储大数据时的加法运算。那我们如何实现大数的加法呢？我们可以使用数组、链表和其他结构来分段存储大数据。在这里，我用数组来描述大数的运算。如果输入123456789123456 123这两个数据，如果要相加，怎么存储第一个数字？答案是将它们存储在一个数组中，准确地说，是一个字符数组。我们将这两个数据作为字符串输入到一个字符数组中，然后进行逆序处理。我们为什么要进行逆序处理？比如123456789123456 123，这里我们加6和3，5和2，4和3，但是在程序中表达不方便吗？另一个优点是我们可以很容易地进行进位处理，所以我们使用逆序处理。如何颠倒顺序？使用shaping数组存储字符数组从后面推到前面的字符——‘0’来自下面的表0(这里解释一下，减字符0是把字符转换成对应的数字，不知道的可以查Ascii码表)。两个数组依次运算后，就可以加上一个和数组。具体代码实现如下：
# include ' bit/stdc。h
#包含“cstring”
使用命名空间标准；
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；
length 1=strlen(S1)；
length 2=strlen(S2)；
j=0；
for(I=length 1-1；I=0；i -)
a[j]=S1[I]-' 0 '；//反转
j=0；
for(I=length 2-1；I=0；i -)
b[j]=S2[I]-' 0 '；//反转
if(长度1长度2)
len=length1//遍历最长的数字
其他
len=length2
RES=0；//进位保存
for(I=0；我透镜；(一)
{
sum[I]=(a[I]b[I]RES)% 10；
RES=(a[I]b[I]RES)/10；
}
如果此时进位仍然存在
{
sum[I]=RES；
我；
}
for(j=I-1；j=0；j -)
cout sum[j]；//从后向前打印
cout endl
返回0；
}
二.大数减法
大数减法利用大数加法的思想来存储数据。处理数据时，从低位向高位递减，例如123456-123反转后，为654321-321。这时，6-3，5- 2，4-1，然后其他可以直接赋给减数组。如果被减数的对应位数小于归约的对应位数，我们采用借用的方法。比如1234-345，4-50，向前借，借用后的前一位数字是-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;
}七.总结
第一次发表博客，写的不好的地方请及时指出，我会修改的！另外学习是一件很充实又很快乐的事情，一起加油吧！
内容来源网络，如有侵权，联系删除，本文地址：https://www.230890.com/zhan/81996.html