Перестановки Искатель Помогите Номер 2


Предыдущий вопрос:

Java-приложение для нахождения перестановок эффективно>

Я изменил немного код, и нужно еще немного комментариев.

class Permutations {

    static long factorial(int num){
        long factorial = num;
        for (int forBlockvar = num; forBlockvar > 1; forBlockvar--) {
            factorial = factorial * forBlockvar;
        }
        return factorial / num;
    }

    public static void main(String[] args){
        long FactNmR;
        int n = 8;
        int num = n;
        int r = 6;
        int nMr = n - r;

        long FactN = factorial(num);

        if (nMr == 2) {
            FactNmR = 2;
        }
        else if (nMr <= 1){
            FactNmR = 1;
        }
        else if (nMr >= 2) {
            num = nMr;
            FactNmR = factorial(num);
        }

        long permutations = FactN;

        permutations = permutations / FactNmR;

        System.out.println(permutations);
    }
}


981
2
задан 21 декабря 2011 в 04:12 Источник Поделиться
Комментарии
3 ответа

Комментарий код:

static long factorial(int num){
long factorial = num;
for (int forBlockvar = num; forBlockvar > 1; forBlockvar--) {
factorial = factorial * forBlockvar;
}
return factorial / num;
}

Вы начинаете свой факториал = Нум, умножив его на число в первой итерации цикла, а затем делением на число в конце. Начиная с факториал = 1, или начиная forBlockvar = Нум - 1 (я предпочитаю второй) позволит избавиться от необходимости делить в конце. Вы также можете вернуть 1, если на входе меньше 2.

static long factorial(int num){
if(num < 2) {
return 1;
}
long factorial = num;
for (int forBlockvar = num - 1; forBlockvar > 1; forBlockvar--) {
factorial = factorial * forBlockvar;
}
return factorial;
}

Вы также можете выполнить эту функцию рекурсивно.

static long factorial(int num){
if(num < 2) {
return 1;
}
return num * factorial(num - 1);
}

Общие:

Что вы имеете в виду нахождения перестановок из 2 цифр? Есть 2 перестановки 2 чисел [Х, Y]: [х, г] и [г, х].

Редактировать

Я думаю, что я знаю, что вы пытаетесь сделать сейчас... вы хотите знать, сколько перестановок можно получить, выбрав из R объектов из общего числа Н.

Основная формула для этого Н! / (н-р)!. Однако, это означает, что вычисление факториала (н-р) в два раза (в нашем примере, мы имеем 8*7*6*5*4*3*2*1 / 2*1, но с меньшим Р перекрытие будет больше).

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

Правка 2

Так вы поняли, что я намекал, я объясню далее.

Н! можно представить как Н*(Н-1)*(н-2)*(н-3)...(2)*(1). Когда р меньше, чем н а больше, чем 0, н! затем могут быть представлены как Н*(Н-1)*(н-2)...(п-р+1)*(п-р)*(н-р-1)*(н-р-2)...(2)*(1).

(н-р)! это (н-р)*(н-р-1)*(н-р-2)...(2)*(1).

Поэтому наш числитель - Н*(Н-1)*(н-2)...(п-р+1)*(п-р)*(н-р-1)*(н-р-2)...(2)*(1)и наш знаменатель (п-р)*(н-р-1)*(н-р-2)...(2)*(1). Отменяя, как условия, у нас есть н!/(н-р)! = Н*(Н-1)*(н-2)...(п-р+1).

static long permute(int totalItems, int numToPick) {
long permutations = totalItems;
while (--numToPick > 0) {
permutations *= --totalItems;
}
return permutations;
}

Вы должны убедиться, что 0 < numToPick <= totalItems, и totalItems > 0.

2
ответ дан 21 декабря 2011 в 05:12 Источник Поделиться

CodeAdmiral,

Я думаю, что я бы найти программу, Самый читаемый так:

Самый простой способ:

class Permutations {

static long factorial(int n) {
long f = 1;
while (n > 0) f *= n--;
return f;
}

public static void main(String[] args){
int n = 8, k = 6;
long permutations = factorial(n) / factorial(n-k);
System.out.println(permutations);
}
}

Конечно, этот метод является менее эффективным, а также более склонны к переполнению -- чем более прямой способ вычисления результата без лишних операций. Таким образом, более чистый путь будет такой:

Более эффективный способ:

class Permutations {

static long permutations(int n, int k) {
long p = 1;
while (k-- > 0) p *= n--;
return p;
}

public static void main(String[] args){
int n = 8, k = 6;
System.out.println(permutations(n, k));
}
}

Связав все это вместе с версией, которая также вычисляет N выбрать к (комбинации) дает следующее:

Вычислительной как перестановки и комбинации:

class Permutations {

static long factorial(int n) {
long f = 1;
while (n > 0) f *= n--;
return f;
}

static long permutations(int n, int k) {
long p = 1;
while (k-- > 0) p *= n--;
return p;
}

static long combinations(int n, int k) {
long a = 1, b = 1;
while (k > 0) { a *= n--; b *= k--; }
return a / b;
}

public static void main(String[] args){
int n = 8, k = 6;
System.out.println(
"Permutations: " + permutations(n, k) + " = " +
factorial(n) / factorial(n-k));
System.out.println(
"Combinations: " + combinations(n, k) + " = " +
factorial(n) / factorial(k) / factorial(n-k));
}
}

Надеюсь, что это помогает!

2
ответ дан 22 декабря 2011 в 12:12 Источник Поделиться

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

В факторный метод следует назначать 1 к факторной переменной в первой строке, поэтому вам не придется делить его с Нум в последней строке.

    static long factorial(int num) {
long factorial = 1;
...
return factorial;
}

Это приведет к более простой и легче читать код и он дает должного результата на 0.

После этого вы должны уменьшить если-иначе если-то-если структура после факторный метод сейчас дает должного результата для
2, 1 и 0.


Вы могли бы назвать факторного метода ЯМР в этой части:

num = nMr;
FactNmR = factorial(num);


На основе классической

P(n, k) = n! / ((n - k)!)

формула, Я бы создать одну переменную только одну вещь с этими именами:


  • Н, К для входных значений,

  • дифф будет результат н - к,

  • дивиденд будет результат в N!,

  • делитель будет результатом дивиденды!.

В н и к являются наиболее важными. Во всяком случае, поставить формулу в комментарий с используемые имена переменных. Это поможет читателям большое.

1
ответ дан 21 декабря 2011 в 06:12 Источник Поделиться