devbox
小丑西瓜9
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

大数问题（合辑）_大数存储问题 题目:读入n,m,输出 n!*m!. (1<=n,m<=100) 结果的位数不超过40

作者：小丑西瓜9 | 2024-04-16 03:36:29

赞

踩

大数存储问题 题目:读入n,m,输出 n!*m!. (1<=n,m<=100) 结果的位数不超过400. 提

今天给学弟学妹们讲大数问题，自己又把大数问题好好的复习了一遍，用c重新实现了一下；除法还是有点复杂，有点没搞清，所以就不误人子弟了，把大数的加法，乘法，减法，阶乘都自己写了一遍，对大数问题又加深了一点，大精度的还是要慢慢的积累，java版本的上次已经写了；加一个自己的传送门；java写真的是挺方便的啊；java大数

一些基本数据类型的范围：

int：32位整数，占4字节，-2^31~2^31-1(-21亿多~21亿多)
unsigned int：占4字节，0~2^32-1(0~42亿多) –10位数

VC的64位整数 ：
__int64：占8字节，-2^63~2^63-1（-900亿亿多~900亿亿多）
unsigned __int64:占8字节，0~2^64-1(0~1800亿亿多)-20位数
G++的64位整数：
long long==__int64
unsigned long long==unsigned __int64

实数
float：占4字节，7位有效数字
double：占8字节，15位有效数字
浮点型的问题都是追求精度的，在一般情况下我们应当选择使用double，而很少用float；

所以当我们要进行计算的数超过了20位，我们就要用数组来模拟我们的计算过程了；

选取的是poj百练上的比较基础的例题，从基础的开始做，只要弄懂就好，积累自己的模板，再灵活运用；


2981:大整数加法   http://bailian.openjudge.cn/practice/2981


其实大整数的加法之类的，算法都比较简单，按照我们平时竖式计算的方式，用数组模拟大数的加法，要注意的就是处理好之间的进位问题，然后其中的输入输出也要注意，转化成我们习惯的那种方式去进行计算，输出的时候要处理好前端零；
主要是要理解这种处理方式；
下面是代码：代码就是随便写一下的，还可以进行优化，并不是最简的，能够易于理解就好； 
  1. #include <cstdio>
  2. #include <cstring>
  3. char a[220],b[220];
  4. int c[220],d[220];
  5. int result[240];
  6. int main()
  7. {
  8.     int i=0,j=0,lena,lenb,n;
  9.     gets(a);//把数字用字符串保存输入
  10.     gets(b);
  11.     memset(c,0,sizeof(c));//对数组进行初始化
  12.     memset(d,0,sizeof(d));
  13.     memset(result,0,sizeof(result));
  14.     lena=strlen(a);
  15.     lenb=strlen(b);
  16.     n=lena>lenb?lena:lenb;
  17.     for(j=0,i=lena-1;i>=0;i--)//把字符数组倒序转换到数字数组中（满足我们的计算习惯）
  18.         c[j++]=a[i]-'0';
  19.     for(j=0,i=lenb-1;i>=0;i--)
  20.         d[j++]=b[i]-'0';
  21.     for(i=0;i<n;i++)
  22.     {
  23.      result[i]+=c[i]+d[i];//把两个数组相加
  24.       if(result[i]>=10)//处理进位
  25.        {
  26.            result[i+1]++;
  27.            result[i]-=10;
  28.        }
  29.     }
  30.     i=n;
  31.     int flag=0;
  32.     while(!result[i])//处理前端零
  33.     {
  34.         if(i==0)
  35.         {
  36.             flag=1;
  37.             printf("0");
  38.         }
  39.         i--;
  40.     }
  41.     while(i>=0&&flag==0)
  42.     {
  43.         printf("%d",result[i]);
  44.         i--;
  45.     }
  46.     printf("\n");
  47.     return 0;
  48. }

2980:大整数乘法  http://bailian.openjudge.cn/practice/2980


乘法和加法的思想基本上一致，这里要注意的是，i和j位置相乘的结果要保存在结果数组的i+j的位置；
下面是代码； 
  1. #include <cstdio>
  2. #include <cstring>
  3. char a[220],b[220];
  4. int c[220],d[220];
  5. int result[440];
  6. int main()
  7. {
  8.     int i=0,j=0,lena,lenb,n;
  9.     gets(a);//把数字用字符串保存输入
  10.     gets(b);
  11.     memset(c,0,sizeof(c));//对数组进行初始化
  12.     memset(d,0,sizeof(d));
  13.     memset(result,0,sizeof(result));
  14.     lena=strlen(a);
  15.     lenb=strlen(b);
  16.     n=lena>lenb?lena:lenb;
  17.     for(j=0,i=lena-1;i>=0;i--)//把字符数组倒序转换到数字数组中（满足我们的计算习惯）
  18.         c[j++]=a[i]-'0';
  19.     for(j=0,i=lenb-1;i>=0;i--)
  20.         d[j++]=b[i]-'0';
  21.     for(i=0;i<lena;i++)
  22.         for(j=0;j<lenb;j++)
  23.         result[i+j]+=c[i]*d[j];//i*j的结果要保存在i+j的位置
  24.     for(i=0;i<n*2;i++)
  25.     {
  26.         if(result[i]>=10)//处理进位
  27.         {
  28.             result[i+1]+=result[i]/10;
  29.             result[i]%=10;
  30.         }
  31.     }
  32.     i=n*2-1;
  33.     while(result[i]==0) i--; //处理前端零
  34.     while(i>=0)
  35.     {
  36.          printf("%d",result[i]);
  37.          i--;
  38.     }
  39.     return 0;
  40. }

2736:大整数减法   http://bailian.openjudge.cn/practice/2736


减法和加法的思想基本一致；把程序中的加法换成减法，进位处理的时候注意；
下面是代码； 
  1. #include <cstdio>
  2. #include <cstring>
  3. int main()
  4. {
  5.     //freopen("1.txt","r",stdin);
  6.     char a[220],b[220];
  7.     int c[220],d[220];
  8.     int result[240];
  9.     int n,i,j,lena,lenb;
  10.     scanf("%d",&n);
  11.     while(n--)
  12.     {
  13.         scanf("\n%s",a);
  14.         getchar();
  15.         scanf("%s",b);
  16.         memset(c,0,sizeof(c));
  17.         memset(d,0,sizeof(d));
  18.         memset(result,0,sizeof(result));
  19.         lena=strlen(a);
  20.         lenb=strlen(b);
  21.         for(i=lena-1,j=0;i>=0;i--)
  22.            c[j++]=a[i]-'0';
  23.         for(i=lenb-1,j=0;i>=0;i--)
  24.            d[j++]=b[i]-'0';
  25.         for(i=0;i<lena;i++)
  26.             result[i]=c[i]-d[i];
  27.         for(i=0;i<lena;i++)
  28.             if(result[i]<0)//处理小于零的情况
  29.             {
  30.                 result[i]+=10;//向前一位借10；
  31.                 result[i+1]--;
  32.             }
  33.       for(i=lena-1;!result[i]&&i>0;i--);//处理前端零
  34.       for(j=i;j>=0;j--)
  35.        printf("%d",result[j]);
  36.       printf("\n");
  37.     }
  38.     return 0;
  39. }

大数阶乘这里就相当于进行了多次乘法，这里我是用的10000进位，基本思想也是一样的；
下面是代码： 
  1. #include <cstdio>
  2. #include <cmath>
  3. void factorial(int n)
  4. {
  5. int a[10000];
  6. int i,j,c,m=0;
  7. a[0]=1;
  8. for(i=1;i<=n;i++)
  9. {
  10.     c=0;
  11.     for(j=0;j<=m;j++)//m表示的是当前数组的位数
  12.     {
  13.         a[j]=a[j]*i+c;
  14.         c=a[j]/10000;//判断有没有进位
  15.         a[j]=a[j]%10000; //保存进位的数
  16.     }
  17.     if(c>0) {m++;a[m]=c;}
  18. }
  19.    printf("%d",a[m]);
  20.    int w=m*4+log10(a[m])+1;//这里是计算阶乘的总位数 （这里可以不要）
  21.    for(i=m-1;i>=0;i--)
  22.       printf("%0.4d",a[i]);//假如当前位置的数没满4位的话，在前补零
  23.     printf("\n");
  24.     printf("%d",w);//（也可以不要这个输出）
  25. }
  26. int main()
  27. {
  28.     int m;
  29.     while(scanf("%d",&m)!=EOF)
  30.     {
  31.         factorial(m);
  32.     }
  33.     return 0;
  34. }

大数除法还要自己去研究一下~研究好了再更新~









声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小丑西瓜9/article/detail/432145
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号