นับวิธีแสดงจำนวนเป็นผลรวมของกำลังด้วย C++

ได้รับตัวเลขสองจำนวน num และ power เป็นอินพุต เป้าหมายคือหาจำนวนวิธีที่ num สามารถแสดงเป็นผลรวมของจำนวนธรรมชาติที่ไม่ซ้ำกัน ยกกำลังตาม power ที่กำหนด ถ้า num=10 และ power=2 แล้ว 10 = 1² + 3² รวม 1 วิธี

ตัวอย่าง

Input

num=30

Output

Count of ways to express a number as sum of powers are: 2

Explanation

The ways in which we can express 30 as sum of powers: 12 + 22 + 52 and 12 + 22 + 32 + 42

Input

num=35

Output

Count of ways to express a number as sum of powers are: 1

Explanation

The ways in which we can express 'num' as sum of powers: 22 + 32

วิธีการที่ใช้ในโปรแกรม

วิธีนี้ตรวจสอบก่อนว่าตัวเลขนั้นเองเป็นกำลังของ num^power หรือไม่ ถ้าใช่ คืนค่า 1 ถ้าไม่ เรียกซ้ำตรวจสอบผลรวม numpower + (num+1)power

• รับจำนวนเต็ม num และ power เป็นอินพุต
• ฟังก์ชัน sum_of_powers(int num, int power, int val) คืนค่าจำนวนวิธีแสดง num เป็นผลรวมกำลัง
• คำนวณ check = (num - pow(val, power)) ถ้า check เป็น 0 คืนค่า 1 (ตัวเลขเองเป็น val^power)
• ถ้า check น้อยกว่า 0 คืนค่า 0
• มิฉะนั้น temp = val + 1
• คืนค่าผลรวมของ (sum_of_powers(check, power, temp) + sum_of_powers(num, power, temp))
• ในที่สุดจะได้จำนวนวิธี

ตัวอย่างโค้ด

#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 << "Count of ways to express a number as sum of powers are: " << sum_of_powers(num, power, 1);
    return 0;
}

Output

หากรันโค้ดข้างต้นจะได้ผลลัพธ์ดังนี้:

Count of ways to express a number as sum of powers are: 2