7

2つの値があるとしましょう。可能な限り最短のバイナリ展開で0 <= a < b <= 1、どのように選択xできますか？a <= x<b

これまでの私のアプローチは、小数点を削除したaとのバイナリ文字列を取得することです。最初にそれらは異なり、そのポイントまでの展開を取得します。消費するものがもっとある場合は、最後のビットを取り除きます。最後に、を追加します。baa1

JavaScriptの場合：

var binaryInInterval = function(a, b) {
  if (a < 0 || b > 1 || a >= b) return undefined;

  var i, u, v, x = '';

  a = a.toString(2).replace('.', '');
  b = b.toString(2).replace('.', '');

  for (i = 0; i < Math.max(a.length, b.length); i++) {
    u = parseInt(a.substr(i, 1), 10) || 0;
    v = parseInt(b.substr(i, 1), 10) || 0;

    x += u.toString();
    if (u != v) { 
      if (i + 1 < a.length) x = x.slice(0, -1);
      x += '1';
      break;
    }
  }

  return '0.' + x.substr(1);
};

これは機能しますが、一般的に正しいとは思いません。何かご意見は？...

編集私はすでに正しく動作しないケースを見つけました：P

binaryInInterval(0.25, 0.5) = '0.1'

0.25  0.01
0.5   0.1
        ^ Difference
          but a hasn't been fully consumed
          so we strip 00 to 0 before adding 1

編集2別のアルゴリズムは、反復して2^-n、これの倍数が間隔内に収まるかどうかを確認することです。ただし、これはより高価になります。

4

3 に答える 3

4

a = 0.1、b = 0.100001 (2 進数で -- つまり、10 進数で a = 0.5、b = 0.515625) のような入力では失敗します。この場合、正解は 0.1 になりますが、アルゴリズムは代わりに 0.11 を生成します。これは、最小長であるだけでなく、b よりも大きくなります :-(

あなたの数字チェックは私にはうまく見えます-問題は、ループを終了する（正しい）決定をしたときに、bの数字文字列が長い場合、間違った出力を作成することです。これを修正する簡単な方法の 1 つは、数字を一度に 1 つずつ出力することです。別の文字が表示されるまで、現在の文字を含める必要があることがわかります。

もう 1 つのヒント: 私は Javascript をよく知りませんが、どちらのparseInt()呼び出しも不要だと思います。uv

[編集]

以下は、いくつかの考慮事項を組み込んだ 1 桁ずつのコードの例です。

var binaryInInterval = function(a, b) {
  if (a < 0 || b > 1 || a >= b) return undefined;

  if (a == 0) return '0';  // Special: only number that can end with a 0

  var i, j, u, v, x = '';

  a = a.toString(2).replace('.', '');
  b = b.toString(2).replace('.', '');

  for (i = 0; i < Math.min(a.length, b.length); i++) {
    u = a.substr(i, 1);
    v = b.substr(i, 1);

    if (u != v) {
      // We know that u must be '0' and v must be '1'.
      // We therefore also know that u must have at least 1 more '1' digit,
      // since you cannot have a '0' as the last digit.
      if (i < b.length - 1) {
        // b has more digits, meaning it must
        // have more '1' digits, meaning it must be larger than
        // x if we add a '1' here, so it's safe to do that and stop.
        x += '1';     // This is >= a, because we know u = '0'.
      } else {
        // To ensure x is >= a, we need to look for the first
        // '0' in a from this point on, change it to a '1',
        // and stop.  If a only contains '1's from here on out,
        // it suffices to copy them, and not bother appending a '1'.
        x += '0';
        for (j = i + 1; j < a.length; ++j) {
          if (a.substr(j, 1) == '0') {
            break;
          }
        }
      }
      break;  // We're done.  Fall through to fix the binary point.
    } else {
      x += u;    // Business as usual.
    }
  }

  // If we make it to here, it must be because either (1) we hit a
  // different digit, in which case we have prepared an x that is correct
  // except for the binary point, or (2) a and b agree on all
  // their leftmost min(len(a), len(b)) digits.  For (2), it must therefore be
  // that b has more digits (and thus more '1' digits), because if a
  // had more it would necessarily be larger than b, which is impossible.
  // In this case, x will simply be a.
  // So in both cases (1) and (2), all we need to do is fix the binary point.
  if (x.length > 1) x = '0.' + x.substr(1);
  return x;
};
于 2012-12-21T12:12:33.030 に答える
3 
function bin(a, b) {
 var den = 1;
 while (true) {
  var bint = Math.floor(b);
  if (bint == b) bint--;
  if (a <= bint) {
   return bint / den;
  }
  den *= 2;
  a *= 2;
  b *= 2;
 }
}

denコードは、範囲内に収まる値をサポートする分母が見つかるまで、2 のべき乗の分母 ( ) を繰り返します。

于 2012-12-22T11:29:58.827 に答える
2

別のバージョンのコードを投稿しています。それは既知の問題を修正しようとします:

  var binaryInIntervalNew = function(inpA, inpB) {

    if (inpA < 0 || inpB > 1 || inpA >= inpB) return undefined;

    var i, u, v, x = '';

    a = inpA.toString(2).split('.');
    b = inpB.toString(2).split('.');

    a = a[a.length - 1];
    b = b[b.length - 1];

    for (i = 0; i < Math.min(a.length, b.length); i++) {

      u = a.substr(i, 1);
      v = b.substr(i, 1);

      if (u !== v) {
        // x cannot become equal to b, let us verify that
        if ((i+1) === b.length) {
          x += '01';
        } else {
          x += '1';
        }
        break;
      } else {
        x += u;
      }
      // console.log("x: " + x + " i:" + i);
    }

    x = '0.' + x;
    return parseFloat(x);
  };

両方の機能をテストする短い機能:

function bin(a, b) {
  console.log("a:" + a.toString(2));
  console.log("b:" + b.toString(2));
  if (binaryInIntervalNew) console.log("binaryInIntervalNew: " + binaryInIntervalNew(a, b));
  if (binaryInInterval) console.log("binaryInInterval: " + binaryInInterval(a, b));
}

今いくつかの結果:

bin(1/16, 1/4);
a:0.0001 
b:0.01
binaryInIntervalNew: 0.001
binaryInInterval: 0.01

bin(.1, .2);
a:0.0001100110011001100110011001100110011001100110011001101 
b:0.001100110011001100110011001100110011001100110011001101
binaryInIntervalNew: 0.001
binaryInInterval: 0.001

bin(1/4, 1/2);
a:0.01 b:0.1
b:0.1
binaryInIntervalNew: 0.01
binaryInInterval: 0.1

bin(.2, .5);
a:0.001100110011001100110011001100110011001100110011001101 b:0.1
b:0.1
binaryInIntervalNew: 0.01
binaryInInterval: 0.1

bin(.0011, .1);
a:0.00000000010010000001011011110000000001101000110110111000101111 b:0.0001100110011001100110011001100110011001100110011001101
b:0.0001100110011001100110011001100110011001100110011001101
binaryInIntervalNew: 0.0001
binaryInInterval: 0.0001
于 2012-12-21T17:02:11.460 に答える