Получить обратное уравнение - JavaScript

Question

Допустим, у меня есть эта формула, например:

function getExperience(level) {
  let a = 0;
  for (let x = 1; x < level; x += 1) {
    a += Math.floor(x + (200 * (2 ** (x / 3))));
  }

  return Math.floor(a / 4);
}


for (var i = 1; i < 100; i++) {
  console.log(`Level ${i}: ${getExperience(i)}`);
}

Чтобы получить опыт, необходимый для 50-го уровня, вы должны сделать: getExperience(50).

Но как бы вы изменили это и получили УРОВЕНЬ?нужен для опыта?Таким образом, getLevel(20010272) будет выводить 50.

Answer 1

Короткий ответ

Вы можете использовать 4.328085 * Math.log(0.00519842 * xp + 1.259921045) как очень хорошее приближение соответствующего уровня.

Если вам нужно точное значение, вы можете перебирать все уровни, пока не найдетежелаемый диапазон, как в этом ответе .

Длинном ответе

Слегка измененная функция

Не думаю, что можно найти точный, выражение в замкнутой форме для обратной функции.Это возможно, если вы немного измените getExperience(level).

• Во-первых, вы можете заметить, что x растет намного медленнее, чем 2 ** (x / 3).
• Тогда Math.floor не имеет большого влияния на большие числа.

Так что давайте удалим их!Вот немного измененная функция:

function getExperienceEstimate(level) {
  let a = 0;
  for (let x = 1; x < level; x += 1) {
    a += 200 * (2 ** (x / 3));
  }
  return a / 4;
}

Преимущество этого метода состоит в том, что теперь он представляет собой геометрический ряд , поэтому можно вычислять сумму напрямую , безлюбой цикл:

function getExperienceEstimate(level) {
  let a = 50;
  let r = 2 ** (1 / 3);
  return a * (r**level - r) / (r - 1);
};

getExperienceEstimate(50) возвращает 20011971.993575357, что всего на 0,0015% меньше, чем getExperience(50).

Обратная функция

Согласно Wolfram Alpha , вот обратная функция getExperienceEstimate:

function getLevelEstimate(xp){
  let a = 50;
  let r = 2 ** (1 / 3);
  return Math.log(xp * (r - 1) / a + r) / Math.log(r);
};

С небольшой потерей точности вы можете еще больше упростить ее:

function getLevelEstimate(xp){
  return 4.328085 * Math.log(0.00519842 * xp + 1.259921045)
};

Это только оценка,но он работает довольно хорошо и не требует никакого цикла!

Test

Для 20012272 XP приблизительная обратная функция возвращает 50.00006263463371, что должно быть хорошей отправной точкой, если вы хотитенайти точный результат.

function getExperience(level) {
  let a = 0;
  for (let x = 1; x < level; x += 1) {
    a += Math.floor(x + (200 * (2 ** (x / 3))));
  }
  return Math.floor(a / 4);
}

function getLevelEstimate(xp){
  return 4.328085 * Math.log(0.00519842 * xp + 1.259921045)
};

for (var i = 1; i < 100; i++) {
  console.log(`Level ${i} (XP = ${getExperience(i)}). Estimated level : ${getLevelEstimate(getExperience(i))}`);
}

Answer 2

Идея бинарного поиска может быть использована следующим образом.Обратите внимание, что следующее предполагает, что существует максимум 100 уровней.При необходимости вы можете изменить его на 1000, 10000 или 100000.

function getExperience(level) {
    let a = 0;
    for (let x = 1; x < level; x += 1) {
        a += Math.floor(x + (200 * (2 ** (x / 3))));
    }
    return Math.floor(a / 4);
}

function getLevel(exp) {
    let min = 1,
        max = 100;
    while (min <= max) {
        let mid = Math.floor((min + max) / 2),
            expm = getExperience(mid),
            expn = getExperience(mid + 1);
        if (expm <= exp && exp < expn) {
            return mid;
        }
        if (expm < exp) {
            min = mid + 1;
        } else {
            max = mid - 1;
        }
    }
    return null;
}

console.log(getLevel(getExperience(17)));
console.log(getLevel(getExperience(17) - 1));
console.log(getLevel(getExperience(100)));
console.log(getLevel(getExperience(100) - 1));

Answer 3

Вы можете использовать бинарный поиск , чтобы быстрее определить значение уровня - максимум за 7 шагов

(хотя я сомневаюсь, что усиление имеет значение для списка длины 100)

Answer 4

Вы можете использовать алгоритм двоичного поиска , чтобы избежать зацикливания всех возможностей.

Здесь - это пример, который я адаптировал к вашему случаю.

Сначала вам нужно создать массив для отображения всех ваших level => experience, это действие должно быть выполнено только ОДИН РАЗ, затем вам никогда не придется делать это снова.

Как вы можете видеть в моем примере,даже с 1000 уровнями вам никогда не придется повторять более 9 раз любой уровень, который вы пытаетесь найти.

// You first have to create an array with all your levels.
// This has to be done only ONCE because it's an expensive one!
const list = [];
for (let i = 1; i <= 1000; i++) {
  list[i] = getExperience(i);
}

function getExperience(level) {
  let a = 0;
  for (let x = 1; x < level; x += 1) {
    a += Math.floor(x + (200 * (2 ** (x / 3))));
  }

  return Math.floor(a / 4);
}

function getLevel(value) {
  // initial values for start, middle and end
  let start = 0
  let stop = list.length - 1
  let middle = Math.floor((start + stop) / 2)
  let iterations = 0;
  
  // While the middle is not what we're looking for and the list does not have a single item.
  while (list[middle] !== value && start < stop) {
    iterations++;
    if (value < list[middle]) {
      stop = middle - 1
    } else {
      start = middle + 1
    }

    // Recalculate middle on every iteration.
    middle = Math.floor((start + stop) / 2)
  }
  
  console.log(`${value} is Level ${middle} (Result found after ${iterations} iterations)`);
  return middle;
}

// Then you can search your level according to the experience
getLevel(0);
getLevel(72);
getLevel(20010272);
getLevel(getExperience(50));
getLevel(33578608987644589722);

Answer 5

Грубое (но не элегантное) решение состоит в том, чтобы просто вызывать getExperience для уровней, пока вы не достигнете уровня, который требует больше опыта, чем пройденный exp:

function getLevel(exp) {
  if (exp === 0) return 0;
  let level = 0;
  let calcExp = 0;
  while (exp > calcExp) {
    calcExp = getExperience(level);
    if (calcExp > exp) break;
    level++;
  }
  return level - 1;
}

console.log(getLevel(20012272)); // experience required for 50 on the dot
console.log(getLevel(20012270));
console.log(getLevel(20012274));
console.log(getLevel(0));

function getExperience(level) {
  let a = 0;
  for (let x = 1; x < level; x += 1) {
    a += Math.floor(x + (200 * (2 ** (x / 3))));
  }

  return Math.floor(a / 4);
}