专栏首页Urlteamacm-大数问题集锦

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 零基础学习 Python 之与函数的初次相见

    大家好,这里是零基础学习 Python 系列,在这里我将从最基本的Python 写起,然后再慢慢涉及到高阶以及具体应用方面。我是完全自学的 Python,所以很...

    Rocky0429
  • 零基础学习 Python 之函数对象

    我在前面的文章提过这么一个概念 「函数也是对象」,那么对于这种对象,是不是有什么特别的应用呢?下面就让我们从这个角度出发再次深入的探究函数。

    Rocky0429
  • 新版 Kite为啥这么火,问就俩字『好用』

    不久前,一个免费的专门针对 Python 的代码补全工具 Kite,有了新的动态。这次,Kite 开发者在之前的基础上,增加了「Intelligent Snip...

    昱良
  • 零基础学习 Python 之类属性

    如果你看过昨天(写个“类”就是这么 so easy)和前天(我与 “类” 的初次相见)的文章相信你已经对 “类” 有了一些基本的认识,为了能给之后的编程打个稍微...

    Rocky0429
  • 零基础学习 Python 之闭包

    在昨天的文章中(零基础学习 Python 之嵌套函数),当需要在函数内部多次执行复杂的任务的时候,嵌套是很有用的,可以避免循环和代码的重复冗余,而嵌套函数可以看...

    Rocky0429
  • 你真的知道什么是 “命名空间” 吗?

    命名空间,又名 namesapce,是在很多的编程语言中都会出现的术语,估计很多人都知道这个词,但是让你真的来说这是个什么,估计就歇菜了,所以我觉得 “命名空间...

    Rocky0429
  • 参数?变量?形参?实参?在 Python 眼里那都不是事。

    函数的参数,我在之前的文章中也提到过,参数这个东西我感觉还是比较有话题的,你可能在某些地方听说过诸如 “形参”,“实参” and so on...那么这些到底是...

    Rocky0429
  • 零基础学习 Python 之初识迭代

    大家好,这里是零基础学习 Python 系列,在这里我将从最基本的Python 写起,然后再慢慢涉及到高阶以及具体应用方面。我是完全自学的 Python,所以很...

    Rocky0429
  • 效率 | 命令行备忘工具navi,快速调用复杂命令

    刚学的一句新命令,才用完就忘了用法?通常情况下,命令后加一句—help就行了。如果能够把自己最想要掌握的命令整理成一份秘籍就好了。这份秘籍最好可以在终端里随时查...

    昱良
  • 零基础学习 Python 之嵌套函数

    我在几天以前的文章中(零基础学习 Python 之函数对象)说过,函数不单单可以作为对象来传递,还可以在一个函数里面嵌套一个函数,这个就是我们今天要讲的嵌套函数...

    Rocky0429

扫码关注云+社区

领取腾讯云代金券