Đề bài
Tính base mũ exponent bằng đệ quy: x⁰ = 1, và xⁿ = (x^(n/2))² nếu n chẵn, hoặc x × (x^((n−1)/2))² nếu n lẻ. Cách này sử dụng ít phép nhân hơn nhiều so với vòng lặp đơn giản.
Cài đặt hàm recursive_power(base, exponent).
Đầu vào
base: Cơ số. exponent: Số mũ (không âm).
Đầu ra
Trả về giá trị base lũy thừa exponent.
Ràng buộc
-10 ≤ base ≤ 10; 0 ≤ exponent ≤ 18
Ví dụ
Đầu vào:
base = 3
exponent = 5
Kết quả mong đợi:
expected = 243Đầu vào:
long long base = 3;
long long exponent = 5;
Kết quả mong đợi:
long long expected = 243;Đầu vào:
long base = 3;
long exponent = 5;
Kết quả mong đợi:
long expected = 243;Giải thích
3⁵ = 3 × (3²)² = 3 × 81 = 243.
Đầu vào:
base = 7
exponent = 0
Kết quả mong đợi:
expected = 1Đầu vào:
long long base = 7;
long long exponent = 0;
Kết quả mong đợi:
long long expected = 1;Đầu vào:
long base = 7;
long exponent = 0;
Kết quả mong đợi:
long expected = 1;Giải thích
Trường hợp cơ bản: bất kỳ số nào mũ 0 đều bằng 1.
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Dùng tính chẵn lẻ của số mũ để rút gọn bài toán nhanh hơn.
Gợi ý 2
Bình phương đệ quy tránh lặp lại công việc và giảm mạnh số phép nhân.
Gợi ý 3
Cẩn thận với số mũ 0 và các trường hợp cơ sở cho số mũ nhỏ.
Độ phức tạp mong đợi
thời gian O(log exponent), bộ nhớ phụ O(log exponent)
Tham khảo
Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.