关于我，穿越异世界，凭c语言搅动风云vlog----利用数组进行大数相关计算
一 .有关大数你应该要知道的那些事
1.大数的概念
我们一般将计算机基本数据类型无法存储的数称之为大数，本文涉及的大数均为整数，不包含小数。而且下文代码实现中的数组大小可根据需要修改。
2.问题引入
在c语言的学习过程中，我们知道，基本数据类型存储的数据是有范围的，比如当前大多数编译器的short int 的范围是-32767到32767，即使是long long int 存储的数据也只有19位左右。那这时，我们就会有一个问题，面对位数最少十几为最长几万几十万的数据，计算机如何存储和计算呢？
3.大数在计算机中的存储
我们一般利用数组在内存中存储大数，如下图所示。将大数的每一位数存储在数组中，再利用数组下标提取大数。
二.大数的相关计算
1.大数的加法
a.前要
首先我们要输入两个字符串，因为当前部分编译器不支持变长数组的，所以我们利用字符串数组来进行大数的输入。阅读代码推荐顺序，先看主函数再看add函数，结合注释。
b.原理
核心思想就是人工列竖式的方式进行计算
c.代码实现
#include<stdio.h>
#include<string.h>
int num1[300], num2[300], num3[300];//1，2为进行计算的大数果
//3为计算结果
void add(int num1[], int num2[], int len)
{
int temp = 0;//进行进位
for (int i = 0; i < len; i++)
{
num3[i] = num1[i] + num2[i] + temp;
temp = num3[i] / 10;
if (num3[i] > 9&&i<len-1)
{
num3[i] %= 10;
}
}//加法实现
for (int i = len - 1; i >= 0; i--)
{
if (num3[i] != 0)
{
break;
}//删除前缀0
len--;
if (len == 0)
{
printf("0");
break;//讨论两个数都为0的情况
}
}
if (num3[len - 1] > 9)
{
num3[len - 1] %= 10;
len++;
num3[len - 1] = 1;
}//讨论最大位是否需要进位
for (int i = len - 1; i >= 0; i--)
{
printf("%d", num3[i]);
}//倒序打印结果
}
int main()
{
char arr1[300], arr2[300];
int len1, len2;//两个字符串长度
gets(arr1);//输入我们要进行计算的大数
gets(arr2);//
len1 = strlen(arr1);//算出大数长度，方便将大数存储在
len2 = strlen(arr2);//整型数组中
for (int i = len1-1; i >= 0; i--)
{
num1[i] = arr1[len1 - 1 - i]-'0';
}
for (int i = len2 - 1; i >= 0; i--)
{
num2[i] = arr2[len2 - 1 - i]-'0';
}//两个循环将字符串转化为整型
if (len1 > len2)//确定长度，方便进行进位的讨论
{
add(num1, num2, len1);//加法函数实现目的
}
else
{
add(num1, num2, len2);
}
return 0;
}
2.大数的减法
a.前要
大数减法的实现和大数加法类似。
b.原理
大数的减法的核心也是利用人工列竖式的方式，但是负号位置的问题正常来说很难处理，所以我们采用单独打印负号的方式，详情请看代码。
c.代码实现
#include<stdio.h>
#include<string.h>
char arr1[300], arr2[300];//大数的输入
int num1[300], num2[300], num3[300];//1，2为输入，3为结果
int len1, len2;//num1,2的长度
int count = 0;
void sub(int num1[], int num2[], int len)//减法具体实现
{
for (int i = 0; i < len; i++)
{
if (num1[i] >= num2[i])
{
num3[i] = num1[i] - num2[i];
}
else if (num1[i] < num2[i])
{
num3[i] = num1[i] - num2[i]+10;
num1[i + 1]--;
}
}//大数相减过程
for (int i = len - 1; i >= 0; i--)
{
if (num3[i] != 0)
{
break;
}
len--;
if (len == 0)
{
printf("0");
break;
}
}//去除前导0，并解决0-0的特殊情况
for (int i = len - 1; i >= 0; i--)
{
printf("%d", num3[i]);//倒序打印
}
}
int main()
{
gets(arr1);
gets(arr2);
len1 = strlen(arr1);
len2 = strlen(arr2);
for (int i = len1 - 1; i >= 0; i--)
{
num1[len1 - 1 - i] = arr1[i]-'0';
}
for (int i = len2 - 1; i >= 0; i--)
{
num2[len2 - 1 - i] = arr2[i]-'0';
}//将字符串转为整型
if (len1 > len2)
{
sub(num1, num2, len1);
}
if (len2 > len1)
{
printf("-");
sub(num2, num1, len2);
}
if (len1 == len2)//位数相同时大小比较
{
for (int i = len1-1; i >= 0; i--)
{
if (num1[i] == num2[i])
{
count++;
continue;
}
else if (num1[i] > num2[i])
{
sub(num1, num2, len1);
break;//注意退出循环，否则容易错
}
else if (num1[i] < num2[i])
{
printf("-");
sub(num2, num1, len1);
break;
}
}
}
if (len1 == count)
{
printf("0");//两个数相同时处理
}
return 0;
}
3.大数的乘法
a.原理
从低位向高位乘，在竖式计算中，我们是将乘数第一位与被乘数的每一位相乘，记录结果之后，用第二位相乘，记录结果并且左移一位，以此类推，直到计算完最后一位，再将各项结果相加，得出最后结果。计算的过程基本上和小学生列竖式做乘法相同。为编程方便，并不急于处理进位，而将进位问题留待最后统一处理。本质也是模拟人工竖式计算。
b.代码实现
#include<stdio.h>
#include<string.h>
int main()
{
char arr1[300], arr2[300];
int num1[300] = { 0 }, num2[300] = { 0 }, num3[600] = { 0 };//两数相乘的结果位数一定小于等于因子位数两倍
int len1, len2;
gets(arr1);
gets(arr2);
len1 = strlen(arr1);
len2 = strlen(arr2);
if (arr1[0] == '0' && len1 == 1)
{
printf("0");//解决有一个数为0
return 0;
}
if (arr2[0] == '0' && len2 == 1)
{
printf("0");//解决有一个数为0
return 0;
}
for (int i = len1 - 1; i >= 0; i--)
{
num1[len1 - 1 - i] = arr1[i] - '0';
}
for (int i = len2 - 1; i >= 0; i--)
{
num2[len2 - 1 - i] = arr2[i] - '0';
}
int k = 599;
for (int i = 0; i < len1; i++)
{
for (int j = 0; j < len2; j++)
{
num3[i + j] = num1[i] * num2[j] + num3[i + j];
//观察列竖式计算可得这个规律，先不进位
}
}
for (int i = 0; i <= 599; i++)
{
if (num3[i] > 9)
{
num3[i + 1] += num3[i] / 10;
num3[i] %= 10;//处理进位
}
}
for (int i = 599; i >= 0; i--)
{
if (num3[i] != 0)
{
break;//去除前缀0
}
k--;
}
for (int i = k; i >= 0; i--)
{
printf("%d", num3[i]);//逆序打印
}
return 0;
}
4.大数的除法
a.前要
我们知道，大数除法可以分为求商和求余数。而且对与a/b的问题，一般分为a=b,a>b,a<b三种情况，我们经常遇到的便是a>b的情况。
b.原理
其实除法可以理解为不断做减法的过程，但是有时候效率会比较低，那有没有什么方式可以加快这个进程呢？我们以28536 除以23 为例来看一下：开始商为0。先减去23 的1000 倍，就是23000，发现够减1 次，余下5536，于是商的值就增加1000；然后用5536减去2300，发现够减2 次，余下936，于是商的值增加200，即1200；再用936 减去230，够减4 次，余下16，于是商值增加40，即1240。
c.代码实现
#include<stdio.h>
#include<string.h>
char a[100],b[100];//用两个字符串用来输入两个大数
int x[100],y[100],z[100];//被除数 除数 商
int digit;//大数的位数
void sub(int x[],int y[],int len1,int len2)//大数减法
{
int i;
for(i=0;i<len1;i++)
{
if(x[i]<y[i])
{
x[i]=x[i]+10-y[i];
x[i+1]--;
}
else
x[i]=x[i]-y[i];
}
for(i=len1-1;i>=0;i--)//判断减法结束之后，被除数的位数
{
if(x[i])
{
digit=i+1;
break;
}
}
}
int judge(int x[],int y[],int len1,int len2)
{
int i;
if(len1<len2)
return -1;
if(len1==len2)//若两个数位数相等
{
for(i=len1-1;i>=0;i--)
{
if(x[i]==y[i])//对应位的数相等
continue;
if(x[i]>y[i])//被除数 大于 除数，返回值为1
return 1;
if(x[i]<y[i])//被除数 小于 除数，返回值为-1
return -1;
}
return 0;//被除数 等于 除数，返回值为0
}
}
int main()
{
int i,j=0,k=0,temp;
int len1,len2,len;//len两个大数位数的差值
while(~scanf("%s %s",a,b))
{
len1=strlen(a);//被除数位数
len2=strlen(b);//除数位数
for(i=len1-1,j=0;i>=0;i--)//将字符串中各个元素倒序储存在数组中
x[j++]=a[i]-'0';
for(i=len2-1,k=0;i>=0;i--)
y[k++]=b[i]-'0';
if(len1<len2)//当被除数位数 小于 除数位数时
{
printf("商是：0\n");
printf("余数是：");
puts(a);
}
else //当被除数位数 大于或者 除数位数时
{
len=len1-len2;//两个大数位数的差值
for(i=len1-1;i>=0;i--)//将除数后补零，使得两个大数位数相同。被除数：4541543329 除数：98745,加零后:9874500000
{
if(i>=len)
y[i]=y[i-len];
else
y[i]=0;
}
len2=len1;//将两个大数数位相同
digit=len1; //将原被除数位数赋值给digit
for(j=0;j<=len;j++)
{
z[len-j]=0;
while(((temp=judge(x,y,len1,len2))>=0)&&digit>=k)//判断两个数之间的关系以及位数与除数原位数的关系
{
sub(x,y,len1,len2); //大数减法函数
z[len-j]++;//储存商的每一位
len1=digit;//重新修改被除数的长度
if(len1<len2&&y[len2-1]==0)
len2=len1;//将len1长度赋给len2;
}
if(temp<0)//若被除数 小于 除数，除数减小一位。例如：被除数：4541543329 除数：(原)98745,(加零后)9874500000，后退一位后:0987450000
{
for(i=1;i<len2;i++)
y[i-1]=y[i];
y[i-1]=0;
if(len1<len2)
len2--;
}
}
printf("商是：");
for(i=len;i>0;i--)//去掉前缀0
{
if(z[i])
break;
}
for(;i>=0;i--)
printf("%d",z[i]);
printf("\n");
printf("余数是：");
for(i=len1;i>0;i--)
{
if(x[i])
break;
}
for(;i>=0;i--)
printf("%d",x[i]);
printf("\n");
}
}
return 0;
}
5.大数的阶乘
a.原理
对于大数来说，一个数的阶乘是非常大的，同样，一个int类型的整数，他的阶乘就有可能会很大。就拿50来说，他的阶乘位数是65位，就已经远远超过了long long int类型的最大值。这时候，我们要通过字符串的方法，来进行阶乘的运算。当然，需要注意的是：
我们所求一个数的阶乘，这个数是在基本数据类型范围内的，5000的阶乘位数是16326位。其方法是：首先，我们是可以先求一定范围内的最大值的阶乘位数，以便于申请数组空间的确定。**对于大数问题，我们要有将大数与数组结合的思想，可以利用类似于人工求值的方法求出有关大数的问题。**对于大数阶乘来说，最重要的是如何将每个数的每位数与相对应的数组元素储存起来，就如算50的阶乘，我们要先从1开始乘：
1*2=2,将2存到a[0]中，
接下来是用a[0]*3；
2*3=6，将6储存在a[0]中，
接下来是用a[0]*4；
6*4=24，是两位数，那么24%10==4存到a[0]中，24/10==2存到a[1]中，
接下来是用a[0]*5；a[1]*5+num(如果前一位相乘结果位数是两位数，那么num就等于十位上的那个数字；如果是一位数，num==0)
24*5=120，是三位数，那么120%10==0存到a[0]中，120/10%10==2存到a[1]中，120/100==1存到a[2]中，
接下来是用a[0]*3；a[1]*6+num；a[2]*6+num；
120*6=720，那么720%10==0存到a[0]中，720/10%10==2存到a[1]中，720/100==7存到a[2]中，
…
直到乘到50，将每一位数储存为止。
b.代码实现
#include<stdio.h>
#include<string.h>
int main()
{
int num[30000];
int n;
int digit=1,p=0, temp;//digit代表位数，p可以帮助进位
scanf("%d", &n);
num[0] = 1;
for (int i = 2; i <= n; i++)
{
p = 0;
for (int j = 0; j < digit; j++)
{
temp = num[j] * i + p;
num[j] = temp % 10;
p = temp / 10;
}
while (p)
{
num[digit] = p % 10;
p /= 10;
digit++;
}
}
for (int i = digit-1; i >= 0; i--)
{
printf("%d", num[i]);
}
return 0;
}
c.大数阶乘位数
利用lg(N!)=[lg(N*(N-1)(N-2)…32*1)]+1 =[lgN+lg(N-1)+lg(N-2)+…+lg3+lg2+lg1]+1。
代码实现
#include<stdio.h>
#include<math.h>
int main()
{
int n;
double sum = 0;
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
sum = sum + log10(i);
}
printf("%d\n", (int)sum + 1);
return 0;
}
6.大数阶乘和
a.原理
当我们掌握大数阶乘就可以写出来。
b.代码实现
#include<stdio.h>
int main()
{
int m;
scanf("%d", &m);
int aee[100000] = { 0 };
int hp = 0;
int hpp = 0;
int x;
for (int n =1; n <= m; n++)
{
hp=0;
int arr[100000] = { 0 };
int num;
int sum = 0, dight = 1;
arr[0] = 1;
for (int i = 2; i <= n; i++)
{
num = 0;
for (int j = 0; j < dight; j++)
{
sum = arr[j] * i + num;
arr[j] = sum % 10;
num = sum / 10;
}
while (num)
{
arr[dight] = num % 10;
dight++;
num /= 10;
}
}
for (int i = 0; i < dight; i++)
{
hpp= arr[i] + hp+aee[i];
aee[i] = hpp % 10;
hp = hpp / 10;
if (i == dight - 1 && hp)
{
dight++;
}
}
x = dight;
}
for (int i = x- 1; i >= 0; i--)
{
printf("%d", aee[i]);
}
return 0