如何找到将 (a,b) 转换为 (x,y) 的步骤数
How to find number of steps to transform (a,b) to (x,y)
给定 2 个数字 a=1 和 b=1。
在每个步骤中，您可以执行以下操作之一：
- a+=b;
- b+=a;
如果可以将 a 转换为 x 并将 b 转换为 y，请找到所需的最少步骤
x和y可以任意大（大于10^15）
到目前为止，我的方法只是进行递归回溯，复杂度约为 O(2^min(x,y))（太大）。 DP 也不会做，因为状态可以超过 10^15。
有什么想法吗？是否需要任何数论来解决这个问题？
P.s。这不是作业。
鉴于您达到了某个 (x,y)，到达那里的唯一方法是将较小的值添加到现在较大的值中。假设 x > y，那么唯一可能的先前状态是 x-y, y.
另请注意，到达 x,y 的步数与到达 y,x 的步数相同。
所以你正在寻找的解决方案类似于
steps(x,y):
if x < y: return steps(y, x)
if y == 1: return x - 1
if y == 0: throw error # You can't get this combination.
return x / y + steps (y, x % y)
也就是说，在Calkin--Wilf tree中找到一个节点的深度。该节点存在当且仅当 gcd(a, b) = 1。您可以修改 gcd 算法以将操作数作为副产品给出（将沿途计算的所有商相加并减去一个）。
给定 2 个数字 a=1 和 b=1。
在每个步骤中，您可以执行以下操作之一：
- a+=b;
- b+=a;
如果可以将 a 转换为 x 并将 b 转换为 y，请找到所需的最少步骤
x和y可以任意大（大于10^15）
到目前为止，我的方法只是进行递归回溯，复杂度约为 O(2^min(x,y))（太大）。 DP 也不会做，因为状态可以超过 10^15。
有什么想法吗？是否需要任何数论来解决这个问题？
P.s。这不是作业。
鉴于您达到了某个 (x,y)，到达那里的唯一方法是将较小的值添加到现在较大的值中。假设 x > y，那么唯一可能的先前状态是 x-y, y.
另请注意，到达 x,y 的步数与到达 y,x 的步数相同。 所以你正在寻找的解决方案类似于
steps(x,y):
if x < y: return steps(y, x)
if y == 1: return x - 1
if y == 0: throw error # You can't get this combination.
return x / y + steps (y, x % y)
也就是说，在Calkin--Wilf tree中找到一个节点的深度。该节点存在当且仅当 gcd(a, b) = 1。您可以修改 gcd 算法以将操作数作为副产品给出（将沿途计算的所有商相加并减去一个）。