Tính tổng S

Nguồn: CLUE OJ Độ khó: Dễ Vòng lặp for Số thực

Đề bài

Cho số nguyên dương $N$, hãy tính tổng

$S = 1 + \dfrac{1}{2!} + \dfrac{1}{3!} + \ldots + \dfrac{1}{N!}$

trong đó $k! = 1 \cdot 2 \cdot 3 \cdots k$ (đọc là "$k$ giai thừa"). Lưu ý số hạng đầu tiên $1$ chính là $\dfrac{1}{1!}$, nên tổng có đúng $N$ số hạng.

Dữ liệu vào:

Một số nguyên dương $N$.

Kết quả:

In ra giá trị của $S$, làm tròn đến 10 chữ số sau dấu thập phân. Kết quả được chấp nhận nếu sai khác với đáp án không quá $10^{-9}$.

Giới hạn:

• $1 \le N \le 100$

Giới hạn thời gian: 1 giây, bộ nhớ: 256 MB. Dữ liệu nhập từ bàn phím và in ra màn hình.

Ví dụ 1 – input

10

Ví dụ 1 – output

1.7182818011

$S = 1 + \dfrac{1}{2} + \dfrac{1}{6} + \dfrac{1}{24} + \ldots + \dfrac{1}{3628800} \approx 1.7182818011$.

Nguồn: phỏng theo bài "TÍNH TỔNG" – vinhdinhcoder.net (chủ đề Lặp FOR).

Lời mở đầu

Tính tổng nghịch đảo các giai thừa $1 + \frac{1}{2!} + \ldots + \frac{1}{N!}$. Vòng lặp thì đơn giản, cái khó là giai thừa tăng cực nhanh: $13!$ đã vượt int, $21!$ vượt long long, còn $100!$ có tới 158 chữ số! Ghi chú: đề gốc viết "$1 + 1/2! + …$"; số 1 đầu tiên chính là $1/1!$ nên tổng có đúng $N$ số hạng. Bài được chấm với sai số tuyệt đối $10^{-9}$.

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Bộ test20 testÝ tưởngnhân dồn giai thừaLời giảicode C++ / PythonCái bẫycách làm saiTổng kếtkết quả

Bộ testBộ test chính thức có gì?

Bộ test có 20 test, mỗi test đúng được 1 phần điểm như nhau. Mọi test có $1 \le N \le 100$. Từ $N = 14$ trở đi kết quả làm tròn đều là $1.7182818285$ (vì $\frac{1}{15!} < 10^{-12}$), nhưng chương trình phải không bị tràn số.

Test	Nội dung kiểm tra
1–10	$N = 10$ (ví dụ), $N = 1, 2, 3, 4, 5, 7, 9, 12, 13$
11–14	$N = 14, 15, 20, 21$: quanh ngưỡng tràn int ($13!$) và long long ($21!$)
15–20	$N = 25, 34, 50, 66, 99, 100$: giai thừa cực lớn (kiểu số nguyên tràn về 0 → chia cho 0)

Ý tưởngNhân dồn giai thừa bằng double

Không tính lại $k!$ từ đầu mỗi lần: $k! = (k - 1)! \cdot k$. Giữ một biến gt, ở vòng thứ $k$ nhân thêm $k$ rồi cộng $\frac{1}{gt}$ vào tổng.

Chọn kiểu dữ liệu cho gt

• int: tràn từ $13!$, long long: tràn từ $21!$. Tràn rồi còn có thể thành 0 (với long long từ $66!$) → chia cho 0 ra inf.
• double lưu được tới khoảng $10^{308}$ nên $100! \approx 9{,}3 \cdot 10^{157}$ vẫn ổn. Sai số của double chỉ khoảng $10^{-16}$, quá đủ cho yêu cầu $10^{-9}$.
• Nhớ viết 1.0 / gt: nếu cả hai đều là số nguyên thì 1 / gt là phép chia nguyên, bằng 0!

Em nhập $N$ rồi bấm Tiếp để xem giai thừa và tổng thay đổi qua từng vòng:

N =

Ví dụ nhanh:

Lời giảiVòng for, giai thừa kiểu double

Hai biến double: gt (giai thừa) và s (tổng). In bằng fixed << setprecision(10).

C++▶ Chạy tay từng dòng codeNhân dồn giai thừa, cộng nghịch đảo vào tổng.

Dữ liệu vào (stdin) – sửa thoải mái10

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. fixed << setprecision(10) in đúng 10 chữ số sau dấu phẩy (tự làm tròn). Nếu chỉ cout << s thì C++ in 6 chữ số có nghĩa: 1.71828 – sai số quá lớn.
2. Cách khác không cần giai thừa: giữ biến term $= \frac{1}{k!}$, mỗi vòng term = term / k rồi cộng vào tổng.
3. Python: số nguyên không bị tràn nên gt nguyên vẫn đúng; 1 / gt trong Python 3 là phép chia số thực. In bằng "%.10f" % s.

Không gian$O(1)$

Thời gian$O(N)$

Kết quả chạy thật: bản C++ đúng 20/20 test, chạy lâu nhất 0.003s. Bản Python đúng 20/20 test, chạy lâu nhất 0.023s. Full điểm.

Cái bẫyNhững cách làm sai hay gặp

Các cách làm sai mình đã chấm thử trên bộ test:

Cách làm sai	Đúng	Ghi chú
Viết 1 / gt với gt nguyên (chia nguyên)	1/20	sai test 1, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20
Giai thừa kiểu int (tràn từ $13!$)	10/20	sai test 11, 12, 13, 14, 15, 16, 17, 18, 19, 20
Giai thừa kiểu long long (tràn từ $21!$, về 0 từ $66!$)	17/20	sai test 18, 19, 20
In bằng cout << s (thiếu chữ số)	2/20	sai test 1, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20
Cộng thêm số hạng $1 = \frac{1}{0!}$ (ra số $e$)	0/20	sai test 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20

Để ý cách dùng long long: từ $21!$ giá trị đã sai nhưng $\frac{1}{21!}$ quá nhỏ nên tổng vẫn "trông" đúng; chỉ khi gt tràn về đúng 0 (từ $66!$) thì phép chia cho 0 mới lộ ra inf. Lỗi tràn số có thể ẩn rất lâu!

Tổng kếtKết quả chạy thật trên bộ test

Cách	Ngôn ngữ	Đúng	Lâu nhất	Ghi chú
Lời giải chuẩn	C++	20/20	0.003s	Full điểm
	Python	20/20	0.023s	Full điểm
Chia nguyên	C++	1/20	–	Mất 19 test
Giai thừa int	C++	10/20	–	Mất 10 test
Giai thừa long long	C++	17/20	–	Mất 3 test
Thiếu chữ số	C++	2/20	–	Mất 18 test
Thêm 1/0!	C++	0/20	–	Mất 20 test

Ghi chú của mình: tổng $1 + \frac{1}{1!} + \frac{1}{2!} + \ldots$ chính là số $e \approx 2{,}718281828$ – nên tổng của bài này tiến tới $e - 1 \approx 1{,}7182818285$. Biết trước giới hạn giúp em tự kiểm tra kết quả.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇