一般酒吧和星星

一尘不染

一般酒吧和星星

algorithm

我有以下用Python实现的“星星和星星”算法，该算法将总和的所有分解分解成3个档位，总和从0到5。我想归纳一下我的代码，以便与N个箱（其中N小于最大和，即5个）。模式是如果您有3个垃圾箱，则需要2个嵌套循环；如果您有N个垃圾箱，则需要N-1个嵌套循环。

有人能想到一种通用的编写方式，可能不使用循环吗？

# bars and stars algorithm
N=5
for n in range(0,N):
    x=[1]*n
    for i in range(0,(len(x)+1)):
        for j in range(i,(len(x)+1)):
            print sum(x[0:i]), sum(x[i:j]), sum(x[j:len(x)])

阅读 250

2020-07-28

共1个答案

一尘不染

一次迈出一步。

首先，删除sum()呼叫。我们不需要它们：

N=5
for n in range(0,N):
    x=[1]*n
    for i in range(0,(n+1)):  # len(x) == n
        for j in range(i,(n+1)):
            print i, j - i, n - j

注意，这x是一个未使用的变量：

N=5
for n in range(0,N):
    for i in range(0,(n+1)):
        for j in range(i,(n+1)):
            print i, j - i, n - j

是时候概括了。上面的算法对于N星形和三个条形是正确的，因此我们只需要概括这些条形即可。

递归执行此操作。对于基本情况，我们有零个条形或零个星号，这都是微不足道的。对于递归情况，请遍历最左边的条的所有可能位置，并在每种情况下递归：

from __future__ import print_function

def bars_and_stars(bars=3, stars=5, _prefix=''):
    if stars == 0:
        print(_prefix + ', '.join('0'*(bars+1)))
        return
    if bars == 0:
        print(_prefix + str(stars))
        return
    for i in range(stars+1):
        bars_and_stars(bars-1, stars-i, '{}{}, '.format(_prefix, i))

为了获得奖励积分，我们可以更改range()为xrange()，但这会在您移植到Python 3时给您带来麻烦。

2020-07-28