`
弄月吟风
  • 浏览: 199508 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论

ACM高精度运算

阅读更多
#include<stdio.h>
#include<string.h>
char c[2000];//全局变量,存储大数运算的结果
char arr[1000];//高精度除以高精度的余数
long z=0;//高精度除以低精度的余数
int Judge(char ch[])
{//判断字符串ch是否全为,若全为,返回,否则返回

     int i,k;

     k=strlen(ch);

     for(i=0;i<k;i++) if(ch[i]!='0')  return 0;

     return 1;

}

int Compare(char a[],char b[])
{//比较字符串的大小,方法不同于strcmp函数,类似于整型常量的比较

     int lena,lenb,i;

     lena=strlen(a); lenb=strlen(b);

     if(lena<lenb) return -1;

     else if(lena>lenb) return 1;

     else {

         if(strcmp(a,b)==0) return 0;

         else{ for(i=0;i<lena;i++){ if(a[i]>b[i]) return 1; if(a[i]<b[i]) return -1;}

              return 0;

         }}}

/*算法:先确定a和b中的最大位数k,然后依照由低至高位的顺序进行加法运算。

注意进位,若高位有进位,则c的长度为k+1。*/

//高精度加法

void BigNumberAdd(char a1[],char b1[])

{

     int i,j,k,lena,lenb;

     int a[1000]={0},b[1000]={0},d[1000]={0};

     lena=strlen(a1);

     lenb=strlen(b1);

     for(i=0;i<lena;i++) //将加数与被加数化为整型数组,并且该数组的其他位为

         a[i]=a1[lena-i-1]-'0';

     for(i=0;i<lenb;i++)

         b[i]=b1[lenb-1-i]-'0';

     k=lena>lenb?lena:lenb;//当数组除了加数和被加数以外的整型数组元素均为时,无需考虑lena和lenb的大小

     for(i=0;i<k;i++){   d[i]=a[i]+b[i]+d[i];  d[i+1]=d[i+1]+d[i]/10; d[i]=d[i]%10;   }

     while(d[k]) //若高位进

          k++;

     while(!d[k-1])

         k--;//001+0003=4

     for(j=0;j<k;j++) //将整型数组逆着转变并赋值给c字符型数组

         c[j]=d[k-j-1]+'0';

     if(Judge(c))//若全为,则只输出一个

         strcpy(c,"0");

}

/*算法:依照由低位至高位的顺序进行减法运算。在每次位运算中,

若出现不够减的情况,则向高位借位。在进行了la的减法后,若最高

位为,则a的长度减。若A、B大小未知,则需先判断大小。*/

//高精度减法

void BigNumberSub(char a1[],char b1[])
{//a1为被减数,b1为减数

     int lena,lenb,i,j,k,flag;

     int a[1000]={0},b[1000]={0},d[1000]={0};

     lena=strlen(a1);

     lenb=strlen(b1);

     if(Compare(a1,b1)>=0) {//若被减数大于等于减数

         for(i=0;i<lena;i++)  a[i]=a1[lena-1-i]-'0';

         for(i=0;i<lenb;i++)  b[i]=b1[lenb-1-i]-'0';

         flag=0;//结果正的标志

      }

     else {//若被减数小于减数

         for(i=0;i<lenb;i++) a[i]=b1[lenb-1-i]-'0';

         for(i=0;i<lena;i++)  b[i]=a1[lena-1-i]-'0';

         flag=1;//结果负的标志

     }

     k=lena>lenb?lena:lenb;

     for(i=0;i<k;i++)

     {//大数减小数

         if(a[i]<b[i]) {//若被减数不够减,向高位借一位

              a[i+1]--;

              d[i]=a[i]-b[i]+10; }

         else  d[i]=a[i]-b[i];

     }

     //若较高位已为,并且不止位时

     while(!d[i-1])

     {  k--; i--;  }

     //根据flag,输出有无"-"

     if(!flag) { for(i=0;i<k;i++) {//将结果转化为字符逆着赋给数组c

              if(!i&&!d[k-i-1])//若差的第一个字母为,则马上跳过

                   continue;

              c[i]=d[k-i-1]+'0'; } }

     else  { c[0]='-';  for(i=1;i<=k;i++)

         {//将结果转化为字符逆着赋给数组c

              if(i==1&&!d[k-i])//若差的第一个字母为,则马上跳过

                   continue;

              c[i]=d[k-i]+'0';//注意d的下标,不是k-i-1

         }

     }

     if(Judge(c))//若差全为,则只输出一个

         strcpy(c,"0");}

/*算法:将多位数存入数组,低位在前、高位在后,

然后用一位数去乘数组的各位,考虑进位,最后按正常顺序输出*/

//高精度乘法--高精度乘以低精度

void BigNumMultiSmall(char a1[],int b1)
{ int i,j,t;

     int a[2000]={0};

     //将字符串转化为整型数组,并逆置

     t=strlen(a1);

     for(i=0;i<t;i++)  a[i]=a1[t-1-i]-'0';

     //整型数组的每个元素乘以b1,然后对其进行求余,整除,使其只有一位数

     a[0]=a[0]*b1;

     for(i=1;i<t;i++) { a[i]*=b1;  a[i]+=a[i-1]/10; a[i-1]=a[i-1]%10; }

     while(a[i-1]>9)

     {//若最后一个元素大于

         a[i]=a[i-1]/10;  a[i-1]=a[i-1]%10;  i++;

     }

     //将得到的整型数组逆置赋给字符串

     for(j=0;j<i;j++)

         c[j]=a[i-j-1]+'0';

     if(Judge(c))//若积全为,则只输出一个

         strcpy(c,"0");

}

//高精度乘法--高精度乘以高精度

void BigNumMultiBig(char a1[],char b1[])
{  int i,j,k,lena,lenb;

     int a[1000]={0},b[1000]={0},d[2000]={0};

     //将字符串转化为整型数组,并逆置

     lena=strlen(a1);  lenb=strlen(b1);

     for(i=0;i<lena;i++)

         a[i]=a1[lena-i-1]-'0';

     for(i=0;i<lenb;i++)

         b[i]=b1[lenb-i-1]-'0';

     //计算乘数从低位到高位以此乘以被乘数的低位到高位

     for(i=0;i<lena;i++)

         for(j=0;j<lenb;j++){   d[i+j]=d[i+j]+a[i]*b[j]; d[i+j+1]+=d[i+j]/10;  d[i+j]=d[i+j]%10; }

         //根据高位是否为判断整型数组的位数

         k=lena+lenb;

         while(!d[k-1])

              k--;

         //积转化为字符型

         for(i=0;i<k;i++) c[i]=d[k-1-i]+'0';

         if(Judge(c))//若积全为,则只输出一个

              strcpy(c,"0");

}

//整型常量的阶乘

void BigNumFact(int x)
{   int i,k,m=0,a[1000]={0};

     a[0]=1;

  for(;x;x--)

     {//m为在求阶乘过程中a的元素个数

         for(k=i=0;i<=m;i++)  {  k=k+a[i]*x;//数组各个元素均乘以x(x递减),以完成阶乘的运算

              a[i]=k%10;

              k/=10;

         }

         while(k) { a[++m]=k%10;  k/=10; }

     }

     //阶乘的结果转化为字符型

     for(i=0;i<=m;i++) c[i]=a[m-i]+'0';

     if(Judge(c))//若结果全为,则只输出一个

         strcpy(c,"0");

}

//1-整型常量的阶乘和

void BigNumFactAdd(int t)
{

     int i;

     char sum[2000],d[2000];

     //对字符串进行初始化

     memset(d,0,sizeof(d)); memset(sum,0,sizeof(sum));

     //分别求出相应i的阶乘然后相加

     for(i=t;i>0;i--)  { BigNumFact(i);  strcpy(d,c);  memset(c,0,sizeof(c));  BigNumberAdd(d,sum); strcpy(sum,c);

 memset(c,0,sizeof(c)); }

     strcpy(c,sum);//将结果赋值给全局变量,进行输出

}

 

//高精度的乘方,幂数为整型常量

void BigNumInvol(char a1[],int b1)
{  int i;

     char temp[1000];

   strcpy(temp,a1);//注意乘方是自己乘自己,而不是结果乘结果

  for(i=2;i<b1;i++)  {  BigNumMultiBig(a1,temp); strcpy(temp,c);  memset(c,0,sizeof(c));//将c清空,防止出现错误

     }

     //进行最后一次乘法

     BigNumMultiBig(a1,temp); if(Judge(c))//若结果全为,则只输出一个

         strcpy(c,"0");}

//高精度除法--高精度除以低精度,只产生余数

int BigNumDividSmall(char a1[],int b1)
{ if(!b1)  return 0;

     int i,j,k,flag=0,a[1000]={0};

     char b[2000];

     memset(b,0,sizeof(b));

     k=strlen(a1);

   for(i=0;i<k;i++)  a[i]=a1[i]-'0';

     z=0; for(i=0;i<k;i++) {  z=a[i]+z*10;  b[i]=z/b1+'0';  z=z%b1;  }

     i=j=0;

     while(b[i++]=='0');

     for(i=i-1;i<k;i++) c[j++]=b[i];

     return 1;

}

//高精度除法--高精度除以高精度,只产生余数

void BigNumDividBig(char a1[],char b1[])
{

     char a[1000],b[1000],time[1000];

     int lena1,lentime,i,j,k,flag=0;

    emset(arr,0,sizeof(arr));

     //若被除数小于除数,则商为,余数为被除数

     if(Compare(a1,b1)<0)  strcpy(arr,a1);

     //若两数相等,则商为,余数为

     else if(!Compare(a1,b1))  c[0]='1';

     //若被除数大于除数

     else{  j=lentime=0; lena1=strlen(a1); memset(b,0,sizeof(b));  memset(time,0,sizeof(time));

         for(i=0;i<lena1;i++)

         {//计算得到被除数的前几位,得到整型数组形式的商

              //time的一个元素表示一次相除的商

              b[j++]=a1[i];  flag=0;

              while(Compare(b,b1)>=0) {BigNumberSub(b,b1);strcpy(b,c);memset(c,0,sizeof(c));time[lentime]++;flag=1;//控制time的元素的位置

              }

              if(flag)//将商转换为字符

                   time[lentime]+='0';

              else//当被除数前几位小于除数,商补

                   time[lentime]='0';

              if(!strcmp(b,"0"))//若b为‘’

                   j=0;

              else//继续在b的后面加值

                   j=strlen(b);

              lentime++; }

         k=0;

         for(i=0;i<lentime;i++)

              if(time[i]!='0')break;//找到time数组中第一个不为的位置

         for(j=i;j<lentime;j++)  c[k++]=time[j];

         strcpy(arr,b);  }

     if(Judge(c))strcpy(c,"0");

     if(Judge(arr)) strcpy(arr,"0");

}

int main()

{

     int flag=0,a3,k,i;

     char a2[1000],b2[1000];

     printf("说明:该程序适用于正整数的高精度运算,并且运算结果的位数在位以内。\n");

     while(1) {

         printf("/************************/\n");printf("1、两数相加\n"); printf("2、两数相减\n"); printf("3、大数与低精度相乘\n"); printf("4、大数与大数相乘\n");  printf("5、大数的阶乘\n");  printf("6、大数的阶乘和\n"); printf("7、大数的乘方\n"); printf("8、大数除以低精度\n"); printf("9、大数除以大数\n");  printf("10、退出\n"); printf("/************************/\n"); printf("请输入你想要进行的操作数:"); scanf("%d",&k); 

        getchar();memset(c,0,sizeof(c));

         switch(k) {

         case 1:  printf("请输入您想要进行运算的两个数字:\n");  scanf("%s%s",a2,b2);  BigNumberAdd(a2,b2);

         printf("%s+%s=%s\n\n",a2,b2,c); break;

         case 2:  printf("请输入您想要进行运算的两个数字:\n");scanf("%s%s",a2,b2); BigNumberSub(a2,b2);

              printf("%s-%s=%s\n\n",a2,b2,c); break;

         case 3: printf("请输入您想要进行运算的两个数字:\n");scanf("%s%d",a2,&a3); BigNumMultiSmall(a2,a3);

              printf("%s*%d=%s\n\n",a2,a3,c); break;

         case 4: printf("请输入您想要进行运算的两个数字:\n");scanf("%s%s",a2,b2); BigNumMultiBig(a2,b2);

              printf("%s*%s=%s\n\n",a2,b2,c); break;

         case 5:  printf("请输入您想要的阶乘数:"); scanf("%d",&a3); BigNumFact(a3);printf("%d!=%s\n\n",a3,c); break;

         case 6:  printf("请输入您想要的阶乘数:");  scanf("%d",&a3); if(!a3) { printf("0!=1\n\n");  continue; }

             BigNumFactAdd(a3); for(i=1;i<=a3;i++) {  printf("%d!",i);  if(i!=a3)  printf("+"); }

              printf("=%s\n\n",c); break;

         case 7: printf("请输入您想要进行运算的两个数字:\n");  scanf("%s%d",a2,&a3);  BigNumInvol(a2,a3);

              printf("%s^%d=%s\n\n",a2,a3,c);  break;

         case 8: printf("请输入您想要进行运算的两个数字:\n");  scanf("%s%d",a2,&a3);if(BigNumDividSmall(a2,a3)) 

         { if(!z)  printf("%s/%d=%s\n\n",a2,a3,c);

         else   printf("%s/%d=%s……%ld\n\n",a2,a3,c,z); } else  printf("0不能作除数。\n\n"); break;

         case 9:printf("请输入您想要进行运算的两个数字:\n"); scanf("%s%s",a2,b2); if(Judge(b2))  printf("0不能作除数。\n\n");

               else { BigNumDividBig(a2,b2); if(!Judge(arr)) printf("%s/%s=%s……%s\n\n",a2,b2,c,arr);

                   else printf("%s/%s=%s\n\n",a2,b2,c);  }break;

         case 10:flag=1;printf("感谢您的使用,再见。\n\n");break;

         default: printf("对不起,您的输入有误,请重新输入。\n\n");  }

         if(flag) break;} return 0;}
分享到:
评论

相关推荐

    ACM高精度计算

    ACM高精度计算.ACM高精度计算.ACM高精度计算.ACM高精度计算.ACM高精度计算.

    ACM高精度计算,非常详细适合入门

    在ACM(国际大学生程序设计竞赛)中,高精度计算是一项重要的技能,特别是在处理需要大量精确数字运算的问题时。本文将详细介绍如何进行高精度计算,特别是针对初学者的入门指导。 传统的C/C++语言中,基本的数据类型...

    ACM高精度运算ACM(ACM high precision operation ACM).pdf

    ACM高精度运算ACM(ACM high precision operation ACM)

    ACM高精度计算.ppt

    在ACM(国际大学生程序设计竞赛)中,高精度计算问题一直是参赛选手们必须面对的一道难关。这类问题主要涉及处理超出标准数据类型存储范围的大整数运算,如加法、减法、乘法等。本文将集中讨论大整数加法和乘法的...

    ACM模拟与高精度计算

    ACM模拟与高精度计算,具有大量的例题以及对应的详尽的题解与参考标准程序,适合acm入门者,以及应对ccf考试以及算法面试等等,很好理解

    北大ACM高精度幂

    根据给定的信息,本文将详细解释“北大ACM高精度幂”的相关知识点,包括高精度幂的概念、实现原理以及代码中的关键部分。 ### 高精度幂的概念 在计算机科学领域,“高精度幂”通常指的是计算非常大的数字的幂运算...

    acm大数高精度模板

    本文将深入解析一个ACM竞赛中常用的高精度计算模板,并详细介绍其工作原理及使用方法。 #### 二、高精度计算模板详解 ##### 2.1 类定义:BigInt ```cpp struct BigInt { int Len; int Data[Capacity]; BigInt...

    ACM必做50题的解题-高精度

    高精度计算解题思路 ...高精度计算是ACM竞赛中非常重要的一部分,本文详细介绍了高精度计算的解题思路,包括将小数转换成整数、大数阶乘思想、输出要求的考虑等。这些知识点对于ACM竞赛的高精度计算题目非常重要。

    数组型高精度算法 ACM竞赛常用算法

    在实际应用中,如ACM竞赛等场合,经常需要用到高精度算法来解决涉及大数运算的问题。常见的高精度算法包括加法、减法、乘法和除法等基本运算,以及更高级的操作如幂运算等。 #### 二、高精度数 ##### 高精度数的...

    基础算法-高精度计算(c/c++)|信息学奥赛、ACM、蓝桥杯

    我们可以利用程序设计的方法去实现这样的高精度计算。介绍常用的几种高精度计算的方法。 适合人群:acm、蓝桥杯、信息学奥赛等算法竞赛 能学到:基本的高精度计算的方法 阅读建议:理解代码并进行实践

    acm.rar_高精度算法

    在ACM(国际大学生程序设计竞赛)中,高精度算法是一种关键技能,它涉及处理大整数的运算,包括加法、减法、乘法和除法。这些运算在常规的计算机语言中可能会超出整数类型的限制,因此需要特别的设计和实现。下面将...

    用高精度算N阶乘,编程语言c++,acm经典题型之一...

    总结起来,实现高精度计算N阶乘是ACM中的一个经典问题,涉及到大数的表示、运算以及算法优化等多个方面的知识。通过解决这个问题,不仅可以提升编程技能,还能深入理解高精度计算的原理和方法。

    高精度课件

    10. **性能优化**:在实现高精度运算时,应注重代码的效率,例如减少不必要的拷贝操作,利用缓存局部性等。 通过学习这个高精度课件,你可以深入了解这些概念并实践相关算法,从而在ACM比赛中解决涉及大整数运算的...

    ACM常用函数

    ACM 编程队伍内部的常用函数库,涵盖了数学问题、字符串处理、计算几何、数论、图论、高精度运算等多个领域,提供了详细的函数实现代码和说明。 数学问题 1. 精度计算——大数阶乘:实现了大数阶乘的计算,使用了...

    高精度运算加法乘法减法除法算法

    高精度运算加法乘法减法除法算法 高精度运算加法乘法减法除法算法是指在计算机科学中对大整数进行运算的...8. 高精度运算的应用:高精度运算可以在实际应用中发挥重要作用,例如在密码学、科学计算和金融计算等领域。

    ACM常用算法介绍 ACM常用算法介绍

    在大数乘小数时,也需要注意精度的问题,使用高精度算术库或自行实现高精度算法可以解决这个问题。 3. 精度计算——乘法(大数乘大数) 大数乘大数时,需要使用高精度算术库或自行实现高精度算法来避免溢出或精度...

    acm.zip_acm.zip

    高精度计算涉及大整数的加减乘除、模运算、幂运算等,这些问题无法直接用标准库函数解决,需要我们自定义算法。例如,我们可以使用数组存储多位数,然后逐位进行运算。在ACM中,高精度计算经常出现在数论问题、组合...

    高精度1906,1965

    通过阅读和理解这些代码,我们可以学习到具体的算法实现细节,包括如何组织数据结构,如何高效地进行高精度运算,以及如何优化代码以满足时间限制。对于初学者,这是一个很好的学习资源,可以从中学习到如何处理实际...

    中山大学ACM模板

    高精度运算在编程竞赛中非常常见,因为输入或输出的数据规模往往超过了标准数据类型所能表示的范围。模板提供了大数与单精度数、大数与大数之间的运算实现,通过自定义类型和函数来处理大数的加减乘除运算。例如,...

Global site tag (gtag.js) - Google Analytics