Trong bài viết này, chúng ta sẽ thảo luận về một chương trình để tìm cách một số nguyên (giả sử X) 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.
Ví dụ:cho X =100 và n =2
Sau đó, sẽ có 3 cách để biểu thị 100 dưới dạng tổng bình phương của các số tự nhiên.
100 = 102 100 = 62 + 82 100 = 12 + 32 + 42 + 52 + 72
Điều này có thể được thực hiện dễ dàng bằng cách sử dụng đệ quy. Chúng ta sẽ bắt đầu từ 1 và đi đến tận gốc thứ n của số đã cho. Trong mỗi lần chạy, chúng ta sẽ trừ lũy thừa thứ n của các số tự nhiên (bắt đầu từ 1) cho một số đã cho cho đến khi số đó nhỏ hơn. Điều này sẽ cung cấp cho chúng ta các cách số có thể được biểu diễn dưới dạng tổng lũy thừa bậc n của số tự nhiên.
Ví dụ
#include<iostream>
#include <math.h>
using namespace std;
int result = 0;
int ways(int number, int a, int init, int n){
if (a == 0) {
result++;
}
//setting the higher limit
int max = (int)floor(pow(number, 1.0 / n));
for (int i = init + 1; i <= max; i++) {
//subtracting n-th power values starting from 1
int b = a - (int)pow(i, n);
if (b >= 0)
ways(number, a - (int)pow(i, n), i, n);
}
return result;
}
int main() {
int a = 100, n = 2;
cout << ways(a, a, 0, n);
return 0;
} Đầu ra
3