从大的输入值中获取所有分钟和最大值的总和。

Question

我们正在做以下编程练习。整数函数在笛卡尔平面上的应用。.

我们的任务是写出三个函数，得到x和y之间所有最小数的和（所有的组合），另一个函数得到x和y之间所有最大数的和，第三个函数得到前面几个数的和。

我们已经写好了。

import java.math.BigInteger;

public class Funcij {

    public static BigInteger  sumin /*⬇️*/ (int n) {
        System.out.println("\nsumin n: "+n);
    BigInteger sum = BigInteger.ZERO;
    for(int y=1; y<=n; y++){
      for(int x=1; x<=n; x++){
        sum = sum.add(BigInteger.valueOf(Math.min(x,y)));  
      }
    }
    return sum;
    }
    public static BigInteger  sumax /*⏫*/ (int n) {
        System.out.println("\nsumax n: "+n);
    BigInteger sum = BigInteger.ZERO;
    for(int y=1; y<=n; y++){
      for(int x=1; x<=n; x++){
        sum = sum.add(BigInteger.valueOf(Math.max(x,y)));  
      }
    }
    return sum;
    }

    public static BigInteger  sumsum /*➕*/ (int n) {
        System.out.println("\nsumsum n: "+n);
    return sumin(n).add(sumax(n));
    }
}

但是它的执行时间会耗尽 (所以它不能通过测试) 对于大的输入数字。

我们如何改进代码以避免嵌套循环？

我们已经读到了自己解决这个问题。

• https:/www.geeksforgeeks.orgbiginteger-valueof-method-in-java
• 有什么方法可以避免在添加到列表中时出现循环？
• https:/www.geeksforgeeks.orgbiginteger-class-in-java
• 从这个哈希数组中获取最小值和最大值。
• 所有数值在最小值和最大值之间

Answer 1

对于和素．

整数x比n -x范围内的其它整数小 [1, n]. 因此，它将有助于 x * (n - x) + x (+x，因为我们还在x和x之间加上了最大值)。如果你把这个表达式的Xs从1加到n，你将得到 n*(n+1)*(n+2)/6. 最后一个表达式正好是sumin。

同理，对于sumax，每个数字都将准确地贡献出 x*x 综上所述 n*(n+1)*(2n+1)/6，同样，这将是精确的sumax。

这些公式对于大多数输入来说都是非常快的 (但是对于非常大的输入，你可能需要使用比默认算法更快的乘法算法)