NOI OJ 1.6 10:大整数加法 C语言

描述

求两个不超过200位的非负整数的和。

输入

有两行，每行是一个不超过200位的非负整数，可能有多余的前导0。

输出

一行，即相加后的结果。结果里不能有多余的前导0，即如果结果是342，那么就不能输出为0342。

有一说一我本人是不大想讲的，因为这个题考的就是你们的思路，算是oj上的第一大难点吧（事实上就是我懒，讲解一遍太费力了）。但是，我看很多同学都卡死在这道题，一筹莫展，我就感到十分的悲痛，宝贵的刷题时光就这样浪费了，多可惜。所以我写了这篇文章给那些想了很久但是真的没什么思路的同学（那些没想过的最好别看，因为这只是我的思路，说不定你能想到更好的，这篇文章只是帮助这些同学用我自认为比较“笨”方法来做出这道题，来拓展一下他们局限的思路）废话不多说了，我们正式开始。

难点1：本题之所以难就难在他给的数据太大了，远远超出了int 甚至long long的范围（仅限于c，python和java没有这方面的问题）所以第一步我们要知道如何输入数据

我是是用字符串的方式进行输入的，为什么用字符串不用数组呢

因为字符串输入很方便，直接一个%s，这一行的数据都可以直接输入了（也可以用gets，我本人喜欢用gets），我们可以很轻易的定义一个长度很大的字符串，这样就可以确保我们的数据都可以输入进去。

这个不是完整代码，只是讲输入的代码。我定义了一个长度为201的字符串（题目要求不超过长度200）

#include<stdio.h> #include<string.h> int main(){ char x[201]; char y[201]; gets(x); gets(y); int len1=strlen(x),len2=strlen(y); //用strlen函数来检测字符串长度 }

这里我们要测量出我们输入数据的长度（后面会讲解有什么用），使用strlen()函数要在前面加个#include<string.h>（和math.h一个道理）

strlen的作用：测量字符串的长度，比如我输入一个“1000000”的字符串，用strlen就可以测出它的长度为7。

难点2：我是用字符串的方式输入的，但是计算时用字符串会很麻烦，并且需要重新排序后才可以更方便的进行计算（加法有进一）。

所以我就把字符串内的数据转化成int的形式重新转入数组中（毕竟这章节要用数组，所以转回去也比较好解释）

int a[201]={0}; //代表字符串x（全部初始化为0） int b[201]={0}; //代表字符串y int c[201]={0}; //这是我定义输出的数组c int len=201; //因为我定义的数组大小为201，所以我这里定义一个长度为201的变量len for(int i=0;i<len1;i++){ a[len-len1]=x[i]-'0'; //这里具体解释往下看（flag1） len++; } len=201; for(int i=0;i<len2;i++){ b[len-len2]=y[i]-'0'; len++; }

这里写了个伪代码来把字符串的数据代入数

flag1：这里讲解一下为什么我设一个len=200。我的想法是，从后往前排也就是我们平时见到数字排序的方法，这样的话比较直观好理解，所以我是这样一个个数字排进去的从最大位到最小位（见下表格）

假设我们输入一个1890，在数组中就是这样

这样在之后的计算中我们用同位的数组相加就行了，逢10进一，这就是我们下一步该干的事，这一步比较简单，我直接放出来了

if(len1>=len2){ //这里我把它分成了两种情况（等于的情况放在哪里都是可以的） for(int i=200;i>=200-len1;i--){ //分成两种情况的好处是可以知道最大的数据的长度，循环到比最大位多一位就行了（加法只能进一位） c[i]+=a[i]+b[i]; //我们把数组a+b的值放入数组c中 if(c[i]>=10){ //逢10进一 c[i]-=10; c[i-1]+=1; } } int flag=0; //这里定义一个flag方便之后的前面的清零，保证不会输出012这种情况 for(int i=0;i<=200;i++){ if(flag==0&&c[i]!=0){ //们从最初位往后排,直到不为0的最大项，我们就可以改变flag，让他之后（包括本身）的数据都能输出 flag=1; } if(flag==1){ printf("%d",c[i]); } } } else{ for(int i=200;i>=200-len2;i--){ //同上，只是数据最长值换了一下 c[i]+=a[i]+b[i]; if(c[i]>=10){ c[i]-=10; c[i-1]+=1; } } int flag=0; for(int i=0;i<=200;i++){ if(flag==0&&c[i]!=0){ flag=1; } if(flag==1){ printf("%d",c[i]); } } }

以上就是我个人大整数加法的做法了，比较憨憨，希望大家能够理解吧。

下面把完整的代码发出来（如果你认为对你有用的话不妨点个赞）

#include<stdio.h> #include<string.h> int main(){ char x[201]; char y[201]; int a[201]={0}; int b[201]={0}; int c[201]={0}; gets(x); gets(y); int len1=strlen(x),len2=strlen(y); int len=201; for(int i=0;i<len1;i++){ a[len-len1]=x[i]-'0'; len++; } len=201; for(int i=0;i<len2;i++){ b[len-len2]=y[i]-'0'; len++; } if(len1==1&&len2==1){ if(a[200]==0&&b[200]==0){ printf("0"); return 0; } } if(len1>=len2){ for(int i=200;i>=200-len1;i--){ c[i]+=a[i]+b[i]; if(c[i]>=10){ c[i]-=10; c[i-1]+=1; } } int flag=0; for(int i=0;i<=200;i++){ if(flag==0&&c[i]!=0){ flag=1; } if(flag==1){ printf("%d",c[i]); } } } else{ for(int i=200;i>=200-len2;i--){ c[i]+=a[i]+b[i]; if(c[i]>=10){ c[i]-=10; c[i-1]+=1; } } int flag=0; for(int i=0;i<=200;i++){ if(flag==0&&c[i]!=0){ flag=1; } if(flag==1){ printf("%d",c[i]); } } } return 0; }