Получить сумму всех мин и макс из больших входных значений - PullRequest
Новая
       96

Получить сумму всех мин и макс из больших входных значений

0 голосов
/ 01 мая 2020

Мы выполняем следующее упражнение по программированию: Функции целых чисел на декартовой плоскости .

Задача - написать три функции, чтобы получить сумму всех минимальных чисел между 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));
    }
}

Однако время его выполнения истекает (поэтому он не проходит тесты) для больших входных чисел.

Как мы могли бы улучшить код, чтобы избежать вложенных циклов?

Мы прочитали, чтобы решить его самостоятельно:

1 Ответ

0 голосов
/ 02 мая 2020

Для sumin:

Целое число x меньше, чем nx других целых чисел в диапазоне [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.

Эти формулы будут очень быстрыми для большинства входных данных (но для ДЕЙСТВИТЕЛЬНО больших входных данных вы можете использовать алгоритм умножения быстрее, чем алгоритм по умолчанию)

...