algorithm - 枚举路径的算法

Question

假设你站在实线上的 0 点。在每一步，您可以移动到左侧 l 个位置，也可以移动到右侧 r 个位置。您打算到达数字 p。另外，有些号码是不允许踩的。你想数一数你能做到这一点。提到的所有数字都是整数（当然，l 和 r 是正数）。什么是计算这个的好方法？

笔记。你也可以在旅途中踩到 p 本身，所以在某些情况下答案是无限的。

Answer 1

这不是算法问题，而是数学问题。不过，这是解决方案。让我们假设您的数字l和r是正整数（它们都不是零）。

当且仅当方程r * x - l * y = p具有非负整数解时，才存在解(x, y)。这个等式表达了这样一个事实，即我们以任意顺序x向右行走几次，向左行走多次。y这个方程被称为Bézout 恒等式，我们确切地知道它的解是什么样的。

如果gcd(r,l)除p则存在整数解(x0, y0)，并且所有其他解的形式为x = x0 + k * r / gcd(l,r)，y = y0 + k * l / gcd(l,r)其中k贯穿整数。显然， ifk大于两者-x0 * gcd(l,r) / r，-y0 * gcd(l,r) / lthenx和y是非负的，所以我们有无限多的解决方案。

如果gcd(r,l)不除p则没有解，因为左边总是能被整除，gcd(l,r)但右边不能。

总之，您计算解决方案的算法如下所示：

if p % gcd(l,r):
    return Infinity
else:
    return 0

在这一点上，尝试列举所有路径似乎毫无意义，因为那将是一个相当无聊的练习。对于每个非负解(x,y)，我们简单地列举所有可能的安排x向右移动和y向左移动的方式。会有 (x+y)!/(x! * y!)这样的路径（在x+y步骤中选择x将向右移动）。

Answer 2

就像“L*x+R*y=P 有多少整数 (x,y) 解决方案”。

我相信有很多关于这个问题的文章。