Đếm số cách biểu diễn số dưới dạng tổng các lũy thừa trong C++

Cho hai số num và power làm đầu vào. Mục tiêu là tìm các cách mà num có thể được biểu diễn dưới dạng tổng các số tự nhiên duy nhất được lũy thừa theo power cho trước. Nếu num là 10 và power là 2 thì ta có thể biểu diễn 10 như 1^2 + 3^2. Vậy tổng 1 cách.

Ví dụ

Đầu vào

num=30

Đầu ra

Số cách biểu diễn số dưới dạng tổng các lũy thừa là: 2

Giải thích

Các cách biểu diễn 30 dưới dạng tổng lũy thừa: 1^2 + 2^2 + 5^2 và 1^2 + 2^2 + 3^2 + 4^2

Đầu vào

num=35

Đầu ra

Số cách biểu diễn số dưới dạng tổng các lũy thừa là: 1

Giải thích

Cách biểu diễn 'num' dưới dạng tổng lũy thừa: 2^2 + 3^2

Phương pháp sử dụng

Trong phương pháp này, chúng ta trước hết kiểm tra xem số đó có chính là lũy thừa của num^power nào không. Nếu có thì trả về số cách là 1, nếu không thì đệ quy kiểm tra tổng num^power + (num+1)^power.

• Nhận hai số nguyên num và power làm đầu vào.
• Hàm sum_of_powers(int num, int power, int val) nhận num và trả về số cách biểu diễn num dưới dạng tổng các số tự nhiên duy nhất lũy thừa theo power cho trước.
• Lấy check = (num - pow(val, power)). Nếu check là 0 thì trả về 1 vì số đó chính là val^power.
• Nếu check nhỏ hơn 0 thì trả về 0.
• Ngược lại lấy temp = val + 1.
• Trả về tổng của (sum_of_powers(check, power, temp) + sum_of_powers(num, power, temp)).
• Cuối cùng, chúng ta sẽ nhận được số cách để trả về giá trị.

Ví dụ mã

#include <bits/stdc++.h> 
using namespace std; 

int sum_of_powers(int num, int power, int val) {
    int check = (num - pow(val, power));
    
    if (check == 0) {
        return 1;
    } else if (check < 0) {
        return 0;
    } else {
        int temp = val + 1;
        return sum_of_powers(check, power, temp) + sum_of_powers(num, power, temp);
    }
}

int main() {
    int num = 25, power = 2;
    cout << "Số cách biểu diễn số dưới dạng tổng các lũy thừa là: " << sum_of_powers(num, power, 1);
    return 0;
}

Đầu ra

Nếu chạy mã trên, sẽ tạo ra đầu ra sau:

Số cách biểu diễn số dưới dạng tổng các lũy thừa là: 2