java使用算术运算，一共进了多少球？

Question

一名男子正在为一场足球比赛记分。他跟踪的部分结果如下：1-0，1-1，2-1，2-2，3-2。所有这些部分结果中的目标总和为15，最终结果为3-2，即5个目标。给定N这是部分结果的目标之和，您需要找到最终结果的目标数。以下是一些例子：

Input 15
Output 5

Input 6
Output 3

Input 55
Output 10

我不能用循环来解决这个问题；我只能使用if/else和算术运算。仅使用这些操作，我如何才能找到最终结果的目标数

Answer 1

似乎算术级数S（n）的和是给定的，你必须找到n。 使用简单的数学公式计算n：

S(n) = n * (n + 1) / 2

Answer 2

关于是否允许平方根，这个问题是不明确的，它是否严格算作算术运算

如果我们假设它是不允许的，并且我们不能使用任何循环，那么我们可以使用Newton's method来给出一个很好的近似答案。其他人指出，我们基本上是在尝试寻找三角形数T(n)=n(n+1)/2的倒数。如果给我们一个求和S让f(n)=n^2/2+n/2-S，我们要解f(n)=0。牛顿法是一种快速迭代法，给定初始猜测x0，我们可以使用x1找到更好的猜测

 x1 = x0 - f(x) / df(x)

其中df(x)=x-1/2是导数。如果我们这样做4次，就会得到一个很好的解决方案

public class InverseSqrt {

    static float f(float x,float S) {
        return x*x/2+x/2-S;
    }

    static float df(float x,float S) {
        return x+0.5f;
    }

    static float newton(float sum) {
        float x = sum/2; // first initial guess

        // Apply Newton's method four time
        x = x - f(x,sum) / df(x,sum); 
        x = x - f(x,sum) / df(x,sum);
        x = x - f(x,sum) / df(x,sum);
        x = x - f(x,sum) / df(x,sum);
        return x;
    }

    public static void main(String[] args) {
        int i=0;
        int ires=0;
        do {        // loop through possible number of goals
            ++i;
            float s = i * (i+1) * 0.5f; // calculate the total
            float res = newton(s);
            ires = (int) (res+0.5); // round to nearest integer

            System.out.print("T("+i+")="+(int)s);
            System.out.println("\tres="+ires+"\t("+res+")");

        } while(ires==i); // break first time it fails
    }
}

当输入351，输出26时，这项功能非常有效。但下一次输入378失败，目标是28而不是27

通过使用牛顿法的5个步骤，我们可以改进一些东西，输入为1176，输出为48。调整初始猜测可以显著提高性能，使用n/16的起始猜测和5个步骤可以工作到输入42195输出290

使用Fast inverse squareroot可以找到更好的解决方案。这可以在this answer之后的Java中实现

static float Q_rsqrt( float x )
{
    float xhalf = 0.5f*x;
    int i = Float.floatToIntBits(x);
    i = 0x5f3759df - (i>>1);
    x = Float.intBitsToFloat(i);
    x = x*(1.5f - xhalf*x*x);
    return x;
}

我们的牛顿迭代法是

static float newton(float sum) {
    float x = Q_rsqrt(1/sum);

    x = x - f(x,sum) / df(x,sum);
    x = x - f(x,sum) / df(x,sum);
    x = x - f(x,sum) / df(x,sum);
    return x;
}

只有3个迭代步骤

这将工作到输入1073720960输出46340。than之后的下一项在计算总和时会出现整数溢出，因此可以说它适用于所有合法的int值

这可能不算是一个合法的解决方案，因为它使用了floatToIntBits(x)和intBitsToFloat(x)这两种方法并不是真正的算术运算

Answer 3

这是一个求和问题。每次进球时都会创建一个记录。该记录始终比上一个记录大一个。总数是所有记录的总和

总数=总和（得分的目标数）

总目标数是1，那么你知道目标数也是1

如果总数为三，则有两个进球（1和1+1）

55=10+9+8+7+6+5+4+3+2+1，所以一共进了10个球

编辑计算实际答案比使用其他答案中显示的分数数学简单，但它需要解一个二次方程

Note that the solution to ax**2 + bx + c == 0 is 
x = (-b +/- SQRT( b**2 - 4*a*c) / 2*a

T = n(n+1)/2
2T = n**2 + n
n**2 + n - 2T = 0
n = (-1 +/- SQRT( 1 - 4*1*(-2T))) / (2 * 1), n > 0
n = (SQRT( 1 + 8T ) - 1) / 2

so if T = 10, n = (SQRT(81) - 1) / 2 == 4

Answer 4

r ="result"
s = "sum of goals"
n = "number of goals"

r      s            n

1-0    1            1
1-1    3            2
2-1    6            3
2-2    10           4
3-2    15           5

这告诉我们s只是前n个整数的和，但我们需要n（s），而不是s（n）

下面是一个计算示例

下面是在java中实现这一点的代码：

class Example {
    public static int n(int s) {
        return (int) Math.round(-1.0 / 2.0 + Math.sqrt(1.0 / 4.0 + 2.0 * s));
    }

    public static int s(int n) {
        return (n * (n + 1)) / 2;
    }

    public static void main(String[] args) {
        for (int n = 0; n <= 10; n++) {
            int s = s(n);
            printResult(s);
        }
    }

    private static void printResult(int s) {
        int n = n(s);
        System.out.println("If the sum of goals is " + s + ", then the number of goals is " + n);
    }
}

以下是输出：

If the sum of goals is 0, then the number of goals is 0
If the sum of goals is 1, then the number of goals is 1
If the sum of goals is 3, then the number of goals is 2
If the sum of goals is 6, then the number of goals is 3
If the sum of goals is 10, then the number of goals is 4
If the sum of goals is 15, then the number of goals is 5
If the sum of goals is 21, then the number of goals is 6
If the sum of goals is 28, then the number of goals is 7
If the sum of goals is 36, then the number of goals is 8