โปรแกรมตรวจสอบว่าเลขเป็นผลรวมของกำลังสามหรือไม่ใน Python

สมมติว่าเรามีตัวเลข n เราต้องตรวจสอบว่าสามารถแทน n เป็นผลรวมของกำลังสามที่แตกต่างกันได้หรือไม่ จำนวนเต็ม y ถือว่าเป็นกำลังสาม หากมีจำนวนเต็ม x ใดๆ ที่ y = 3^x

เช่น ถ้าอินพุตคือ n = 117 ผลลัพธ์จะเป็น True เพราะ 117 = 3^4 + 3^3 + 3^2 = 81 + 27 + 9

วิธีแก้ปัญหา

• สำหรับ i ในช่วง 16 ถึง 0 ลดทีละ 1:
  • ถ้า n >= 3^i: n := n - 3^i
• ถ้า n > 0: return False
• return True

ตัวอย่าง

def solve(n):
    for i in range(16, -1, -1):
        if n >= pow(3,i):
            n -= pow(3,i)
    if n > 0:
        return False
    return True

n = 117
print(solve(n))

อินพุต

117

เอาต์พุต

True