algorithm - 指定された範囲内の最大の異なる数を見つける

Question

a<=10*b および b<=10*a の場合、2 つの数値 (a,b) は類似していると言われます。2 つの範囲 low と high が指定された場合、指定された範囲内の類似していない数値の最大数を含むコレクションを返します。

ブルートフォースアプローチしか思い浮かびません。この問題をより複雑に解決する方法のアイデアが必要です。

Answer 1

あなたの説明から、大きい方が小さい方の 10 倍以下であれば、2 つの数値は似ていることがわかります。したがって、[low...high] の範囲から最大の数値セットを見つけて、そのセット内の 2 つの数値が類似しないようにする場合、解決策は、範囲内の最小の数値、つまり "low" から開始することです。毎回、セット内のどの数値にも類似していない次の最小の数値を取得します (または、セット内の最大要素に類似していないかどうかを確認するだけの場合は同じです)。

アルゴリズム：

lowを取り、次に10 * low + 1、10 * (10 * low + 1) + 1など...上限を超えるまで。

Answer 2

問題を正しく理解していれば、これはうまくいくはずです：

// start with smallest number:

var numbers = [];
var number = range.lowest;
// while not reached end of range
while (number <= range.highest) {
    // add this number;
    numbers.push(number);
    // find next not similar number
    number = numbers * 10 + 1;
}

// start with highest number:

var numbers = [];
var number = range.highest;
// while not reached end of range
while (number >= range.lowest) {
    numbers.push(number);
    // find next non-similar number
    var newNumber = Math.floor(number / 10.0);
    if (numNumber == number / 10.0);
        newNumber--;
    number = newNumber;
}

後者のアプローチは、最初のアプローチよりも多くの数値を見つけることができるかもしれません。試してみてください。ただし、同じサイズが可能な、類似していない数の異なるセットが常に存在する可能性があります。