如何找到最接近目标输出（Y）的最佳函数输入整数（X）？

Question

这个答案与VBA中的excel宏有关，我正在寻找最佳解决方案。答案可以用伪代码、Python、Java或Excel兼容的VBA提供。该方法应能用excelvba编写。你知道吗

如果你有其他的解决方案（比如Haskell中的函数编程），我也希望看到，但这不是主要的问题。你知道吗

我有一个复杂的函数：y=函数（x），其中x是输入，y是输出。 x是一个整数 y是双精度（可以包含小数）

我知道x的目标范围，比如0到2000，或者800到1800。 我也知道y应该是什么。

函数是一个计算开销很大的函数，应尽可能少地计算。你知道吗

我看不到函数的内容，或者太复杂，无法分析。 函数的输出是一条递增曲线。 即x=2>；x=1然后y（2）>；y（1）

我需要找到给我一个最接近y的已知值的x值

计算效率最高的方法是什么？你知道吗

---

我想把这个范围分成20个区域，然后循环通过。循环将在比目标大的第一个y处停止。它将运行2到20次。然后我将转到精确的单位（整数）并循环这个子区域或子范围，这意味着调用的最大次数是（startingrange/20-即，如果起始范围是0到600），那么函数将被调用2到30次。你知道吗

有没有更好的方法来做到这一点，也许是递归的。 我好像错过了这条船？你知道吗

Answer 1

您可以编写另一个更简单的函数来计算所需值y和函数的输出之间的差值，然后根据差值的比例计算新的x。例如，在Python中

while abs(y-desired) > *whatever accuracy you need*:
   y = function(x)
   x = x + (x*((desired - y)/desired))
return x

通过找到（期望的-y），你可以找到离答案有多远，如果y太小的话，你可以把改变变成正的，如果y太大的话，你可以把改变变成负的。这个差值除以期望值，使差值成为误差百分比。最后，将百分比乘以x，使百分比误差变成与x的范围成比例的变化，不管是什么。你知道吗

这个公式可能需要根据你的具体情况稍加修改，但我认为这应该有助于你得到一个更准确的答案，通过这个大函数可以少跑很多次。你知道吗

Answer 2

显然，对于正规函数，答案是执行代数运算，直到可以解出x（因为如果知道y只有一个变量）。然而，在假设函数不能被分析的前提下，在一个范围内寻找某物的最佳方法是二进制搜索。这将运行函数O（log（n））次，这可能是使用这些条件所能达到的最少次数。你知道吗

像这样的。你知道吗

find_x(int xmin, int xmax, double y){
    if (xmin == xmax){
        return xmin;
    }
    int xmid = (xmax-xmin)/2;
    int resx = func(xmid);

    if (resx <= y){
       return find_x(xmin, xmid, y);
    if (resx > y){
       return find_x(xmid, xmax, y);
}

Answer 3

对于y值总是增加的函数，可以使用binary search快速缩小潜在值的范围。Python实现示例：

def binary_search(func, min_x, max_x, target_y):
    while max_x - min_x > 1:
        midpoint = (min_x + max_x) / 2
        if func(midpoint) > target_y:
            max_x = midpoint
        else:
            min_x = midpoint
    return min_x

print binary_search(lambda n: n**2, 0, 600, 300**2)

该算法具有对数效率。对于0到600的范围，它只调用func10次；对于两倍大的范围，它只调用11次。你知道吗