给定一对数字(a，B)。您可以执行操作(A+B，B)或(A，A+B)。(A，B)被初始化为(1，1)。对于任何N>0，找到您需要在(A，B)上执行的最小操作数，直到A=N或B=N
在玻璃门的一次采访总结中遇到了这个问题。思考了几个方法，在网上搜索，但找不到任何解决这个问题的文章/答案。我有一个如下所示的强力方法，但它必须遍历O(2^N)路径，不知道是否有一个我没有看到的优雅的解决方案。
def pairsum(N):
A = 1
B = 1
return helper(N, A, B, 0)
def helper(N, A, B, ops):
# Solution found
if A == N or B == N:
return ops
# We've gone over, invalid path taken
if A > N or B > N:
return float("inf")
return min(helper(N, A + B, B, ops + 1), helper(N, A, A + B, ops + 1))
给定一个目标数N，可以在大约O(N log(N))的基本算术运算中计算最小运算数(尽管我怀疑有更快的方法)。方法如下：
对于这个问题，我认为向后处理比向前处理更容易。假设我们试图达到一个正整数的目标对(a, b)。我们从(a, b)开始，向(1, 1)逆向工作，边走边计算步骤。这很容易的原因是，从一对(a, b)到(1, 1)只有一条路径：如果是a > b，那么对(a, b)就不可能是第二次运算的结果，所以我们可能到达这对的唯一方法是将第一次运算应用于(a - b, b)。类似地，如果a < b，我们只能通过应用于(a, b - a)的第二个运算到达对。案例a = b呢？好吧，如果是a = b = 1，那就没什么可做的了。如果a = b和a > 1，那么我们根本无法到达这对：注意，这两个运算都是从整数的互质对到整数的互素对，所以如果我们从(1, 1)开始，我们永远无法到达一对最大公约数大于1的整数。
这导致以下代码对任何一对正整数a和b从(1, 1)到(a, b)的步数进行计数：
def steps_to_reach(a, b):
"""
Given a pair of positive integers, return the number of steps required
to reach that pair from (1, 1), or None if no path exists.
"""
steps = 0
while True:
if a > b:
a -= b
elif b > a:
b -= a
elif a == 1: # must also have b == 1 here
break
else:
return None # no path, gcd(a, b) > 1
steps += 1
return steps
看看上面的代码，它与计算最大公约数的欧几里得算法非常相似，只是我们做事情的效率非常低，使用重复减法，而不是用欧几里得除法直接求余数。因此，可以用以下等效的、更简单、更快的版本来取代上述版本：
def steps_to_reach_fast(a, b):
"""
Given a pair of positive integers, return the number of steps required
to reach that pair from (1, 1), or None if no path exists.
Faster version of steps_to_reach.
"""
steps = -1
while b:
a, (q, b) = b, divmod(a, b)
steps += q
return None if a > 1 else steps
我让你检查这两段代码是否等效：这并不难证明，但如果你不想拿出纸和笔，那么在提示下快速检查应该是令人信服的：
>>> all(steps_to_reach(a, b) == steps_to_reach_fast(a, b) for a in range(1, 1001) for b in range(1, 1001))
True
调用steps_to_reach_fast(a, b)需要O(log(max(a, b)))的算术运算。(这源于欧几里得算法的标准分析。)
现在可以直接找到给定n:的最小操作次数
def min_steps_to_reach(n):
"""
Find the minimum number of steps to reach a pair (*, n) or (n, *).
"""
# Count steps in all paths to (n, a). By symmetry, no need to
# check (a, n) too.
all_steps = (steps_to_reach_fast(n, a) for a in range(1, n+1))
return min(steps for steps in all_steps if steps is not None)
这个函数运行得相当快，最高可达n = 1000000左右。让我们打印出前几个值：
>>> min_steps_to_reach(10**6) # takes ~1 second on my laptop
30
>>> [min_steps_to_reach(n) for n in range(1, 50)]
[0, 1, 2, 3, 3, 5, 4, 4, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 7, 6, 7, 7, 7, 7, 7, 7, 8, 7, 7, 7, 8, 8, 7, 8, 8, 8, 9, 8, 8, 8, 9, 8, 8, 8, 8, 8, 9, 8]
在整数序列在线百科全书上搜索很快得到A178047序列，它与我们的序列完全匹配。序列描述如下：
考虑Farey树A006842/A006843；a(n)=分母n首先出现(假设第一行标记为第0行)。
事实上，如果你从(1, 1)开始查看由两个操作生成的树，并将每一对视为一个分数，你会得到与Stern-Brocot树(Farey树的另一个名称)非常相似的东西：每一行的内容都是相同的，但每一行中的顺序不同。事实证明，这是伪装的斯特恩布洛克树！
这一观察结果为我们提供了一个易于计算的min_steps_to_reach下界：很容易证明，在Stern-Brocot树的i行中，作为分子或分母出现的最大整数是i+2第二个Fibonacci数。因此，如果n > Fib(i+2)，那么min_steps_to_reach(n) > i(如果n == Fib(i+2)，则min_steps_to_reach(n)恰好是i)。要得到一个上界(或者在没有详尽搜索的情况下得到一个精确的值)似乎有点困难。以下是最坏的情况：对于每个整数s >= 0，最小的n需要s步(例如，506是第一个需要15步)：
[1, 2, 3, 4, 7, 6, 14, 20, 28, 38, 54, 90, 150, 216, 350, 506, 876, 1230, 2034, 3160, 4470, 7764]
如果这里有一个模式，我不会发现它(但它本质上是OEIS上的A135510序列)。
[我在意识到@mark dickinson已经回答之前写了这篇文章；他的回答比我的好得多，但我还是提供我的答案供参考]
如果你逆向工作，这个问题很容易解决。举个例子，假设N=65:
-
这意味着对于x和y的一些未知值，我们的当前对是{65，x}或{y，65}。
-
如果{A，B}是前一对，这意味着{A，A+B}或{A+B，B}等于{65，x}或{y，65}，这给了我们4种可能的情况：
-
{A，A+B}＝{65，x}，这意味着A=65。然而，如果A=65，我们在前面的步骤中已经达到了A=N，我们假设这是A=N或B=N的第一步，所以我们放弃了这种可能性。
-
｛A，A+B｝＝｛y，65｝，这意味着A+B＝65
-
｛A+B，B｝＝｛65，x｝，这意味着A+B＝65
-
{A+B，B}＝{y，65}，这意味着B＝65。然而，如果B=65，我们在前一步已经有了解决方案，我们也放弃了这种可能性。
-
因此，A+B=65。有65种方式可以发生这种情况(实际上，我认为你可以忽略A=0或B=0的情况，也可以通过对称选择B>A，但即使没有这些假设，解决方案也很容易)。
-
我们现在检查了所有65例病例。举个例子，让我们使用A=25和B=40。
-
如果{C，D}是生成{25,40}的对，则有两种可能的情况：
-
{C+D，D}={25,40}，所以D=40，C=-15，这是不可能的，因为从{1,1}开始，我们永远不会得到负数。
-
{C，C+D}＝{25,40}，因此C=25，并且D=15。
-
-
因此，{25,40}的"前身"必然是{25,15}。
-
通过类似的分析，{25,15}的前身，我们称之为{E，F}，必须具有以下属性之一：
-
{E，E+F}={25,15}，这是不可能的，因为这意味着F=-10
-
{E+F，F}＝{25,15}，意味着E=10和F=15。
-
-
类似地，{10,15}的前身是{10,5}，其前身是{5,5}。
-
{5,5}的前身是{0,5}或{5,0}。这两对是他们自己的前任，但没有其他前任。
-
由于我们从未在这个序列中命中{1,1}，我们知道{1,1}永远不会生成{25,40}，所以我们继续计算其他对{A，B}，使得A+B=65。
-
如果我们真的达到了{1,1}，我们会计算到达那里所需的步骤数，存储值，计算{A，B}的所有其他值，使A+B=65，并取最小值。
请注意，一旦我们选择了值a(从而选择了值B)，我们就有效地执行了欧几里得算法的减法版本，因此所需的步骤数为O(log(N))。由于你做了N次这些步骤，所以算法是O(N*log(N))，比你的O(2^N)小得多。
当然，你可以找到快捷方式，使方法更快。
有趣的笔记
如果您从｛1，1｝开始，以下是在删除重复项后，您可以在k个步骤中生成的对(我们使用k＝0表示｛1、1｝本身)：
k=0:{1,1}
k=1:{2,1}，{1,2}
k=2:{3,1}，{2,3}，{3,2}，{1,3}，{1/3}
k=3:{4,1}、{3,4}、{5,3}、{2,5}、{5/2}、{3,4}
k=4:{5，1}，{4，5}，{7，4}，{3，7}，{8，3}，{5，8}，{7,5}，｛2，7}、{7，2}，{5,7}，｛8，5}、{3，8}、{7,3}、{4,7}、｛5，4}、{1,5}
k=5:{6,1}、{5,6}、{9,5}、{4,9}、{11,4}、{7,11}、{10,7}、{3,10}、{11/3}、{8,11}、｛13,8}、{5,13}、｛12,5}、｛7,12}、｛9,7}、｛2,9}、｛9/2}、｛7}、｛5,12}、{13,5｝、｛8,13}、｛11,8}、｛3,11}、10，3}，{7，10}，{11，7}，{4，11}，{9，4}，{5，9}，{6，5}，{1，6}
需要注意的事项：
-
您可以在4个步骤中生成N=7和N=8，但不能生成N=6，这需要5个步骤。
-
生成的对数为2^k
-
达到给定N所需的最小步数(k)为：
N=1:k=0
N=2:k=1
N=3:k=2
N=4:k=3
N=5:k=3
N=6:k=5
N=7:k=4
N=8:k=4
N=9:k=5
N=10:k=5
N=11:k=5
得到的序列{0,1,2,3,3,5,4,5,5,5,5，…}是https://oeis.org/A178047
-
在k步中生成的最高数是第(k+2)个Fibonacci数，http://oeis.org/A000045
-
在k步中可以达到的不同整数的数量现在是http://oeis.org/A293160
-
作为k=20:的示例
-
当k=20 时，有2^20或1048576对
-
在上述1048576对中，最高的是17711，是第22个(20+2)斐波那契数
-
但是，使用这些对不能达到前17711个整数中的所有整数。你只能到达其中的11552个，A293160 的第21个(20+1)元素
-
有关如何解决此问题的详细信息，请参阅https://github.com/barrycarter/bcapps/blob/master/STACK/bc-add-sets.m