【PTA数据结构 | C语言版】大整数相加运算
本专栏持续输出数据结构题目集,欢迎订阅。
文章目录
- 题目
- 代码
题目
请编写程序,求两个不超过 1000 位的大整数的和。题目保证和是正整数。
输入格式:
输入在两行中分别给出两个整数,保证不超过 1000 位。
输出格式:
在一行中输出两个整数的和。但如果和超过了 1000 位,则仅输出 错误:位数超限。
输入样例 1:
499876543201234567893
11223756899976543227
输出样例 1:
511100300101211111120
输入样例 2:
-11223756899976543227
499876543201234567893
输出样例 2:
488652786301258024666
代码
#include <stdio.h>
#include <string.h>#define MAX_LEN 1001int main() {char a[MAX_LEN], b[MAX_LEN], res[MAX_LEN+1] = {0};int sign_a = 1, sign_b = 1;int idx_a = 0, idx_b = 0; // 用于跳过符号位的索引int len_a, len_b, len_res = 0;// 读取输入并处理符号scanf("%s %s", a, b);if (a[0] == '-') { sign_a = -1; idx_a = 1; }if (b[0] == '-') { sign_b = -1; idx_b = 1; }len_a = strlen(a) - idx_a; // 实际数值长度len_b = strlen(b) - idx_b;// 处理加法(同号)或减法(异号)if (sign_a == sign_b) {// 加法:逐位相加并处理进位int carry = 0;for (int i = len_a-1, j = len_b-1; i >= 0 || j >= 0 || carry; i--, j--) {int da = (i >= 0) ? (a[i+idx_a] - '0') : 0;int db = (j >= 0) ? (b[j+idx_b] - '0') : 0;int sum = da + db + carry;res[len_res++] = sum % 10 + '0';carry = sum / 10;}// 添加符号(负数)if (sign_a == -1) res[len_res++] = '-';} else {// 减法:比较绝对值大小,用大减小int cmp = 0;if (len_a > len_b) cmp = 1;else if (len_a < len_b) cmp = -1;else cmp = strncmp(a+idx_a, b+idx_b, len_a);const char *larger = (cmp >= 0) ? (a+idx_a) : (b+idx_b);const char *smaller = (cmp >= 0) ? (b+idx_b) : (a+idx_a);int len_l = (cmp >= 0) ? len_a : len_b;int len_s = (cmp >= 0) ? len_b : len_a;int sign_res = (cmp >= 0) ? sign_a : sign_b;// 逐位相减并处理借位int borrow = 0;for (int i = len_l-1, j = len_s-1; i >= 0; i--, j--) {int dl = larger[i] - '0';int ds = (j >= 0) ? smaller[j] - '0' : 0;int diff = dl - ds - borrow;if (diff < 0) { diff += 10; borrow = 1; }else borrow = 0;res[len_res++] = diff + '0';}// 去除前导零while (len_res > 1 && res[len_res-1] == '0') len_res--;// 添加符号(负数)if (sign_res == -1 && res[0] != '0') res[len_res++] = '-';}// 反转结果字符串for (int i = 0; i < len_res/2; i++) {char t = res[i];res[i] = res[len_res-1-i];res[len_res-1-i] = t;}res[len_res] = '\0';// 判断是否超限(不包括符号位)int digits = (res[0] == '-') ? len_res - 1 : len_res;if (digits > 1000) printf("错误:位数超限。\n");else printf("%s\n", res);return 0;
}