javascript - 找到最短的数学运算序列

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)

标签： javascriptalgorithm

Answer 1

我只是在看 -11，并认为 11 是二进制的 1011，这类似于您的 LLRL 手动解决方案，只是倒退。测试表明这可能是负数的关键：获取它们的绝对值，然后开始向右移动直到它变为零。移出 1 时向左移动，移出 0 时向右移动。最后一步是左移，结果进入left.
然后我只是检查了正数是什么，简单地交换动作（因为将它们留在原地会产生负面结果），它似乎产生了一个高于目标的数字。所以我只是从原来的中减去了一个，它就开始起作用了。当然这次最后一步将是正确的，结果是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 - moveLefts 之后），那么*2= ，- (-119)= ，这正是需要将模式扩展到8 个最低位置）moveRight10011001010010...1111000100110001001100110001001
• 关于“最短”：增长最快的部分是moveRight，如果left一直保持为0 ，则right每步跳到2的下一个幂，因此ceil(log2(number))需要步数才能达到或超过给定的数字，即有效二进制数字的个数required 表示数字，等于循环所采取的步骤。