Kết quả cần tìm được giữ dưới dạng p×c^n
Ban đầu p=1,c=a, số mũ n là đầu vào. Giữ giá trị cần tính dưới dạng $p\times c^n$.
Nếu n chẵn, đổi n thành n//2 và c thành c²; phần $c^n$ không đổi giá trị. Nếu n lẻ, lấy bớt một thừa số c sang p: p thành p×c, n giảm 1. Khi n=0, phần còn lại là p×1, nên trả p.
Cập nhật theo số mũ chẵn hoặc lẻ
```python
def power_loop(a, n):
p = 1
c = a
while n != 0:
if n % 2 == 0:
n = n // 2
c = c * c
else:
n = n - 1
p = p * c
return p
```
Với a=2,n=13, các trạng thái sau mỗi bước là:
| n còn lại | p | c |
|---|---|---|
| 13 | 1 | 2 |
| 12 | 2 | 2 |
| 6 | 2 | 4 |
| 3 | 2 | 16 |
| 2 | 32 | 16 |
| 1 | 32 | 256 |
| 0 | 8192 | 256 |
Giá trị cuối cần trả là p=8192; c chỉ là cơ số đang dùng trong quá trình thu nhỏ. Với n ban đầu bằng 0, vòng lặp không chạy và p vẫn bằng 1.
Đối chiếu ba bản tính lũy thừa
Tải mã và chạy bằng Python3 tại thư mục chứa tệp:
```text
python3 g11-cs-thiet-ke-chia-de-tri.py luy-thua 2 13
```
Ba dòng kết quả của bản nhân lần lượt, bản chia để trị đệ quy và bản vòng lặp đều cần bằng 8192. Thử cơ số −2/số mũ 5 để nhận −32; số mũ 0 cần cho 1.
Mẫu dòng lệnh nhận cơ số nguyên khác 0, trị tuyệt đối không quá 1000; số mũ nguyên từ 0 đến 512 để giữ kết quả thử nhỏ. Thuật toán trong bài dùng điều kiện a≠0,n≥0; giới hạn của tệp không phải giới hạn toán học. Nhập cơ số 0, số mũ âm hoặc chữ phải báo lỗi.
Bài luyện
Bắt đầu p=1,c=2,n=13. Sau một bước của power_loop, trạng thái nào đúng?
13 lẻ: giảm n một đơn vị và đưa một thừa số c sang p.
Đó là cập nhật nhánh chẵn, nhưng 13 lẻ.
Không thực hiện cả hai nhánh trong cùng một bước.
Không có quy tắc gán p=n hoặc đặt n=0 ngay.
Lời giải
n=13 lẻ nên n thành 12, p thành 1×2=2; c giữ nguyên 2. Nhánh chẵn chưa chạy ở bước này.
Bài luyện
Đang có p=2,c=2,n=12. Sau bước nhánh chẵn, trạng thái nào đúng?
p không được tự đổi lại thành 1.
Giảm đôi n, bình phương c và giữ p.
Đó là kiểu cập nhật nhánh lẻ, không phù hợp n=12.
Phải bình phương c để giữ giá trị của phần còn lại.
Lời giải
12 chẵn nên n=12//2=6 và c=2×2=4, còn p=2. Giá trị 2×2^12 bằng 2×4^6 nên trạng thái giữ đúng phép tính.
Bài luyện
Khi vòng lặp kết thúc với n=0, vì sao trả p thay vì c?
Nhánh lẻ có cập nhật p.
Đầu ra là giá trị lũy thừa, không phải số mũ.
Phần tích còn lại không thêm thừa số nào.
c là cơ số biến đổi, không phải luôn là đáp số.
Lời giải
Các bước giữ giá trị cần tìm dưới dạng p×c^n. Khi n=0 và c khác 0, c^0=1 nên giá trị còn lại chính là p.
Đang học