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.