寻找最短的数学运算序列

Question

我正在尝试数学计算出达到所需数字结果的最短移动序列。我有两个函数，它们都将一个数字乘以2，并减去另一个数字的值。

以下是我的代码，目前我手动调用这两个函数来获得所需的结果；但是，我希望通过循环自动执行此操作的逻辑。

function findShortestSequence(number) {
    let left = 0;
    let right = 1;
    let moves = [];

    const moveLeft = () => {
        moves.push('L');
        left = 2 * left - right;
    }

    const moveRight = () => {
        moves.push('R');
        right = 2 * right - left;
    }

    moveLeft();
    moveLeft();
    moveRight();
    moveLeft();

    console.log(left, right, moves);
}

findShortestSequence(-11)

- AnonymousSB

Answer 1

我刚刚看了一下-11，并考虑到11在二进制中是1011，这类似于您手动解决问题LLRL，只是反过来。测试表明，这可能是负数的关键：获取它们的绝对值，向右移位直到变为零。当您移动一个1时，向左移动，当您移动一个0时，向右移动。最后一步将是一个左移动，结果放入left。
然后我只是检查正数情况，简单地交换移动（因为保留不变会提供负结果），它似乎生成了一个目标数以上的数字。所以我从原始数字中减去了1，并开始工作。当然，这次最后一步将是右移动，结果放入right：

function findShortestSequence(number) {
    let org = number;
    if(number<=0)number=-number; // work with absolute values when input is not positive
    else number--;               // work with one less, if input is positive
    let left = 0;
    let right = 1;
    let moves = [];

    const moveLeft = () => {
        moves.push('L');
        left = 2 * left - right;
    }

    const moveRight = () => {
        moves.push('R');
        right = 2 * right - left;
    }

    if(org<=0)
        while(number!=0){
          if(number&1)moveLeft();
          else moveRight();
          number>>=1;
        }
    else
        while(number!=0){
          if(number&1)moveRight();
          else moveLeft();
          number>>=1;
        }

    console.log(org, left, right, moves.join(''), (org==left)||(org==right));
}

for(var i=-20;i<=20;i++)
    findShortestSequence(i);

虽然我不打算提供全面的解释，但我可以提供一些您可能会发现有用的信息：

• "减1（如果是正数）"的部分感觉像创建反二进制补码数字（在二进制补码中，对于正数不做任何处理，对于负数取它的正数补码，反转其位，并将结果加1）
• 从远处看，“乘以2并修复”并不那么极端：
  如果某个数变成了10001001（137）,而1001是修复器，则乘以2会使每个位向左移动（100010010，274），如果要保留0001001在其原始位置上，"局部减去"修复器可以将该部分“局部除以”并返回原来的位置（100010010-1001=100001001），这基本上是moveRight对于正数所做的操作。
• 更新修复器更加复杂，但其中一些部分确实类似于上一个想法：2*1001变成了10010，而减去10001001则在较低的位置上修复了1001，并在高位引入了开头的1。恶心的是，10001001显然比10010大，因此结果是一个负数，并且实际上修复器（在目标数为正的情况下是left）从来没有是过1001，因为在第一次更新时，它就变成了"2*0-something"（其中“something”是一个正数，因为right从1开始）。事实上，在查看示例循环时，left似乎总是最终变为非正数，而right似乎保持为非负数。
• 反二进制补码也使问题变得更加复杂，可以先考虑负的目标数，因为修复器（right）为非负数，而且positive*2-negative仍然为正数：
  ...11110001001（left）和1001（right），...11110001001*2等于...111100010010，并且...111100010010-1001=...111100001001，完成了第一部分任务（保留1001模式）
  如果目标是稍后要达到的...1110010001001（在2个moveLeft之后），那么moveRight确实会执行1001*2=10010，10010-...11110001001（-119）=10001001，这正是将1001模式扩展到8个最低位的所需的操作。
• 关于“最短”的问题：增长最快的部分是moveRight，如果left始终保持为0，则每一步right都跳到下一个2的幂，因此需要ceil(log2(number))步骤才能达到或超过给定的数字，这等于表示数字所需的有效二

- tevemadar

---

这是一个关于使用位运算符的很好的观察。我所做的一个小修改是去掉了 if(org <= 0) 语句，并用三元运算符替换了 moveLeft() 和 moveRight()。 - AnonymousSB

@AnonymousSB，因为我对另一个答案中的“看，很容易”的解释有些疑问，所以添加了一些关于内部发生了什么的想法。 - tevemadar

Caleb Lucas的答案在我看来对于正数无法奏效。我理解错了吗？例如，任何2的幂次方都会包括一个“L”，而我们只需要R。而且测试3和-3只返回LL。这怎么可能？ - גלעד ברקן

@גלעדברקן 对于正数来说，那个答案是完全错误的：它返回生成相应负数的序列，只是镜像。它无法从“1”开始工作，这应该导致一个空序列，因为“right=1”已经（与“0”一样，因为“left=0”已经）。 - tevemadar

@ArsalanAhmed 这只是一个猜测（用词优美：启发式技术），我没有遵循任何正式的方法，只是看了一下二进制表示中的位数。顺便说一句：https://cs.stackexchange.com/ 可能是一个讨论算法设计理论问题的姊妹站点。 - tevemadar

Answer 2

我认为我得出了和tevemadar相同的结论。以下是代码：

```html

我认为我得出了和tevemadar相同的结论。以下是代码：

```

function confirm(str, n){
  let l = 0;
  let r = 1;
  let i = 0;
  
  while(str[i]){
    if (str[i++] == 'L')
      l = 2*l - r;
    else
      r = 2*r - l;
  }
  
  if ([l, r].includes(n))
    return true;
    
  return false;
}

function f(n){
  if ([0, 1].includes(n))
    return '';
  else if (n > 1)
    return (n - 1)
      .toString(2)
      .split('')
      .map(x => x & 1 ? 'R' : 'L')
      .reverse()
      .join('');
  else
    return (-n)
      .toString(2)
      .split('')
      .map(x => x & 1 ? 'L' : 'R')
      .reverse()
      .join('');
}

for (let i=-11; i<=11; i++){
  fi = f(i);
  console.log(i + ': ' + fi + ', ' + confirm(fi, i));
}

- גלעד ברקן

---

虽然至少有错误的被接受的答案已经完全消失了，但我仍然感到困惑，为什么对于提问者来说接受一个与我的答案不同的答案如此重要... - tevemadar

我接受了这个答案，因为提供的确认函数显示它生成了正确的移动，除非我漏掉了什么？ - AnonymousSB

Answer 3

你可以采用迭代的方法，使用栈来存储下一个状态以检查结果。

这种方法首先测试最小量的更改，然后逐渐增加可能性的数量。

function findShortestSequence(number) {
    const
        moveLeft = (left, right, moves) => [left * 2 - right, right, [...moves, 'L']],
        moveRight = (left, right, moves) => [left, right * 2 - left, [...moves, 'R']],
        functions = [moveLeft, moveRight];

    var stack = [[0, 1, []]],
        left, right, moves;

    while ([left, right, moves] = stack.shift()) {
        if (left === number) return moves;
        functions.forEach(fn => stack.push(fn(left, right, moves)));
    }
}

console.log(findShortestSequence(-11));

.as-console-wrapper { max-height: 100% !important; top: 0; }

- Nina Scholz

---

你如何确保这个程序终止？ - Simone

@Simone，它终止了，因为有限的值，假设堆栈足够深。 - Nina Scholz

@NinaScholz 此处正整数输入无法终止程序。 - nickj

Answer 4

是的，我也完全同意自己，并发现我的提示很有用（好的，那个答案已经消失了）。

如果不需要验证，生成步骤就这么简单：

function getSequence(n){
  if(n==0 || n==1)return "";
  var steps=n<0?["R","L"]:["L","R"];
  return (n<0?-n:n-1).toString(2)                        // get binary number
         .replace(/0/g,steps[0]).replace(/1/g,steps[1])  // replace digits with L/R
         .split('').reverse().join('');                  // reverse order
}

for(var i=-20;i<=20;i++)
  console.log(i,getSequence(i));

.as-console-wrapper { max-height: 100% !important; top: 0; }

- tevemadar

---

我真的很欣赏你的努力，并且对于它是二进制的原始观察非常感激。这个解决方案比@גלעדברקן的答案更简洁，提供了相同的结果。提前交换步骤非常聪明。考虑到最大二进制长度为31，我没有看到任何主要的时间复杂度问题；然而，你可以使用这个replace来减少一次操作，而不是.replace(/0|1/g, match => match === '0' ? steps[0] : steps[1])。 - AnonymousSB