python - 如果可能的话，如何获得所需的迭代次数来获得数组的 2 个元素？

Question

我对算法相当陌生，我正在处理一个我无法完全翻译成数学语言的问题。

所以，我得到了数组 [1,1]，我只能在每一步的数字之间执行一个求和，即你只能在以下之间进行选择：

[x(s+1), y(s+1)]=[x(s)+y(s),y(s)]

或者

[x(s+1),y(s+1)]=[x(s), x(s)+y(s)]

但不能同时

因此，

0: [1,1]
1: [2,1],                      [1,2]
2: [3,1],        [2,3],        [3,2],        [1,3]
3: [4,1], [3,4], [5,3], [2,5], [5,2], [3,5], [4,3], [1,4]
...and so on.

目标是知道需要多少步才能获得给定的 [x,y] 数组。

到目前为止，我知道

if (min(x,y)==1):
   steps =max(x,y)-1

if (x%2 ==0 and y%2==0):
   steps= not possible
if (max(x,y)%min(x,y) == 0):
   steps= not possible
if (x%3 ==0 and y%3==0):
   steps= not possible

我还为每对 (x,y) 绘制了需要多少步，并且我可以看到 x 或 y 的每个倍数都会发生一个模式，但是当 x 或 y >= 时，我不能将其写为数学函数5.

任何指导将不胜感激。

标签： pythonalgorithm

Answer 1

当两者x都y给出时，这比只给出其中一个要简单得多；）

要了解重复发生的情况，请考虑如果您坚持只更新一侧的多个步骤会发生什么。还要考虑在到达输入点之前必须发生的事情。

（还要注意与Calkin-Wilf 和 Stern-Brocot 树的相似性。）

JavaScript 代码（步数正确但显示的顺序跳过重复添加）：

var showSequence = 1;

function g(m, n){
  if (showSequence)
    console.log(m, n);

  if (m == 0 || n == 0)
    return Infinity;
  
  if (m == 1 || n == 1)
    return Math.max(m, n) - 1;
  
  if (m > n)
    return Math.floor(m / n) + g(m % n, n);
  else
    return Math.floor(n / m) + g(m, n % m);
}

var pairs = [
  [2, 5],
  [3, 7],
  [19, 4]
];

for (let [x,y] of pairs){
  console.log(g(x, y));
  console.log('');
}