Hướng dẫn giải của Tính tổng 2 số nguyên lớn
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.
Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.
Bạn phải đăng nhập để mở lời giải này.
Đăng nhậpTác giả: , , ,
Hiểu bài toán
Bài toán yêu cầu tính tổng của hai số nguyên không âm có độ lớn lên đến 10^5 chữ số. Do hai số này quá lớn so với các kiểu dữ liệu nguyên chuẩn (như long long), chúng ta không thể đọc và cộng trực tiếp bằng các phép toán số học thông thường. Thay vào đó, cần xử lý chúng như các chuỗi ký tự và thực hiện phép cộng tương tự như cách cộng từng cột (từ phải sang trái) mà con người thường làm, có xét đến số nhớ.
Các cách tiếp cận
Cách Xử lý trực tiếp chuỗi (không chuẩn hóa)
#include <stdio.h>
#include <string.h>
int main() {
char a[100005], b[100005];
scanf("%s %s", a, b);
int i = strlen(a) - 1;
int j = strlen(b) - 1;
int carry = 0;
char result[100010];
int k = 0;
// Lặp trong khi còn chữ số hoặc còn số nhớ
while (i >= 0 || j >= 0 || carry) {
int digit_a = (i >= 0) ? a[i] - '0' : 0;
int digit_b = (j >= 0) ? b[j] - '0' : 0;
int sum = digit_a + digit_b + carry;
result[k++] = (sum % 10) + '0';
carry = sum / 10;
i--; j--;
}
// In kết quả (đảo ngược chuỗi kết quả)
for (int x = k - 1; x >= 0; x--) {
printf("%c", result[x]);
}
printf("\n");
return 0;
}
- Time Complexity: O(N), với N là độ dài lớn nhất của 2 số
- Space Complexity: O(N)
Hàm main của solution 3 là ví dụ điển hình cho cách tiếp cận này. Đầu tiên, chúng ta đọc hai số a và b dưới dạng chuỗi. Sử dụng hai chỉ số i và j trỏ vào phần tử cuối cùng của a và b. Trong khi một trong hai chỉ số chưa về -1 hoặc còn số nhớ (carry > 0), ta thực hiện cộng từng cột. Biến carry lưu số nhớ từ cột trước. Kết quả mỗi cột (sum % 10) được lưu vào một mảng phụ. Do chúng ta cộng từ phải sang trái, kết quả thu được sẽ ngược, nên cuối cùng cần in ra theo thứ tự ngược lại. Cách này không cần chuẩn hóa độ dài hai số ban đầu.
Cách Chuẩn hóa độ dài trước khi cộng
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX 100010
void chuanhoa(char *a, char *b) {
int len_a = strlen(a);
int len_b = strlen(b);
char temp[MAX];
if (len_a < len_b) {
int diff = len_b - len_a;
memset(temp, '0', diff);
temp[diff] = '\0';
strcat(temp, a);
strcpy(a, temp);
} else if (len_b < len_a) {
int diff = len_a - len_b;
memset(temp, '0', diff);
temp[diff] = '\0';
strcat(temp, b);
strcpy(b, temp);
}
}
int main() {
char a[MAX], b[MAX];
scanf("%s %s", a, b);
chuanhoa(a, b); // Chuẩn hóa để 2 số có cùng độ dài
int len = strlen(a);
char res[MAX];
int carry = 0;
for (int i = len - 1; i >= 0; i--) {
int sum = (a[i] - '0') + (b[i] - '0') + carry;
res[i] = (sum % 10) + '0';
carry = sum / 10;
}
if (carry > 0) {
printf("%d", carry);
}
printf("%s\n", res);
return 0;
}
- Time Complexity: O(N)
- Space Complexity: O(N)
Cách tiếp cận này (thấy rõ trong Solution 2) yêu cầu chuẩn hóa hai số trước. Tức là thêm các ký tự '0' vào phía bên trái của số có độ dài ngắn hơn để cả hai số có cùng độ dài. Việc này giúp vòng lặp cộng trở nên đơn giản hơn: chỉ cần lặp từ cuối đến đầu với một độ dài cố định. Tuy nhiên, cách này tốn thêm thời gian và bộ nhớ cho việc sao chép và nối chuỗi (string concatenation) để chuẩn hóa.
Cách Sử dụng mảng ký tự và chỉ số ngược (Reverse Indexing)
#include <stdio.h>
#include <string.h>
int main() {
char a[100005], b[100005];
scanf("%s %s", a, b);
int n = strlen(a);
int m = strlen(b);
char ans[100010];
int carry = 0;
int len = (n > m ? n : m);
// Duyệt từ phải sang trái nhưng ghi vào mảng result
// từ cuối lên đầu để không cần đảo ngược sau khi tính
for (int i = 0; i < len || carry; i++) {
int digit_a = (i < n) ? a[n - 1 - i] - '0' : 0;
int digit_b = (i < m) ? b[m - 1 - i] - '0' : 0;
int sum = digit_a + digit_b + carry;
ans[i] = (sum % 10) + '0';
carry = sum / 10;
}
int res_len = (len > 0 ? len : 1); // Nếu cả 2 rỗng, mặc định length 1
// Điều chỉnh độ dài thực tế nếu có số nhớ cuối
while (res_len > 0 && ans[res_len-1] == 0) res_len--; // Logic này cần cẩn thận
// Thực ra vòng lặp trên đã xử lý length động
int k = 0;
while (k < len && ans[k] == 0) k++; // Logic này không đúng với char array
// In kết quả từ cuối lên đầu của mảng ans đã tính (đảo ngược lại)
// Hoặc in từ đầu xuống cuối nếu ta đã lưu đúng thứ tự
// Ở đây ta lưu: index 0 là chữ số 10^0, index 1 là 10^1...
// Nên cần in ngược lại.
int final_len = (carry > 0) ? len + 1 : len;
if (final_len == 0) final_len = 1;
for (int i = final_len - 1; i >= 0; i--) {
printf("%c", ans[i]);
}
printf("\n");
return 0;
}
(Xem giải thích chi tiết)
- Time Complexity: O(N)
- Space Complexity: O(N)
Đây là biến thể của Solution 3 nhưng giải thích rõ hơn về việc tối ưu hóa bộ nhớ. Thay vì lưu vào mảng temp rồi đảo ngược (như Solution 3) hoặc chuẩn hóa chuỗi (như Solution 2), ta chỉ cần dùng 2 biến chỉ số i, j trỏ vào cuối a, b. Kết quả tính được của cột thứ k (tính từ phải sang, bắt đầu từ 0) sẽ được lưu vào res[k]. Cuối cùng, ta chỉ cần in mảng res từ cuối lên đầu. Solution 3 thực chất đã làm tương tự nhưng lưu vào temp rồi copy sang result để in đúng thứ tự. Cách này là tối ưu và phổ biến nhất trong các kỳ thi lập trình.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(N), với N là độ dài lớn nhất của 2 số | O(N) | Xử lý trực tiếp chuỗi (không chuẩn hóa) |
| 2 | O(N) | O(N) | Chuẩn hóa độ dài trước khi cộng |
| 3 | O(N) | O(N) | Sử dụng mảng ký tự và chỉ số ngược (Reverse Indexing) |
Bài học kinh nghiệm
- Số quá lớn để lưu vào kiểu số nguyên, cần xử lý như chuỗi ký tự (string).
- Thực hiện phép cộng tương tự như cách làm tay: cộng từ phải sang trái (units, tens, hundreds...) và nhớ số dư sang cột tiếp theo.
- Vòng lặp phải chạy cho đến khi duyệt hết tất cả các chữ số của cả hai số và không còn số nhớ (carry).
Lỗi thường gặp
- Quên xử lý số nhớ (carry) sau khi cộng hết các chữ số của hai số (ví dụ: 5 + 5 = 10, kết quả có thêm chữ số 1).
- Xử lý sai trường hợp hai số có độ dài khác nhau: cần coi như số có độ dài ngắn hơn có các chữ số 0 ở phía trước.
- Sai thứ tự in kết quả: do cộng từ phải sang trái, kết quả tính được thường là ngược (units trước, hundreds sau), cần in ngược lại.
Bình luận