查找最短的数学运算顺序

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)

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-事物”（其中“事物”是一个正数，right从1开始）。确实，查看示例循环，left总是看起来总是非正的，并且right似乎非负的。
• 反补的东西也uglifies图片，它可能是更清洁去想负目标数第一，因为有定影液（right）非负，并且positive*2-negative还保持积极的：
  ...11110001001（left）和1001（right），...11110001001* 2 ...111100010010，和...111100010010- 1001= ...111100001001，任务的第一部分完成（保持1001模式不变）
  ，如果目标是...1110010001001稍后（在2 moveLeft-s之后），则* 2 = ，- （- 119）= moveRight确实如此，这正是需要将模式扩展到最低的8个位置）10011001010010...1111000100110001001100110001001
• 关于“最短”：增长最快的部分是moveRight，如果left一直保持为0，则right跳到每一步的下一个幂次，因此ceil(log2(number))需要达到或超过给定数字（等于有效二进制数字的数量）的步数必需表示数字，它等于循环所采取的步骤。