代码之家 › 专栏 › 技术社区 › AnonymousSB

求最短的数学运算序列

algorithm javascript

AnonymousSB · 技术社区 · 6 年前

我在数学上试图确定最短的移动序列,以达到理想的数值结果。我有两个函数,都是一个数乘以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)

5 回复 | 直到 6 年前

tevemadar 6 年前

我刚才在看-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”这部分感觉就像是在创建反2的补码(在2的补码中,如果是正数,你什么都不做,如果是负数,你得到它的正数对,倒转它的位,结果加1)
如果一个人最终 10001001 (137)和 1001 是定位符,然后乘以2,所有的东西都向左移动( 100010010 ,274),如果你想保留 0001001 部分在其原始位置,减去固定器“局部分割”该部分回到其原始位置( 100010010 1001 100001001 moveRight
更新fixer更复杂,尽管它的某些部分确实类似于前面的想法:2* 变成 10010 ,和减法修复回 1001 在较低的地方,也介绍了 1 从高处开始。最糟糕的是明显大于 10010 如果目标数为正),则 1001 0 正确的 从1开始)。实际上,看看示例循环, 左边 似乎总是以不积极而告终
反二的补码也使情况变得丑陋,首先考虑负的目标数字可能更干净,因为有固定值( )是非负的,并且 positive*2-negative 也保持积极:
...11110001001 左边 ( 正确的 ), *2是 ...111100010010 ,和 ...111100010010 - 1001 ...111100001001 ,完成任务的第一部分(保持 1001
如果目标是 ...1110010001001 稍后(2之后 moveLeft -s) ,那么真的吗 1001 10010 , - ...11110001001 (-119)= ,这正是扩展 1001
关于“最矮”:增长最快的部分是 向右移动 正确的 每一步跳到2的下一次幂,所以 ceil(log2(number)) 步数需要达到或超过给定的数字,它等于所需的有效二进制数字的个数,表示该数字,它等于循环所采取的步数。

×××¢× ××¨×§× 6 年前

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));
}

Nina Scholz 6 年前

您可以采用迭代方法,为下一个状态设置一个堆栈来检查结果。

这种方法首先测试最小的变化量,然后对可能性进行不断增加的计数。

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; }

tevemadar 6 年前

是的,我也完全同意我自己的观点,我觉得我的暗示很有用(好吧,答案不见了)。
如果不需要验证,生成步骤很简单:

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; }