BITEXEDU Chuyên trang chia sẻ tài liệu, kinh nghiệm ứng dụng giải toán trên máy tính cầm tay
Tìm hiểu thuật toán luỹ thừa nhanh
- 3 ngày trước
- 194 lượt xem
| Đặt vấn đề. Trong kỳ thi HSG MTCT THCS ta thường gặp bài toán:
Tìm dư của phép chia $a^n$ cho $b$.
Với những bài toán đơn giản, ví dụ $n$ là năm thi (năm $2027$ chẳng hạn) thì ta đã quen với việc phân tích $n=2025+m=3^4\times 5^2+m$ để xúc tiến tìm dư của phép chia. Bây giờ nếu $n$ rất lớn và không liên quan đến năm thi thì phải có một thuật toán tổng quát để giải bài toán. May mắn là ta có một thuật toán như thế và ta gọi nó là “thuật toán luỹ thừa nhanh”. |
Trước hết ta xem thuật toán này dưới dạng ngôn ngữ lập trình python (bạn không cần biết sử dụng python, chỉ cần biết nó là một ngôn ngữ lập trình đang giảng dạy cho học sinh 11 THPT).
def mod_pow(a, n, b):
res = 1
a = a % b # tối giản a
while n > 0:
if n % 2 == 1: # nếu n lẻ
res = (res * a) % b
a = (a * a) % b # bình phương a
n = n // 2 # chia n cho 2
return res
Giải thích thuật toán:
(dòng 2) Ban đầu ta gán dư bằng 1
(dòng 3) và tối giản $a$, nghĩa là lấy a chia b gán dư vào a. Ví dụ: $\boldsymbol{2028}^{2027} \ \text{mod}\ 2025 $ ta chỉ xét $\boldsymbol{3}^{2027} \ \text{mod} \ 2025$.
(dòng 4) vào vòng lặp
(dòng 5) Nếu $n$ là số lẻ (cụ thể dư của phép chia $n$ cho 2 bằng 1)
(dòng 6) thì ta cập nhật dư bằng cách lấy dư (ở vòng trên) nhân cho $a$ rồi chia có dư cho $b$ để lấy dư gán vào “dư”. Còn nếu $n$ chẵn thì ta bảo lưu “dư” (ở vòng trên).
(dòng 7) để chuyển sang vòng lặp tiếp theo ta bình phương $a$ chia có dư cho $b$ gán dư vào $a$
(dòng 8) và chia $n$ cho $2$ gán thương vào $n$,
(dòng 9) sau đó vào vòng lặp mới.
Vòng lặp sẽ dừng khi $n=1$ và “dư” sẽ là đáp số.
Để xem thuật toán này chạy. các bạn mở một trình biên dịch python online
https://www.online-python.com/
copy đoạn code sau
def mod_pow(a, n, b):
res = 1
a = a % b # tối giản a
while n > 0:
if n % 2 == 1: # nếu n lẻ
res = (res * a) % b
a = (a * a) % b # bình phương a
n = n // 2 # chia n cho 2
return res
print(mod_pow(2028, 2027, 2025))
dán vào màn hình soạn thảo bên trái (xoá mọi thứ của code mẫu), sau đó bấm vào Run (bên phải) sẽ có kết quả $\boldsymbol{162}$ ở dòng đầu bên phải.
Chú ý: câu lệnh cuối cùng phải viết sát lề trái.
Kỳ tới: Chạy thuật toán luỹ thừa nhanh trên bảng tính của máy tính Casio fx-880BTG.
About TS. Nguyễn Thái Sơn
