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)

Answer 1

我只是在看 -11，并认为 11 是二进制的 1011，这类似于您的 LLRL 手动解决方案，只是倒退。测试表明这可能是负数的关键:获取它们的绝对值，然后开始向右移动直到它变为零。移出 1 时向左移动，移出 0 时向右移动。最后一步是左移，结果进入left .
然后我只是检查了正数是什么，简单地交换 Action (因为将它们留在原地会产生负面结果)，它似乎产生了一个高于目标的数字。所以我只是从原来的中减去了一个，它就开始起作用了。当然这次最后一步将是右移，结果进入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 -s 之后)，然后 moveRight真的1001 *2= 10010 , 10010 - ...11110001001 (-119)= 10001001 ，这正是扩展 1001 所需要的模式成 10001001最低的 8 个位置)

关于“最短”:增长最快的部分是moveRight , 如果 left始终为 0，right每步跳到二的下一个幂，所以ceil(log2(number))达到或超过给定数字需要步骤，该数字等于表示该数字所需的有效二进制数字的数量，这等于循环所采取的步骤。