526互联

PAT Basic 1113. 钱串子的加法

发布时间 2023-04-19 16:58:52作者: 十豆加日月

PAT Basic 1113. 钱串子的加法

1. 题目描述：

qcz.JPG

人类习惯用 10 进制，可能因为大多数人类有 10 根手指头，可以用于计数。这个世界上有一种叫“钱串子”（学名“蚰蜒”）的生物，有 30 只细长的手/脚，在它们的世界里，数字应该是 30 进制的。本题就请你实现钱串子世界里的加法运算。

2. 输入格式：

输入在一行中给出两个钱串子世界里的非负整数，其间以空格分隔。

所谓“钱串子世界里的整数”是一个 30 进制的数字，其数字 0 到 9 跟人类世界的整数一致，数字 10 到 29 用小写英文字母 a 到 t 顺次表示。

输入给出的两个整数都不超过 \(10^5\) 位。

3. 输出格式：

在一行中输出两个整数的和。注意结果数字不得有前导零。

4. 输入样例：

2g50ttaq 0st9hk381

5. 输出样例：

11feik2ir

6. 性能要求：

Code Size Limit
16 KB
Time Limit
400 ms
Memory Limit
64 MB

思路：

题目指出两个整数的最大位数为\(10^5\)，且因为是30进制，含有小写英文字母，那就只能将两数存储为字符串。这里宏定义MAX_LEN为\(10^5+1\)，表示最大位数加1个'\0'的长度，分别定义num1[MAX_LEN]、num2[MAX_LEN]和res[MAX_LEN]存储两个非负整数和求和结果，首先比较两个非负整数的长度，在较短长度的非负整数前补0，然后就是从末位开始对每一位进行求和，做好进位即可。另外需要注意的地方有：

  • 加法进位的规则：对于 \(N\) 进制来说，每一位上的数字最大为 \(N-1\) ，那么每一位上的两数相加最大为 \(2(N-1)\) ，考虑到有进位的情况也最多为 \(2(N-1) + 1 = 2N-1<2N\) ，所以两数相加要么没有进位，要么只进位1。
  • 根据上述加法进位的规则，结果字符串的长度最多为MAX_LEN+1，这里res的长度定义为MAX_LEN，最后输出时如果还有进位则在开头补1即可。
  • 这里定义标志位nonzeroFlag避免结果数字输出前导零。

第一次提交时testpoint3报错，检查后发现题目只保证输入两数非负，testpoint3又只有1分，考虑两数均为0的边界情况，这时候结果应该输出0（但是根据前导零的条件会什么都不输出），加上这一判断后AC。

My Code:

#include <stdio.h>
#include <string.h> // strlen header
#include <ctype.h> // isdigit header

#define MAX_LEN (100000+1) // MAX_LEN + '\0'

// first submit testpoint3 wrong answer
int main(void)
{
    char num1[MAX_LEN] = "", num2[MAX_LEN] = "";
    char res[MAX_LEN] = "";
    int temp1=0, temp2=0, tempSum=0;
    int num1Len=0, num2Len=0, resLen=0;
    int i=0; // iterator
    int carry=0;
    int nonzeroFlag=0;
    
    scanf("%s%s", num1, num2);
    
    num1Len = strlen(num1);
    num2Len = strlen(num2);
    resLen = num1Len;
    
    if(num1Len>num2Len) // add zero to num2
    {
        resLen = num1Len;
        for(i=num1Len-1; i>=num1Len-num2Len; --i) // move the num2
        {
            num2[i] = num2[i-(num1Len-num2Len)];
        }
        for(i=num1Len-num2Len-1; i>=0; --i) // add zero in front of num2
        {
            num2[i] = '0';
        }
    }
    else if(num1Len<num2Len) // add zero to num1
    {
        resLen = num2Len;
        for(i=num2Len-1; i>=num2Len-num1Len; --i) // move the num1
        {
            num1[i] = num1[i-(num2Len-num1Len)];
        }
        for(i=num2Len-num1Len-1; i>=0; --i) // add zero in front of num1
        {
            num1[i] = '0';
        }
    }
    
    //printf("%s\n%s\n", num1, num2); //output rectified num1, num2
    
    carry = 0;
    for(i=resLen-1; i>=0; --i) // add two num
    {
        // int isdigit(int c);
        if(isdigit(num1[i]))
        {
            temp1 = num1[i] - '0';
        }
        else // num1[i] is alpha
        {
            temp1 = num1[i]-'a'+10;
        }
        
        if(isdigit(num2[i]))
        {
            temp2 = num2[i] - '0';
        }
        else // num2[i] is alpha
        {
            temp2 = num2[i]-'a'+10;
        }
        
        tempSum = temp1+temp2+carry;
        carry = tempSum / 30;
        
        if(tempSum%30 < 10) // current bit is 0-9
        {
            res[i] = tempSum%30 + '0';
        }
        else // current bit is 'a'-'t'
        {
            res[i] = tempSum%30 - 10 + 'a';
        }
    }
    
    if(carry) // if have carry
    {
        printf("1%s\n", res); // carry only can be 1
    }
    else // doesn't have carry
    {
        i=0;
        nonzeroFlag=0;
        while(res[i]!='\0')
        {
            if(res[i]!='0' || nonzeroFlag)
            {
                nonzeroFlag = 1;
                printf("%c", res[i]);
            }
            ++i;
        }
        if(!nonzeroFlag) printf("0\n"); // this fixed testpoint3
        else printf("\n");
        //printf("%s\n", res);
    }
    
    return 0;
}