โปรแกรม C++ หาจำนวนวิธีแสดงจำนวนเต็มเป็นผลรวมกำลัง n ของจำนวนธรรมชาติต่างกัน

หาจำนวนวิธีที่จำนวนเต็ม X แสดงเป็นผลรวมของกำลัง n ของจำนวนธรรมชาติต่างกัน (unique natural numbers)

ตัวอย่าง: X=100, n=2 → 3 วิธี:

100 = 10²
100 = 6² + 8²
100 = 1² + 3² + 4² + 5² + 7²

ใช้ Recursion: เริ่มจาก 1 ถึง n-th root ของ X ลบกำลัง 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++; }
    int max = (int)floor(pow(number, 1.0 / n));
    for (int i = init + 1; i <= max; i++) {
        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