Trong hướng dẫn này, chúng ta sẽ viết một chương trình để tìm số cách một số nguyên có thể được biểu diễn dưới dạng tổng lũy thừa thứ n đã cho của các số duy nhất.
Chúng tôi có hai số nguyên number và quyền lực . Và chúng ta cần tìm xem chúng ta có thể biểu diễn số đã cho bằng bao nhiêu cách dưới dạng tổng lũy thừa thứ n của các số tự nhiên duy nhất. Hãy xem một ví dụ.
Đầu vào - number =50, power =2
Đầu ra - 3
Chỉ có một cách khả thi là chúng ta có thể viết 4 thành tổng của 2 lũy thừa.
Chúng tôi sẽ sử dụng đệ quy để giải quyết vấn đề. Hãy xem các bước để giải quyết vấn đề.
-
Khởi tạo số và nguồn.
-
Viết một hàm đệ quy với tên phù hợp. Nó chấp nhận số , quyền lực và i dưới dạng đối số.
-
Nếu số nhỏ hơn 0 hoặc pow (i, power) lớn hơn số , sau đó trả về 0.
-
Nếu số bằng 0 hoặc pow (i, power) bằng số thì trả về 1.
-
Chúng ta có hai lệnh gọi đệ quy cho các hàm để tính tổng số cách
-
Tăng i .
-
Trong cuộc gọi đệ quy đầu tiên, hãy kiểm tra các số nhỏ hơn số đã cho.
-
Trong cuộc gọi đệ quy thứ hai, hãy kiểm tra số đã cho.
-
Ví dụ
Hãy xem mã.
#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() {
// initializing the number and power
int number = 50, power = 2;
cout << findPossibleWaysCount(number, power) << endl;
return 0;
} Đầu ra
Nếu bạn chạy đoạn mã trên, thì bạn sẽ nhận được kết quả sau.
3
Kết luận
Nếu bạn có bất kỳ câu hỏi nào trong hướng dẫn, hãy đề cập đến chúng trong phần bình luận.