acm-大数问题集锦
大数问题集训会教案
大数问题，其实就是模拟运算，因为系统自带的int long bouble这些类型无法容纳百位千位的大数字，从而手动模拟运算过程，使用字符串来表示这样的超大数字，如果你会Java的话就简单多了，直接有一个大数类，可以像用函数一样直接调用，不过，那个是大三学滴。
大数问题适用的问题，一般是大数阶乘，大数加减乘除余方，这个嘛请参照南阳大数类型题，难度一般是省赛中最简单的3题之一。
废话不说，直接上思路先。
问题一：如何输入输出
问题二：小学生的个位与多位加法是怎么运算的？如何逆转字符串？
问题三：小学生乘法。大数与int数乘，大数与大数乘。
先解决上面三个：
输入输出
Char c【1001】={0}//字符串定义，1000位，清零，
Int input(char c[])
{ char s[1001];
Scanf(“%s”,s）;
Int l = strlen(s);
For(I = 0 ；I < l ；i++ )
C[i] = s[l – I – 1 ] – ‘0’;
Return 0;
} //逆转
Void print（char c【】）
{
for(I = 1000; I > 0 ; I –)
if(c[i] ! = 0 ) break;
for(; I > = 0 ; I –)
printf(“%d”,c[i]);
}//以上是去掉前置0，倒叙输出结果
加法流程
个位开始，一位一位相加同时加上进位的值。
大数 a 0 1 2 3 4 5 6 7 8 9
大数 b 0 1 2 3 4 5 6 7 8 9
相加 0 2 4 6 8 10 12 14 16 18
进位 0 0 0 0 0 1 1 1 1 0
总和 0 2 4 6 9 1 3 5 7 8
Add{char a[], char b[] ,char c []}
{
Int I ;
For(I = 0 ; I < 1000 ; I ++)
C[ I ] = a[I] + b[ i];
For( I = 0 ; I < 1000 ; I ++)
{
If（c[i] > = 10）
{
C[I +1] += c[i] /10 ;
C[i] = c[i] %10 ;
}
}
}逻辑很简单，就是先全部加，然后在检查一遍又大于10的就取十位来进位，在余。
大数乘法：
最大位数为原来的两倍 则 len * 2
和加一样：先全乘，在算进位。
Char c[len*2] = {0};
Void mul ( char a[],char b[],char c[], )
{
For( I = 0 ；I < len;i++
{for(j = 0 ; j < len ; j ++)
{
C [I + j ] += a[j] * b[i];//想不明白就123乘个看看
If(c[i+j])
{ c[I + j +1] += c[I + j ] /10;//和加一样
C[I + j ] %= 10;
}现在 去掉板书，所有人闭眼冥想一下，加和乘的过程，心里再演算一遍，
然后给大家5分钟时间，手写 a*b+a；
随机抽查3个人。同时我在黑板写下面的板书。
大数阶乘：100！
巧用二维数组
Void calc ()
{
I , j ;;
Num[max][len] = {0}
Num [0][0]=1;
Num [1][0]=1;//行代表第几阶。
For( I = 2 ; I <= max ; i++)
For( j = 0 ; j < len ; j++)
{
Num [ I ][ j ] += num[ I – 1] [ j ] *I;//该行该列等于上一行该列乘i
If( num [ I ] [ j ] > = 10)
{
Num[ I ][ j + 1 ] + = num [ I ] [ j ]/10 ;//和加一样，同行下列进位
Num[I ][ j ] %=1 0 ;
}
}这个逻辑，就是循环大行，对每一行的每一列进行乘法运算，然后判断是否超出个位对下列进行进位，因为每一列的运算是上一行对应列的乘i，再加等 本列，所以，进位可以直接隐藏在该列之中，而不用单独开一个t 来保存，
输出的时候，就是选取一个 I 。输出那一行就是 I 的阶乘。同样也是倒着输出。
阶乘的简单问题
阶乘的位数，算stelen
阶乘的每位之和；暴力相加。
二维数组法，算费波纳斯数列的大数。
算卡特兰数列的大数。
第二课时：
问题四：大数减法
问题五：大数除法
问题六：大数求余
现在提升难度啦，首先让我们手算下百位的减法。
那么我们思考下怎么算大数下的减法。
判断大小，最好大减去小。判断补充负号问题。
低位开始对应减。同样要倒叙
处理每一项的时候都先判断能否减去借位，先减去借位，再判断能否减去被减数的该位。再减去。
核心代码
for(i=0;i<k;i++) //逐位进行减法，k是最大最
{
if(n>=0) //正反信息，为正
{
if(num_a[i] >= num_b[i]) 判断当前是否要借位
num_c[i] = num_a[i] – num_b[i];
else
{ //在借位下，前一列减一
num_c[i] = num_a[i] – num_b[i] + 10;
num_a[i+1]–;
}
} 不可以直接strcmp比较。因为长度不一定相同
int compare(char *str_a,char *str_b)
{
int len_a, len_b;
len_a = strlen(str_a); //分别获取大数的位数进行比较
len_b = strlen(str_b);
if ( strcmp(str_a, str_b) == 0 ) //返回比较结果
return 0;
if ( len_a > len_b )
return 1;
else if( len_a == len_b )
return strcmp(str_a, str_b);//长度一样，直接比较大小。
else
return -1;
}
大数余法
D = 0 ;
L = strlen(c);
For( I = 0 ; I < l ; I ++)
{
D = ((d * 10) % n + c[i] – ‘0’)%n; // n 就是 被余 。d 就是最后的余数。
}输出 d
这是个公式记住就好
（A*b）%c = （a%c） * ( b%c ) %c
（A+b）%c = （a%c） +( b%c ) %c
大数除法
大数除小数
/*高精度除低精度求商模板*/
/*大数除法 ——除数为int范围*/
#include<iostream>
#define N 1000
using namespace std;
void division(char * src,int n)
{
int len = strlen(src),i,k,t=0,s=0;
char dest[N];
bool flag = true; //商是否有了第一个有效位，防止商首部一直出现0
for(i=0,k=0; i<len; i++)
{
t = s*10+(src[i]-48); //新余数
if(t/n>0 || t==0) //余数为0要修改商
{
dest[k++] = t/n+48,s = t%n,flag = false;
}
else //不够除，修改余数
{
s = t;
if(!flag) //商已经有有效位了，补零
dest[k++] = ‘0’;
}
}
for(i=0;i<k;i++)
cout<<dest[i];
cout<<endl;
}
int main()
{
char num[N];
int n;
while(scanf(“%s%d”,num,&n)!=EOF)
{
division(num,n);
}
return 0;
}
/*大数除法—高精度除高精度*/
/*
1.a.size<b.size 返回-1
2.a.size=b.size && a-b<0 返回-1
3.a.size=b.size && a-b=0 返回0
*/
#include<iostream>
#include<cstring>
#include<string>
#define N 2000
using namespace std;
//判断a.size 与b.size 的关系 以及做减法
int judge(char a[],int a1,char b[],int b1)
{
int i;
if(a1<b1)return -1;//a.size<b.size
bool flag=false;
if(a1==b1) //a.size==b.size && a<b
{
for(i=a1-1;i>=0;i–)
if(a[i]>b[i])
flag=true;
else if (a[i]<b[i])
{
if(!flag) return -1;
}
}
for(i=0;i<a1;i++)//前提b中b1—a1部分必须为’0′
{
a[i]=a[i]-b[i]+48;//’0’的ASCII为48
if((a[i]-‘0′)<0)
{
a[i]=a[i]+10;a[i+1]=a[i+1]-1;
}
}
for(i=a1-1;i>=0;i–) //返回被除数的长度
if(a[i]!=’0′)
return (i+1);
return 0;//a.size==b.size&&a=b的情况
}
string division(string a,string b)
{
char x1[N],x2[N];
int ans[N];
int a_len,b_len,i,j;
a_len=a.length();
b_len=b.length();
/*初始化部分*/
/*********************************************/
memset(x1,’0′,sizeof(x1));
memset(x2,’0′,sizeof(x2));
memset(ans,0,sizeof(ans));
for(i=a_len-1,j=0;i>=0;i–)
x1[j++]=a[i];
for(i=b_len-1,j=0;i>=0;i–)
x2[j++]=b[i];
/*********************************************/
/*分析部分*/
/*********************************************/
if(a_len<b_len) return “0”;
int temp_len=judge(x1,a_len,x2,b_len);
if(temp_len<0)return “0”;
if(temp_len==0)return “1”;
ans[0]++;//减掉一次，商加1
int ntimes=temp_len-b_len;
if(ntimes<0)
return “1”;
else if(ntimes>0)
//扩充数位，加快减法。
{
for(i=temp_len-1;i>=0;i–)
if(i>=ntimes)
x2[i]=x2[i-ntimes];
else
x2[i]=’0′;
}
b_len=temp_len;
/*********************************************/
/*加快除法的部分*/
/********************************************/
for(j=0;j<=ntimes;j++)
{
int ntemp;
while((ntemp=judge(x1,temp_len,x2+j,b_len-j))>=0)
{
temp_len=ntemp;
ans[ntimes-j]++;
}
}
/*********************************************/
/*处理最后结果进位部分*/
/*********************************************/
for(i=0;i<N;i++)
if(ans[i]>=10)
{
ans[i+1]+=ans[i]/10;
ans[i]%=10;
}
/*********************************************/
/*返回string类型*/
/*********************************************/
int k=N-1;
string c=””;
while(ans[k]==0&&k>0)k–;
for(i=k;i>=0;i–)
c+=(ans[i]+’0’);
/*********************************************/
return c;
}
int main()
{
string a,b;
while(cin>>a>>b)
{
cout<<division(a,b)<<endl;
}
return 0;
}
这里是关于减法的详细代码。
#include<stdio.h>
#include<string.h>
int compare(char *str_a,char *str_b)
{
int len_a, len_b;
len_a = strlen(str_a); //分别获取大数的位数进行比较
len_b = strlen(str_b);
if ( strcmp(str_a, str_b) == 0 ) //返回比较结果
return 0;
if ( len_a > len_b )
return 1;
else if( len_a == len_b )
return strcmp(str_a, str_b);
else
return -1;
}
int main()
{
int f, n， i, k, len_a, len_b;
char str_a[1000], str_b[1000];
int num_a[1000] = {0}; //初始化大数数组，各位全清0
int num_b[1000] = {0};
int num_c[1000];
while (scanf(“%s%s”,str_a,str_b)!= EOF) //可进行多组测试
{
len_a = strlen(str_a); //分别获得两个大数的位数
len_b = strlen(str_b);
k=len_a>len_b?len_a:len_b; //获得最大的位数
num_c[0] = 0;
f = 0;
n = compare(str_a,str_b);//获取正反信息
for (i=0;i<len_a;i++) //颠倒存储
num_a[i] = str_a[len_a-i-1] – ‘0’;
for (i=0;i<len_b;i++)
num_b[i] = str_b[len_b-i-1] – ‘0’;
for(i=0;i<k;i++) //逐位进行减法，k是最大最
{
if(n>=0) //正反信息，为正
{
if(num_a[i] >= num_b[i]) 判断当前是否要借位
num_c[i] = num_a[i] – num_b[i];
else
{ //在借位下，前一列减一
num_c[i] = num_a[i] – num_b[i] + 10;
num_a[i+1]–;
}
}
else //正反信息，为反
{
if( num_b[i] >= num_a[i]) //同上 模拟为b-a
num_c[i] = num_b[i] – num_a[i];
else
{
num_c[i] = num_b[i] – num_a[i] + 10;
num_b[i+1]- -;
}
}
}
if (n<0) //按要求打印
printf(“-“); //输出负号
for (i=k-1; i>=0; i–)
{
if (num_c[i])
f = 1; 寻找第一个不为0的num_c
if (f || i == 0 )
printf(“%d”,num_c[i]);
}
printf(“\n”);
for (i=0;i<k;i++) //清0. 进行下一次操作
{
num_a[i] = 0;
num_b[i] = 0;
}
}
return 0;
}原创文章，转载请注明： 转载自URl-team
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2015-08-012，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读