时间戳

首页 > 解决方案 > 编程挑战：这个算法（与数论相关）是如何工作的？

python - 编程挑战：这个算法（与数论相关）是如何工作的？

问题描述

为了提高我的 Python 技能，我有时会在互联网上进行各种挑战（例如在hackerrank 上）。谷歌搜索别的东西，我发现了这个问题，以及互联网上的随附解决方案，它引起了我的注意：

最宏伟的楼梯

随着她的 LAMBCHOP 世界末日装置完成，拉姆达指挥官正在为她在银河舞台上的首次亮相做准备——但为了隆重登场，她需要一个宏伟的楼梯！作为她的私人助理，你的任务是弄清楚如何建造有史以来最好的楼梯。

Lambda 为您概述了可用的积木类型以及预算。您可以购买不同数量的不同类型的积木（例如，3 块小粉红积木，或 5 块蓝色花边积木）。指挥官 Lambda 想知道每种数量的砖块可以建造多少种不同类型的楼梯，所以她可以选择最多的一个。

每种类型的楼梯都应由 2 个或更多台阶组成。不允许两个台阶处于相同高度 - 每个台阶必须低于前一个台阶。所有台阶必须至少包含一块砖。台阶的高度被归类为构成该台阶的砖的总量。例如，当 N = 3 时，您只有一个选择如何建造楼梯，第一步的高度为 2，第二步的高度为 1：（# 表示砖）

#
##
21

当 N = 4 时，您仍然只有 1 个楼梯选择：

#
#
##
31

但是当 N = 5 时，有两种方法可以用给定的砖块建造楼梯。两个楼梯的高度可以是 (4, 1) 或 (3, 2)，如下图所示：

#
#
#
##
41

#
##
##
32

编写一个名为 answer(n) 的函数，它接受一个正整数 n 并返回可以从恰好 n 个砖块中建造的不同楼梯的数量。n 永远至少是 3（所以你可以有一个楼梯），但不超过 200，因为指挥官 Lambda 不是靠钱赚钱的！

https://en.wikipedia.org/wiki/Partition_(number_theory)

def answer(n):
    # make n+1 coefficients
    coefficients = [1]+[0]* n
    #go through all the combos
    for i in range(1, n+1):
        #start from the back and go down until you reach the middle
        for j in range(n, i-1, -1):
            print "add", coefficients[j-i], "to position", j
            coefficients[j] += coefficients[j-i]
            print coefficients
    return coefficients[n] - 1

现在我试图通过手动浏览一个示例来理解上述解决方案。例如，对于 

answer(10)

选项是：

1 2 3 4
1 2 7
1 3 6
1 9
1 4 5
2 3 5
2 8
3 7
4 6

所以总共有 9 个选项，加起来是 10 个。当我运行程序时，最后几个列表是：

        add 1 to position 10
        [1, 1, 1, 2, 2, 3, 4, 5, 6, 7, 9]
        add 1 to position 9
        [1, 1, 1, 2, 2, 3, 4, 5, 6, 8, 9]
        add 1 to position 10
        [1, 1, 1, 2, 2, 3, 4, 5, 6, 8, 10]

        9

所以结果是正确的，但我不明白最终列表或所有列表与解决方案有什么关系。我试图阅读有关数论的链接，但这更加令人困惑，我认为维基百科条目不是为第一次遇到这种问题类型的人编写的。

有人可以指导我完成解决方案，算法是如何工作的？

标签： pythonalgorithmnumber-theory

解决方案

关于您发布的答案功能：

在外部循环的每次迭代结束时，coefficients[x]您最多可以使用 height 制作楼梯的数量，i总共使用了x块。（包括只有一个楼梯或零楼梯的楼梯）。

coefficients被初始化为[1,0,0...]在循环之前，表示您只能制作一个高度最多为 0 的楼梯。这是没有楼梯的楼梯，因此您将消耗 0 个块来制作它。

在循环的每次迭代中，系数数组从表示 max height 转换i-1为表示 max height i，方法是结合向任何较短的楼梯添加一个高度台阶的可能性，从而i使您至少留下i块。

最后，它返回在使用完所有块后您可以到达终点的方式数n，减一，因为单个高度楼梯n无效。

该算法是“动态规划”的一个例子。

推荐阅读