Javascript - 获取计算机方程的最小整数解

Question

我在尝试解决编程中的方程时遇到问题。

想象一下，我有这样一行代码：

Math.round(((x / 5) + Math.pow(x / 25, 1.3)) / 10) * 10;

给定 x = 1000，结果为 320。

现在，我如何在给定结果的情况下求解这个方程？

想象一下，给定结果 320，我想获得解析该行代码的最小整数值 x。

/*320 =*/ Math.round(((x / 5) + Math.pow(x / 25, 1.3)) / 10) * 10;

由于Math.Round，我遇到了一些困难。即使认为表达式是一个线性方程，Math.Round 也为x提供了比一个更多的解决方案，所以我想要我的解决方案的最小整数值。

请注意，x 是一个整数，如果我设置 x = 999，结果仍然是 320。

如果我继续降低 x，我可以看到 984(至少在 Chrome 64.0.3282.186 中(在这种情况下是正确的答案，因为 x 的最小值等于该表达式/编程行中的 320。

Answer 1

用 Math.round 求解方程只是引入了边界条件。

如果：

Math.round(((x / 5) + Math.pow(x / 25, 1.3)) / 10) * 10 = 320

然后：

Math.round(((x / 5) + Math.pow(x / 25, 1.3)) / 10)  = 32

通过将双方除以 10。 现在您有：

Math.round(expression) = 32

这可以表示为不等式陈述：

31.5 < expression < 32.4999..

等于 31.5 的表达式表示一个边界，等于 32.499 的表达式表示另一个边界。因此，求解边界需要求解：

expression = 31.5 and expression = 32.49999...
((x / 5) + Math.pow(x / 25, 1.3))/10 = 31.5  and 
((x / 5) + Math.pow(x / 25, 1.3))/10 = 32.4999

解决 x 的这两个问题将为您提供 x 的有效值范围。 现在这只是代数，我不打算做:)

Answer 2

我想最可靠的工作方式(尽管有些幼稚(是遍历所有有效数字并检查谓词。

function getMinimumIntegerSolution(func, expectedResult){
  for(let i = 0 /*Or Number.MIN_SAFE_INTEGER for -ves*/; i< Number.MAX_SAFE_INTEGER ; i++ ) { 
    if(func(i) === expectedResult)
        return i;
  }
}

现在

getMinimumIntegerSolution((x) => Math.round(((x / 5) + Math.pow(x / 25, 1.3)) / 10) * 10 , 320)

这将返回您期望的内容 984

Answer 3

因为函数定义

f(n) = Math.round(((x / 5) + Math.pow(x / 25, 1.3)) / 10) * 10

是单调的(在这种情况下，递增(，您可以进行二叉搜索。请注意，我最初是用 Java 编写的以下代码，它在 Javascript 中的语法不正确，但希望可以直接翻译成后者。

var x0 = 0;
var x1 = 1e6;
var Y = 320d;
var epsilon = 10d;
var x = (x1 - x0) / 2d;
var y = 0;
while (Math.abs(Y - (y = f(x))) > epsilon) {
   if (y > Y) {
      x = (x - x0) / 2d;
   } else {
      x = (x1 - x) / 2d;
   }
   // System.out.println(y + " " + x);
}
while (f(x) < Y)
   ++x;
// System.out.println(Math.round(x) + " " + f(x));

在我的计算机上运行它，未注释System.out.println：

490250.0 250000.0
208490.0 125000.0
89370.0 62500.0
38640.0 31250.0
16870.0 15625.0
7440.0 7812.5
3310.0 3906.25
1490.0 1953.125
680.0 976.5625
984 320.0

• 请注意，最后一个循环递增x保证在不到 epsilon 步的时间内完成。
• 可以调整x0、x1和epsilon的值，以便为您的问题提供更好的边界。
• 如果 epsilon 的值"太小"，则此算法将失败，因为舍入发生在 f 中。
• 此解决方案的复杂性是O(log2(x1 - x0)) 。

Answer 4

除了@webnetweaver答案。如果你重新排列最终方程，你会得到一个难以用代数求解的高阶多项式(13 次(。您可以使用数值方法作为牛顿方法。对于 JavaScript 中的数值方法，您可以使用 numeric.js。您还需要仅求解下限 (31.5( 以找到最低整数 x，因为该函数是单调递增的。另请参阅这篇关于 JavaScript 中数值方程求解的文章。

这是使用牛顿方法的解决方案。它使用 0 作为初始猜测。只需五次迭代即可获得最小整数解。

var result = 320;
var d = result - 5;
function func(x) {
  return x / 5 + 0.0152292 * Math.pow(x, 1.3) - d;
}
function deriv(x) {
  return 0.2 + 0.019798 * Math.pow(x, 0.3);
}
var epsilon = 0.001; //termination condition
function newton(guess) {
  var approx = guess - func(guess) / deriv(guess);
  if (Math.abs(guess - approx) > epsilon) {
    console.log("Guess: " + guess);
    return newton(approx);
  } else {
    //round solution up for minimum integer
    return Math.ceil(approx);
  }
}
console.log("Minimum integer: " + newton(0));