ให้ตัวเลขสองตัวและกำลังเป็นอินพุต เป้าหมายคือการหาวิธีที่ num สามารถแสดงเป็นผลรวมของจำนวนธรรมชาติที่ไม่ซ้ำกันซึ่งยกขึ้นเป็นยกกำลังที่กำหนด ถ้า num คือ 10 และกำลังเป็น 2 เราก็สามารถแทน 10 เป็น 12+32 รวมเป็น 1 วิธี
ตัวอย่าง
อินพุต
num=30
ผลลัพธ์
Count of ways to express a number as sum of powers are: 2
คำอธิบาย
The ways in which we can express 30 as sum of powers: 12 + 22 + 52 and 12 + 22 + 32 + 42
อินพุต
num=35
ผลลัพธ์
Count of ways to express a number as sum of powers are: 1
คำอธิบาย
The ways in which we can express ‘num’ as sum of powers: 22 + 32
แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้ −
ในวิธีนี้เราจะตรวจสอบก่อนว่าตัวเลขนั้นเป็นกำลังของ num power . ใดๆ หรือไม่ . ถ้าใช่ ให้คืนค่าเป็น 1 ถ้าไม่เช่นนั้น ให้ตรวจสอบผลรวมซ้ำ กำลัง + (num+1) กำลัง .
-
นำเลขจำนวนเต็มสองตัวและกำลังมาเป็นอินพุต
-
ฟังก์ชัน sum_of_powers(int num, int power, int val) รับค่า num และคืนค่าจำนวนวิธีที่จะแสดง 'num' เป็นผลรวมของจำนวนธรรมชาติที่ไม่ซ้ำกันที่ยกกำลังที่กำหนด
-
เช็ค=(num − pow(val, power)). หากเช็คเป็น 0 ให้คืนค่า 1 เนื่องจากตัวเลขคือ val power .
-
หากเช็คน้อยกว่า 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;
} ผลลัพธ์
หากเราเรียกใช้โค้ดข้างต้น มันจะสร้างผลลัพธ์ต่อไปนี้ -
Count of ways to express a number as sum of powers are: 2
