Skip to main content
 首页 » 编程设计

python之递归如何跟踪答案

2024年12月31日13think

我正在 Hackerrank 上尝试这个挑战:https://www.hackerrank.com/challenges/the-power-sum/problem

有两种方法可以解决这个问题:

  • 递归
  • 动态规划

我的问题:我不明白递归解决方案的一部分。我不明白当它一直设置为零时它如何能够跟踪“答案”。

示例输入:

29

2

正确答案:2

示例输出:

cur 0 
cur 0 
cur 0 
cur 0 
the 0 
cur 0 
the 0 
the 0 
cur 0 
cur 0 
the 0 
the 0 
cur 0 
the 0 
cur 0 
the 0 
the 0 
cur 0 
cur 0 
a match: 
4 9 16 the 1 
the 1 
cur 0 
the 1 
a match: 
4 25 the 2 
the 2 
cur 0 
cur 0 
the 0 
the 2 
cur 0 
the 2 
cur 0 
the 2 

代码:

import math 
import os 
import random 
import re 
import sys 
 
def powerSum(x, n, value): 
    s = sum (v**n for v in value) 
    if s == x: 
        print "a match:" 
        for v in value: 
            print v**n, 
        return 1 
    else: 
        v = value[-1] + 1 if value else 1 
        answer = 0 
        print "cur", answer 
        while s + v**n <= x: 
            answer += powerSum(x, n, value+[v]) 
            v += 1 
            print "the", answer 
    return answer 
 
 
if __name__ == '__main__': 
    fptr = open(os.environ['OUTPUT_PATH'], 'w') 
 
    x = int(raw_input()) 
 
    n = int(raw_input()) 
 
    value = [] 
 
    result = powerSum(x, n, value) 
 
    fptr.write(str(result) + '\n') 
 
    fptr.close() 

请您参考如下方法:

您在问题中提供的代码以稍微复杂的方式实现了递归。就这些。考虑一下相同代码的不同版本:

def powerSum(x, n, value): 
 
    answer = 0 
 
    s = sum(v**n for v in value) 
    # base case 
    if s == x: 
        answer = 1 
    # recursive case 
    else: 
        v = value[-1] + 1 if value else 1 
        while s + v**n <= x: 
            answer += powerSum(x, n, value+[v]) 
            v += 1 
 
    return answer