python - 需要帮助设计解决方案来计算自动换行函数的 "penalty"

Question

我有一个程序可以递归地计算一个自动换行到指定的行长度。

def wrap(input, lineSpaces):
    if len(input) <= lineSpaces: # Base case
        return input
    temp = input.rfind(" ", 0, lineSpaces - 1) # Parsing
    if temp == -1:
        return input
    else:
        prev = input[:temp+1]
        next = wrap(input[temp+1:], lineSpaces)
        wrap.penalty = (lineSpaces-len(prev)+1)**3 +(lineSpaces-len(next)+1)**3 # Penalty calculation
        return prev+'\n'+next


# I/O
list = []
penalties = []
M = int(raw_input())
for i in xrange(0, M):
    lineSpaces = int(raw_input())
    input = raw_input()
    list.append(wrap(input, lineSpaces))
    penalties.append(wrap.penalty)


for i in xrange(0, len(list)):
    print "penalty: ", penalties[i]
    print list[i]+"\n"

使用以下输入:

3
20
This is the first paragraph that you need to print
30
This is another paragraph that you need to print and it ends in a very long word onetwothreefourfivesixseven
36
This paragraph all fits on one line

我期望输出:

penalty: 35
This is the first
paragraph that you
need to print

penalty: 216
This is another paragraph
that you need to print and 
it ends in a very long word
onetwothreefourfivesixseven

penalty: 0
This paragraph all fits on one line

但是，我实际上得到了输出:

penalty:  -1701
This is the first 
paragraph that you 
need to print

penalty:  -148752
This is another paragraph 
that you need to print and 
it ends in a very long word 
onetwothreefourfivesixseven

penalty:  -148752
This paragraph all fits on one line

如您所见，我的惩罚输出是错误的。我想将我的惩罚计算为每个段落中所有行的 (lineSpaces-len(line)+1)**3 的总和，每个段落的最后一行除外，该行的惩罚为0. 似乎每次调用 (lineSpaces-len(prev)+1)**3 的每个段落(除了最后一个，它应该是 0)都会返回正确的值。我的逻辑有什么问题？

Answer 1

您对罚款的计算在某些方面是错误的。首先，将 next 设置为递归调用的返回值。这仍然和原来的一样长，或者更长，因为你所做的只是给它添加换行符。但是你计算这个惩罚。在每次调用中，您都在计算该调用适合一行的惩罚与传递给下一个递归调用的所有其他内容的惩罚。

此外，因为您将此值存储在 wrap.penalty 中，所以每次调用后都会覆盖它。由于您从未对 wrap.penalty 的旧值执行任何操作，因此您忽略了除最后一个计算之外的所有计算。

像这样使用函数属性来存储数据是一种危险的游戏。只有一个 wrap，所以只有一个wrap.penalty，所以并不是每个递归调用都有自己的版本惩罚;他们都在踩同一个。与其将值存储在 wrap.penalty 中，不如将其与包装文本一起返回，如下所示:

def wrap(instr, lineSpaces):
    if len(instr) <= lineSpaces: # Base case
        return instr, 0
    temp = instr.rfind(" ", 0, lineSpaces - 1) # Parsing
    if temp == -1:
        return instr, 0
    else:
        prev = instr[:temp+1]
        next, penalty = wrap(instr[temp+1:], lineSpaces)
        penalty += (lineSpaces-len(prev)+1)**3 # Penalty calculation
        return prev+'\n'+next, penalty

然后:

>>> wrap("This is the first paragraph that you need to print", 20)
('This is the first \nparagraph that you \nneed to print', 35)

在每次调用时，我将从递归调用返回的惩罚添加到为我刚刚解析的行计算的惩罚中。正如 Pham Trung 在评论中所建议的那样，您也可以在包装后的单独步骤中计算罚金。

我还将您的变量名从 input 更改为 instr。你应该避免使用名称 input 因为有一个内置函数就是这个名字。 (出于同样的原因，list 也不是一个好的变量名。)