首页 > 代码库 > 被限制的加法（高精入门）
被限制的加法（高精入门）
题目：仅用不超过10个的变量，变成计算出两个等长的N(1<N<10^7)位正整数A,B(无前导0)相加的结果。
输入格式：第一行一个数N，表示位数，后面有N行，每行两个数字，表示A、B相对位的两个数，输入的格式是从最高位开始到最低位。
输出格式：输出两数的和
输入样例：
4
1 1
2 3
0 5
3 7
输出样例：
2560
思路：由于内存的限制只能考虑从高位到低位的算法，即读一行数据就处理一行数据。
显然，问题的关键是要解决进位引起的麻烦。由于只是两个数字相加，最多只会对上一位有进位1，而引发连续进位的只有一种情况：出现连续的9时后面出现了进位。如99 999+1。
因此，可分三种情况处理：
(1)当前计算的两个同位数的和sum<9时，前位计算的结果不会受以后进位的影响，则可以输出之前的计算结果。
(2)当前计算的两个同位数的和sum=9时，则使用变量n9记录连续9的个数，这样可以处理以后可能的连续进位了。
(3)当前计算的两个同位数的和sum>9时，引发高位的进位，则输出进位后的高位值，并将之前积累的连续n9个9以0输出
1 #include<iostream> 2 #include<cstdio> 3 using namespace std; 4 int n,a,b,c,n9,sum,i,j; 5 bool first; 6 int main() 7 { 8 ios::sync_with_stdio(false); 9 cin>>n; 10 first=1; 11 c=0; 12 n9=0;//n9表示之前累积的9的个数 13 for(i=1;i<=n;i++)//从高位开始，依次处理每一位 14 { 15 cin>>a>>b; 16 sum=a+b; 17 if(sum<9)//无进位情况 18 { 19 if(c>0||first==0)//避免前导零 20 cout<<c; 21 for(j=1;j<=n9;j++)//因为该位无进位，则可将之前积累的999...999 以000...000输出 22 cout<<9; 23 first=0; 24 n9=0;//积累的999...999已输出，因此设为0 25 c=sum; 26 } 27 else 28 if(sum==9)//为9时，只要记录9的个数 29 n9++; 30 else//大于9，即产生进位情况 31 { 32 c++;//进位后输出 33 cout<<c; 34 for(j=1;j<=n9;j++)//因为进位，则将前面积累的999...999以000...000输出 35 cout<<0; 36 first=0; 37 n9=0;c=sum-10; //c记录该位数进位后余下的数 38 } 39 } 40 41 cout<<c; 42 for(j=1;j<=n9;j++)//处理剩下的一段999...999 43 cout<<9; 44 return 0; 45 }
被限制的加法（高精入门）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。