Возникла проблема с выводом этой комбинации в Java - PullRequest
Новая
       94

Возникла проблема с выводом этой комбинации в Java

2 голосов
/ 06 августа 2020

Я пытаюсь вычислить комбинацию по этой формуле: формула

У меня проблемы с выводом. Моя программа просто выводит 0, когда я запускаю этот код: 

public class Lottery {
    public static long numPossibleTickets(int k, int n, int m) {
        int i;
        int j;
        long numerator = n;
        long denominator = k;
        long total = 0;
        for (i = n - 1; i > (k + 1); i--) {
            numerator = numerator * i;
        }
        i = 0;
        for (j = k; j > 0; j--) {
            denominator = denominator * (denominator - i);
            i++;
        }
        total = m * (numerator / denominator);
        return total;
    }

    public static void main(String[] args) {
        Scanner scnr = new Scanner(System.in);
        int k = 5;
        int n = 69;
        int m = 26;
   System.out.println(numPossibleTickets(k, n, m));
    }
}

Однако вывод должен быть 292 201 338. Любая помощь с этим будет очень признательна. Большое спасибо!

Ответы [ 2 ]

1 голос
/ 07 августа 2020

В вашем коде есть как минимум 3 различных проблемы.

Вы пытаетесь вычислить количество комбинаций, используя факториалы. Проблема с факториалом в том, что он растет невероятно быстро: промежуточные результаты не попадают в диапазон для типа данных long, и результат бесполезен. Вы можете использовать BigInteger для вычислений, но это не будет особенно эффективно. С этим изменением: 

public static long numPossibleTickets(int k, int n, int m) {
    int i;
    int j;
    BigInteger numerator = BigInteger.valueOf(n);
    BigInteger denominator = BigInteger.valueOf(k);
    long total = 0;
    for (i = n - 1; i > (k + 1); i--) {
        numerator = numerator.multiply(BigInteger.valueOf(i));
    }
    i = 0;
    for (j = k; j > 0; j--) {
        denominator = denominator.multiply(denominator.subtract(BigInteger.valueOf(i)));
        i++;
    }
    total = m * numerator.divide(denominator).longValue();
    return total;
}

Во-вторых, l oop, вычисляющий числитель, отключен на единицу: вместо вычисления 69! / 5! это вычисление 69! / 6 !. К счастью, это легко исправить: 

    for (i = n - 1; i >= (k + 1); i--) {
        numerator = numerator.multiply(BigInteger.valueOf(i));
    }

В-третьих, l oop, который вычисляет знаменатель, кажется, далек от истины. Я не знаю, что вы пытаетесь сделать, но с учетом того, что вы вычисляете для числителя, знаменатель должен быть вычислением (nk) !, и это может выглядеть так: 

    BigInteger denominator = BigInteger.ONE;
    for (int j = n-k; j > 1; j--) {
        denominator = denominator.multiply(BigInteger.valueOf(j));
    }

With эти три изменения, я получаю ожидаемый результат 292201338.

1 голос
/ 07 августа 2020

Я бы предпочел создать метод для получения факториала числа. помимо того, что также используется BigInteger, поскольку его недостаточно для хранения факториала больших чисел, поэтому вот последний код, и он работает 

public static void main(String[] args) {

    int k = 5;
    int n = 69;
    int m = 26;
    System.out.println(numPossibleTickets(k, n, m)); // result is 292201338
}
public static BigInteger numPossibleTickets(int k, int n, int m) {
    int i;
    int j;
    BigInteger numerator =  getFactorial(n);
    BigInteger denominator = getFactorial(k).multiply(getFactorial(n-k));
    BigInteger total ;

    total = new BigInteger(m+"").multiply(numerator.divide(denominator));
    return total;
}

// to get the factorial of given number 
public static BigInteger getFactorial(int number){
    BigInteger factorial = new BigInteger(number+"");
    for (int i = number - 1; i > 1; i--) {
        factorial = factorial.multiply(new BigInteger(i+""));
    }
    return  factorial;
}
...