ในบทความนี้ เราจะพูดถึงโปรแกรมเพื่อค้นหาวิธีที่จำนวนเต็ม (พูด X) สามารถแสดงเป็นผลรวมของยกกำลังที่ n ของจำนวนธรรมชาติที่ไม่ซ้ำกัน
ตัวอย่างเช่น ให้ X =100 และ n =2
แล้วจะมี 3 วิธีในการแสดง 100 เป็นผลบวกกำลังสองของจำนวนธรรมชาติ
100 = 102 100 = 62 + 82 100 = 12 + 32 + 42 + 52 + 72
สามารถทำได้ง่ายโดยใช้การเรียกซ้ำ เราจะเริ่มจาก 1 และไปจนถึงรากที่ n ของจำนวนที่กำหนด ในทุกการวิ่ง เราจะลบกำลังที่ n ของจำนวนธรรมชาติ (เริ่มจาก 1) จากจำนวนที่กำหนดจนจำนวนนั้นน้อยกว่า นี่จะทำให้เราสามารถแสดงตัวเลขเป็นผลรวมของยกกำลังที่ n ของจำนวนธรรมชาติได้
ตัวอย่าง
#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;
} ผลลัพธ์
3
