Computer >> Máy Tính >  >> Lập trình >> C ++

Tìm cách một Số nguyên có thể được biểu diễn dưới dạng tổng lũy ​​thừa bậc n của các số tự nhiên duy nhất trong C ++

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 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 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.