大数加法

骑猪看日落 2022-05-28 11:26 227阅读 0赞

<table> 
 <tbody> 
  <tr> 
   <td align="center"><h1 style="color:#1a5cc8;"><span style="font-size:14px;">A + B Problem II</span></h1><span style="font-size:14px;"><strong><span style="font-family:Arial;color:rgb(0,128,0);">Time Limit: 2000/1000 MS (Java/Others)&nbsp;&nbsp;&nbsp;&nbsp;Memory Limit: 65536/32768 K (Java/Others)<br>Total Submission(s): 408777&nbsp;&nbsp;&nbsp;&nbsp;Accepted Submission(s): 79219<br></span></strong><br><br></span> 
    <div> 
     <span style="font-size:14px;">Problem Description</span> 
    </div> 
    <div> 
     <span style="font-size:14px;">I have a very simple problem for you. Given two integers A and B, your job is to calculate the Sum of A + B.<br></span> 
    </div> 
    <div> 
     <span style="font-size:14px;">&nbsp;</span> 
    </div><span style="font-size:14px;"><br></span> 
    <div> 
     <span style="font-size:14px;">Input</span> 
    </div> 
    <div> 
     <span style="font-size:14px;">The first line of the input contains an integer T(1&lt;=T&lt;=20) which means the number of test cases. Then T lines follow, each line consists of two positive integers, A and B. Notice that the integers are very large, that means you should not process them by using 32-bit integer. You may assume the length of each integer will not exceed 1000.<br></span> 
    </div> 
    <div> 
     <span style="font-size:14px;">&nbsp;</span> 
    </div><span style="font-size:14px;"><br></span> 
    <div> 
     <span style="font-size:14px;">Output</span> 
    </div> 
    <div> 
     <span style="font-size:14px;">For each test case, you should output two lines. The first line is "Case #:", # means the number of the test case. The second line is the an equation "A + B = Sum", Sum means the result of A + B. Note there are some spaces int the equation. Output a blank line between two test cases.<br></span> 
    </div> 
    <div> 
     <span style="font-size:14px;">&nbsp;</span> 
    </div><span style="font-size:14px;"><br></span> 
    <div> 
     <span style="font-size:14px;">Sample Input</span> 
    </div> 
    <div> 
     <pre></pre> 
     <div style="font-family:'Courier New', Courier, monospace;"> 
      <span style="font-size:14px;">21 2112233445566778899 998877665544332211</span> 
     </div> 
    </div> 
    <div> 
     <span style="font-size:14px;">&nbsp;</span> 
    </div> 
    <div> 
     <span style="font-size:14px;">Sample Output</span> 
    </div> 
    <div> 
     <pre></pre> 
     <div style="font-family:'Courier New', Courier, monospace;"> 
      <span style="font-size:14px;">Case 1:1 + 2 = 3Case 2:112233445566778899 + 998877665544332211 = 1111111111111111110</span> 
     </div> 
    </div> 
    <div> 
     <span style="font-size:14px;">&nbsp;</span> 
    </div><span style="font-size:14px;"><br></span> 
    <div> 
     <span style="font-size:14px;">Author</span> 
    </div> 
    <div> 
     <span style="font-size:14px;">Ignatius.L</span> 
    </div> 
    <div> 
     <span style="font-size:14px;">&nbsp;</span> 
    </div><span style="font-size:14px;"><br></span> 
    <div> 
     <span style="font-size:14px;">Recommend</span> 
    </div> 
    <div> 
     <span style="font-size:14px;">We have carefully selected several similar problems for you:&nbsp;&nbsp;<a href="http://acm.hdu.edu.cn/showproblem.php?pid=1004" rel="nofollow">1004</a>&nbsp;<a href="http://acm.hdu.edu.cn/showproblem.php?pid=1003" rel="nofollow">1003</a>&nbsp;<a href="http://acm.hdu.edu.cn/showproblem.php?pid=1008" rel="nofollow">1008</a>&nbsp;<a href="http://acm.hdu.edu.cn/showproblem.php?pid=1005" rel="nofollow">1005</a>&nbsp;<a href="http://acm.hdu.edu.cn/showproblem.php?pid=1020" rel="nofollow">1020</a>&nbsp;</span> 
    </div> 
    <div> 
     <span style="font-size:14px;">&nbsp;</span> 
    </div><span style="font-size:14px;"><br></span>  <span style="font-size:14px;"><a href="http://acm.hdu.edu.cn/statistic.php?pid=1002" rel="nofollow">Statistic</a>&nbsp;|&nbsp;<a href="http://acm.hdu.edu.cn/submit.php?pid=1002" rel="nofollow">Submit</a>&nbsp;|&nbsp;<a href="http://acm.hdu.edu.cn/discuss/problem/list.php?problemid=1002" rel="nofollow">Discuss</a> | <a href="http://acm.hdu.edu.cn/note/note.php?pid=1002" rel="nofollow">Note</a><br></span> </td> 
  </tr> 
  <tr> 
   <td> 
    <table style="font-size:14px;border-top:#1a5cc8 1px solid;border-right:#1a5cc8 1px solid;border-bottom:#1a5cc8 1px solid;border-left:#1a5cc8 1px solid;"> 
     <tbody> 
      <tr> 
       <td><span style="font-size:14px;"><a href="http://acm.hdu.edu.cn/" rel="nofollow">Home</a> | <a href="http://acm.hdu.edu.cn/showproblem.php?pid=1002#top" rel="nofollow">Top</a></span></td> 
       <td style="padding-bottom:6px;padding-top:6px;padding-left:6px;padding-right:6px;"><span style="font-size:14px;">Hangzhou Dianzi University Online Judge 3.0<br>Copyright © 2005-2018 <a href="mailto:acm@hdu.edu.cn" rel="nofollow">HDU ACM Team</a>. All Rights Reserved.<br><a href="http://acm.hdu.edu.cn/about_us/developer.php" rel="nofollow">Designer &amp; Developer </a>: Wang Rongtao&nbsp;LinLe&nbsp;<a href="mailto:gjavac@gmail.com" rel="nofollow">GaoJie</a>&nbsp;<a href="mailto:gl8997@gmail.com" rel="nofollow">GanLu</a><br><span>Total 0.000000(s) query 5, Server time : 2018-04-04 12:55:52, Gzip enabled</span></span></td> 
       <td><span style="font-size:14px;"><br></span></td> 
      </tr> 
     </tbody> 
    </table></td> 
  </tr> 
 </tbody> 
</table>

![70][]

/*
    	大数加法采用的是模拟的思想，就是利用数组来储存一个数的每一位 
    */
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    const int MAXN=10000;
    char s1[MAXN],s2[MAXN];
    int n1[MAXN],n2[MAXN],sum[MAXN];
    int main()
    {
    	int T;
    	scanf("%d",&T);
    	for(int k=1;k<=T;k++)
    	{
    		scanf("%s %s",s1,s2);//用字符串来储存两个大数 
    		memset(n1,0,sizeof(n1));//初始化数组，让它们全为0 
    		memset(n2,0,sizeof(n2));
    		memset(sum,0,sizeof(sum));//初始化保存结果的数组 
    		int len1=strlen(s1);//第一个数的长度 
    		int len2=strlen(s2);//第二个数的长度 
    		int j=0;
    		for(int i=len1-1;i>=0;i--)//将第一个数的每一位都逆序赋值给第一个数组 
    			n1[j++]=s1[i]-'0';
    		j=0;	
    		for(int i=len2-1;i>=0;i--)
    			n2[j++]=s2[i]-'0';
    		int len=len1>len2?len1:len2;//找出来两个数中比较长的那个数 
    		int pre=0;//用来保存进位 
    		for(int i=0;i<len;i++)//给sum赋值，要记得sum可能是大于9的，输出的时候要对10取余 
    		{
    			sum[i]=n1[i]+n2[i]+pre/10;	
    			pre=sum[i];
    		}
    		if(pre>9)//保存最高位的是sum[len-1] ，如果大于9 ，结果的位数要加一 
    		{
    			sum[len]=pre/10;//取高位 
    			len++;//位数 +1
    		}
    		int t=len;
    		for(int i=len-1;i>=0;i--)	//去掉前置0 
    		{
    			if(sum[i]==0)	t--;//像 0001 + 3 这种，结果应该输出 4 而不是0004 
    			else			break;
    		}
    		printf("Case %d:\n%s + %s = ",k,s1,s2);
    		for(int i=t-1;i>=0;i--)		
    			printf("%d",sum[i]%10);
    		printf("\n");
    		if(k!=T)	printf("\n");//最后一组数据不要空行 
    	 } 
    	return 0;
    }

[70]: /images/20220528/bf36933981bb4a399a12e19fb51a40bd.png