Trong hướng dẫn này, ta sẽ viết chương trình tìm số cách một số nguyên có thể biểu diễn dưới dạng tổng lũy thừa n cho trước của các số tự nhiên khác nhau.
Ta có hai số nguyên number và power. Cần tìm bao nhiêu cách để biểu diễn number dưới dạng tổng lũy thừa power của các số tự nhiên khác nhau. Hãy xem ví dụ.
Đầu vào − number = 50, power = 2
Đầu ra − 3
Chỉ có một cách để viết 4 dưới dạng tổng lũy thừa 2.
Ta sẽ dùng đệ quy để giải quyết. Hãy xem các bước.
- Khởi tạo number và power.
- Viết hàm đệ quy với tên phù hợp. Nhận tham số number, power và i.
- Nếu number < 0 hoặc pow(i, power) > number, trả về 0.
- Nếu number == 0 hoặc pow(i, power) == number, trả về 1.
- Có hai lời gọi đệ quy để tính tổng số cách:
- Tăng i.
- Lời gọi đầu: kiểm tra các số nhỏ hơn number cho trước.
- Lời gọi hai: kiểm tra với number cho trước.
Ví dụ
Xem mã dưới đây:
#include <bits/stdc++.h> using namespace std; int findPossibleWaysCount(int number, int power, int i = 1) { if(number < 0 || number < pow(i, power)) { return 0; } if(number == 0 || number == pow(i, power)) { return 1; } return findPossibleWaysCount(number - pow(i, power), power, i + 1) + findPossibleWaysCount(number, power, i + 1); } int main() { // khởi tạo number và power int number = 50, power = 2; cout << findPossibleWaysCount(number, power) << endl; return 0; }
Đầu ra
Nếu chạy mã trên, bạn sẽ nhận được kết quả sau:
3
Kết luận
Nếu bạn có thắc mắc, hãy đề cập trong phần bình luận.