Lũy thừa 1

Nguồn: CLUE OJ – Chương 19: Đệ quy cơ bản Độ khó: Dễ Đệ quy Chia để trị long long

Đề bài

Cho một số nguyên không âm $N$. Bạn hãy tính giá trị $2^N$.

Dữ liệu nhập: gồm một số nguyên không âm duy nhất là số $N$ $(0 \le N \le 50)$.

Dữ liệu xuất: một số nguyên dương chứa giá trị $2^N$.

Ví dụ – input

4

Ví dụ – output

16

Lời mở đầu

Tính lũy thừa là ví dụ kinh điển nhất khi học hàm đệ quy có giá trị trả về: mỗi lời gọi tính xong thì "trả" kết quả về cho lời gọi bên trên dùng tiếp. Bài có một cái bẫy nho nhỏ: $2^{50}$ vượt xa kiểu int. Mình sẽ giải bằng 2 cách: đệ quy từng bước $O(N)$ và đệ quy chia để trị $O(\log N)$ – nền móng của thuật toán lũy thừa nhanh sẽ học ở các bài sau.

Dành cho học viên · Ưu tiênNộp bài trên hệ thống CLUE OJ

Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.

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ộ test51 testÝ tưởngcây đệ quyCách 1bớt 1, O(N)Cách 2chia đôi, O(log N)

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

Số test	Giá trị N	Đáp án	Subtask
51	Test thứ $i$ có $N = i - 1$, tức là đủ mọi giá trị $N = 0, 1, \dots, 50$	từ $2^0 = 1$ đến $2^{50} = 1.125.899.906.842.624$	Không chia subtask

• Test 1 có $N = 0$: đáp án là $1$ – đây chính là điểm dừng của đệ quy, đừng quên!
• Các test 32–51 ($N \ge 31$) có đáp án vượt $2^{31} - 1 \approx 2{,}1 \cdot 10^9$ – giới hạn của int. Đáp án lớn nhất $2^{50} \approx 1{,}1 \cdot 10^{15}$ vẫn nằm gọn trong long long (tới khoảng $9{,}2 \cdot 10^{18}$).

Bẫy tràn số

Mình đã thử nộp đúng code Cách 1 nhưng khai báo hàm kiểu int thay vì long long: kết quả chỉ 31/51 test – sai từ test 32–51. Với $N = 31$ chương trình in ra -2147483648, từ $N = 32$ trở đi in ra 0. Nên kiểu trả về của hàm phải là long long.

Ý tưởngHai cách chia nhỏ 2^N

Hai công thức đệ quy

Cách 1 – bớt 1: $2^N = 2 \cdot 2^{N - 1}$, điểm dừng $2^0 = 1$. Cần $N$ lời gọi.
Cách 2 – chia đôi: đặt $h = 2^{\lfloor N/2 \rfloor}$ thì $2^N = h \cdot h$ nếu $N$ chẵn, $2^N = h \cdot h \cdot 2$ nếu $N$ lẻ. Mỗi lần gọi $N$ giảm một nửa nên chỉ cần khoảng $\log_2 N$ lời gọi.

Ví dụ $2^{13}$: $13 \to 6 \to 3 \to 1 \to 0$, chỉ 5 lời gọi; quay về: $2^0 = 1$, $2^1 = 1 \cdot 1 \cdot 2 = 2$, $2^3 = 2 \cdot 2 \cdot 2 = 8$, $2^6 = 8 \cdot 8 = 64$, $2^{13} = 64 \cdot 64 \cdot 2 = 8192$. Điều quan trọng là ở Cách 2 ta chỉ gọi luythua(n / 2) một lần, lưu vào h rồi nhân h * h. Nếu viết luythua(n / 2) * luythua(n / 2) thì cây đệ quy sẽ phân nhánh đôi và lại tốn $O(N)$ lời gọi.

Em chọn cách, nhập $N$ rồi bấm Tiếp: lời gọi đi xuống tới điểm dừng, rồi giá trị được trả ngược lên từng tầng (chữ xanh ↩):

Cách (1 hoặc 2): N =

Ví dụ nhanh:

Cách 1Đệ quy bớt 1: 2^N = 2 · 2^N−1

C++▶ Chạy tay từng dòng codeCách 1: luythua(n) = 2 × luythua(n − 1), dừng ở luythua(0) = 1.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. if(n == 0) return 1; – điểm dừng, cũng xử lý luôn test $N = 0$.
2. return 2 * luythua(n - 1); – máy phải chờ luythua(n - 1) tính xong mới nhân được với 2. Vì vậy các lời gọi xếp chồng trong ngăn xếp tới khi gặp điểm dừng, rồi mới lần lượt nhân ngược lên.
3. Kiểu trả về long long (xem bẫy tràn số ở phần Bộ test). Hằng 2 kiểu int nhân với long long sẽ được tính theo long long, không lo tràn.

Không gian$O(N)$ (ngăn xếp)

Thời gian$O(N)$

Kết quả chạy thật: bản C++ đúng 51/51 test, test đúng chạy lâu nhất 0.003s; bản Python đúng 51/51 test, test đúng chạy lâu nhất 0.022s (Python có số nguyên lớn tuỳ ý nên không lo tràn số).

Cách 2Chia để trị: 2^N = (2^N/2)²

C++▶ Chạy tay từng dòng codeCách 2: chia để trị, h = luythua(n / 2) rồi trả về h × h (nhân thêm 2 nếu n lẻ).

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. long long h = luythua(n / 2); – gọi đệ quy đúng một lần cho nửa số mũ (chia nguyên).
2. $N$ chẵn: $2^N = h^2$. $N$ lẻ: $N = 2 \cdot \lfloor N/2 \rfloor + 1$ nên phải nhân thêm 2.
3. Với $N = 50$ chỉ có 7 lời gọi ($50 \to 25 \to 12 \to 6 \to 3 \to 1 \to 0$), so với 51 lời gọi của Cách 1. Ở bài này $N$ nhỏ nên 2 cách chạy nhanh như nhau, nhưng khi số mũ lên tới $10^{18}$ (kèm phép chia lấy dư) thì chỉ Cách 2 dùng được.

Không gian$O(\log N)$ (ngăn xếp)

Thời gian$O(\log N)$

Kết quả chạy thật: bản C++ đúng 51/51 test, test đúng chạy lâu nhất 0.003s; bản Python đúng 51/51 test, test đúng chạy lâu nhất 0.033s.

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ú
Cách 1 nhưng dùng int	C++	31/51	0.003s	Sai ở test 32–51
1. Bớt 1	C++	51/51	0.003s	Full điểm
	Python	51/51	0.022s	Full điểm
2. Chia để trị	C++	51/51	0.003s	Full điểm
	Python	51/51	0.033s	Full điểm

Ghi chú của mình: cả 2 cách (C++ và Python) đều đạt full điểm, mỗi test dưới 0,05 giây. Riêng bản dùng int chỉ đúng 31/51 test vì tràn số. Hai điều cần nhớ: (1) luôn ước lượng kết quả lớn cỡ nào để chọn kiểu dữ liệu; (2) trong chia để trị, lưu kết quả lời gọi con vào biến rồi dùng lại, đừng gọi 2 lần.

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 😇