Hướng dẫn giải của Tính giai thừa 2
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 giá trị giai thừa $n!$ cho các số nguyên không âm $n$ trong phạm vi $0 \le n \le 1000$. Với $n$ lớn, kết quả giai thừa sẽ có số lượng chữ số rất lớn (năm 1000 có ~2568 chữ số), vượt quá khả năng lưu trữ của các kiểu dữ liệu nguyên chuẩn (như long long). Do đó, cần một phương pháp để xử lý các số lớn, cụ thể là lưu trữ và thao tác trực tiếp trên các chuỗi ký tự hoặc mảng các chữ số.
Các cách tiếp cận
Cách Nhân chuỗi (String Multiplication)
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
// Hàm đảo ngược chuỗi
void daonguoc(char *s) {
int l = 0, r = strlen(s) - 1;
while (l < r) {
char temp = s[l];
s[l] = s[r];
s[r] = temp;
l++; r--;
}
}
// Hàm nhân hai chuỗi số lớn
char *nhansolon(const char *a, const char *b) {
if (strcmp(a, "0") == 0 || strcmp(b, "0") == 0) return "0";
int len1 = strlen(a);
int len2 = strlen(b);
// Kết quả có tối đa len1 + len2 chữ số
int *res = (int *)calloc(len1 + len2 + 1, sizeof(int));
// Đảo chuỗi để tính toán từ chữ số cuối
char *s1 = strdup(a); daonguoc(s1);
char *s2 = strdup(b); daonguoc(s2);
for (int i = 0; i < len1; i++) {
for (int j = 0; j < len2; j++) {
res[i + j] += (s1[i] - '0') * (s2[j] - '0');
}
}
// Xử lý nhớ
for (int i = 0; i < len1 + len2; i++) {
if (res[i] >= 10) {
res[i + 1] += res[i] / 10;
res[i] %= 10;
}
}
// Xác định độ dài thực tế của kết quả
int len = len1 + len2;
while (len > 1 && res[len - 1] == 0) len--;
char *final = (char *)malloc(len + 1);
for (int i = 0; i < len; i++) final[i] = res[len - 1 - i] + '0';
final[len] = '\0';
free(s1); free(s2); free(res);
return final;
}
int main() {
int t;
scanf("%d", &t);
while (t--) {
int n;
scanf("%d", &n);
char *ans = (char *)malloc(2);
strcpy(ans, "1");
for (int i = 1; i <= n; i++) {
char num[20];
sprintf(num, "%d", i);
ans = nhansolon(ans, num);
}
printf("%s\n", ans);
}
return 0;
}
- Time Complexity: O(T * n * L^2) hoặc O(T * n! * (log(n!))^2), với L là độ dài chuỗi số lớn hiện tại.
- Space Complexity: O(L) để lưu trữ chuỗi kết quả và mảng phụ.
Phương pháp này mô phỏng phép nhân thủ công. Chuỗi số được lưu dưới dạng mảng ký tự (hoặc mảng số). Để nhân, ta thường đảo ngược chuỗi để xử lý từ chữ số thấp nhất (units) lên. Sử dụng một mảng phụ để lưu tích của từng cặp chữ số, sau đó xử lý các số nhớ. Cuối cùng, chuyển mảng số trở lại chuỗi. Với mỗi bước tính $i!$, ta nhân kết quả trước đó ($ (i-1)! $) với $i$. Do độ dài chuỗi tăng dần, chi phí nhân tăng lên, tổng thể phức tạp phụ thuộc vào tổng độ dài các chuỗi.
Cách Nhân mảng số (Array Multiplication)
#include <stdio.h>
int main() {
int t;
scanf("%d", &t);
while(t--) {
int n;
scanf("%d", &n);
if(n == 0 || n == 1) {
printf("1\n");
continue;
}
// Mảng lưu các chữ số của kết quả, ngược với thứ tự in
int kq[5000] = {0};
kq[0] = 1;
int len = 1;
for(int i = 2; i <= n; i++) {
int du = 0;
// Nhân từng chữ số của kết quả hiện tại với i
for(int j = 0; j < len; j++) {
int tmp = kq[j] * i + du;
kq[j] = tmp % 10;
du = tmp / 10;
}
// Xử lý số nhớ còn lại, tăng độ dài mảng
while(du) {
kq[len] = du % 10;
du /= 10;
len++;
}
}
// In kết quả theo thứ tự từ chữ số hàng đầu
for(int i = len - 1; i >= 0 ;i--) {
printf("%d", kq[i]);
}
printf("\n");
}
return 0;
}
- Time Complexity: O(T * n * L), với L là số lượng chữ số của n!. Ví dụ với n=1000, L~2500.
- Space Complexity: O(L) để mảng lưu các chữ số.
Thay vì lưu dưới dạng chuỗi, ta dùng mảng số nguyên để lưu các chữ số của số giai thừa. kq[j] lưu chữ số tại vị trí $10^j$. Ban đầu, kết quả là 1 (mảng có 1 phần tử là 1). Với mỗi số $i$ từ 2 đến $n$, ta nhân mảng kết quả hiện tại với $i$. Quá trình nhân thực hiện trên từng phần tử của mảng, sử dụng biến du (nhớ) để truyền sang chữ số tiếp theo. Nếu số nhớ còn lại sau khi nhân hết các chữ số, ta mở rộng mảng. Phương pháp này hiệu quả và dễ quản lý bộ nhớ hơn so với việc cấp phát động chuỗi.
Cách Quy hoạch động (Dynamic Programming)
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
// Cấu trúc lưu trữ kết quả giai thừa
struct Factorial {
vector<int> digits; // Lưu các chữ số, digits[0] là chữ số thấp nhất
Factorial() {
digits.push_back(1);
}
};
// Mảng global để lưu kết quả DP
Factorial dp[1001];
// Hàm khởi tạo DP
void precompute() {
for (int i = 1; i <= 1000; i++) {
dp[i] = dp[i-1]; // Gán bằng kết quả trước đó
int carry = 0;
for (int j = 0; j < dp[i].digits.size(); j++) {
int prod = dp[i].digits[j] * i + carry;
dp[i].digits[j] = prod % 10;
carry = prod / 10;
}
while (carry) {
dp[i].digits.push_back(carry % 10);
carry /= 10;
}
}
}
int main() {
precompute();
int t;
if (cin >> t) {
while (t--) {
int n;
cin >> n;
// In từ chữ số cao nhất về thấp nhất
for (int i = dp[n].digits.size() - 1; i >= 0; i--) {
cout << dp[n].digits[i];
}
cout << endl;
}
}
return 0;
}
- Time Complexity: O(N^2 * L) (trong đó N=1000, L là độ dài trung bình). Tuy nhiên, với bài toán này, ta chỉ cần tính $n!$ cho các test case. Nếu dùng DP precompute, chi phí tiền xử lý là O(1000 * L).
- Space Complexity: O(N * L) ~ O(10^6) integers, hoàn toàn chấp nhận được.
Đây là biến thể của phương pháp mảng số nhưng tối ưu cho nhiều test case. Ta tính trước và lưu trữ kết quả giai thừa từ 0! đến 1000! vào một mảng (hoặc vector). dp[i] được tính dựa trên dp[i-1] bằng cách nhân dp[i-1] với i (tương tự phương pháp mảng số). Với mỗi test case, ta chỉ cần truy vấn kết quả đã tính sẵn và in ra. Điều này giúp giảm thời gian chạy đáng kể nếu có nhiều test case.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(T * n * L^2) hoặc O(T * n! * (log(n!))^2), với L là độ dài chuỗi số lớn hiện tại. | O(L) để lưu trữ chuỗi kết quả và mảng phụ. | Nhân chuỗi (String Multiplication) |
| 2 | O(T * n * L), với L là số lượng chữ số của n!. Ví dụ với n=1000, L~2500. | O(L) để mảng lưu các chữ số. | Nhân mảng số (Array Multiplication) |
| 3 | O(N^2 * L) (trong đó N=1000, L là độ dài trung bình). Tuy nhiên, với bài toán này, ta chỉ cần tính $n!$ cho các test case. Nếu dùng DP precompute, chi phí tiền xử lý là O(1000 * L). | O(N * L) ~ O(10^6) integers, hoàn toàn chấp nhận được. | Quy hoạch động (Dynamic Programming) |
Bài học kinh nghiệm
- Vì $n$ lên tới 1000, kết quả giai thừa không thể lưu trong kiểu số nguyên chuẩn. Phải sử dụng cấu trúc dữ liệu tùy chỉnh (chuỗi, mảng, vector).
- Phép nhân số lớn có thể được mô phỏng bằng cách nhân từng chữ số và cộng các số nhớ.
- Với nhiều test case, tính toán trước (Precompute) toàn bộ kết quả từ 0 đến 1000 là hiệu quả nhất.
Lỗi thường gặp
- Quên xử lý số nhớ (carry) trong quá trình nhân hoặc cộng.
- Lỗi in sai thứ tự (mảng lưu trữ thường ngược với thứ tự in, chữ số hàng đơn vị ở vị trí đầu mảng).
- Chọn sai kích thước mảng lưu trữ dẫn đến tràn bộ nhớ hoặc lỗi truy cập.
Bình luận