สมมติว่าเรามีตัวเลข x และอีกตัวเลข n เราต้องการหาจำนวนวิธีที่จะได้ x เป็นผลรวมของกำลัง n ของตัวเลขบางตัวที่ไม่ซ้ำกัน
ตัวอย่างเช่น หาก x = 100 และ n = 2 ผลลัพธ์จะเป็น 3 เพราะมีวิธีที่เป็นไปได้คือ 6^2 + 8^2, 10^2 และ 1^2 + 3^2 + 4^2 + 5^2 + 7^2
ขั้นตอนการแก้ปัญหา
- ans := 0
- กำหนดฟังก์ชัน solve() รับพารามิเตอร์ 4 ตัวคือ x, n, cn, cs โดยค่าเริ่มต้น cs = 0, cn = 1
- p := cn^n
- while p + cs < x:
- ans := ans + solve(x, n, cn + 1, p + cs)
- cn := cn + 1
- p := cn^n
- ถ้า p + cs เท่ากับ x:
- ans := ans + 1
- คืนค่า ans
ตัวอย่างโค้ด
from math import pow
def solve(x, n, cn=1, cs=0):
ans = 0
p = pow(cn, n)
while p + cs < x:
ans += solve(x, n, cn + 1, p + cs)
cn = cn + 1
p = pow(cn, n)
if p + cs == x:
ans = ans + 1
return ans
x = 100
n = 2
print(solve(x, n))
อินพุต
100, 2
เอาต์พุต
3
