Треугольник Паскаля имеет практическое применение в комбинаторике для нахождения сочетания из
n по
k.
Определение из Википедии:
В комбинаторике сочетанием из n по k называется набор k элементов, выбранных из данного множества, содержащего n различных элементов. Наборы, отличающиеся только порядком следования элементов (но не составом), считаются одинаковыми, этим сочетания отличаются от размещений.
Вы можете встретить два вида обозначения сочетения из
n по
k:
или
Давайте придумаем задачу.
Задача
Пусть у нас есть множество из 5 элементов: {1,2,3,4,5}.
Нужно найти кол-во сочетаний из трех элементов.
Причем наборы вида: {1,2,3} и {1,3,2} считаются одинаковыми и засчитываются только один раз.
Ответ
Из 5 элементов мы можем составить
10 наборов по 3 элемента.
Вот эти подмножества:
- {1,2,3}
- {1,2,4}
- {1,2,5}
- {1,3,4}
- {1,3,5}
- {1,4,5}
- {2,3,4}
- {2,3,5}
- {2,4,5}
- {3,4,5}
Решение
Задача сводится к нахождению сочетания из 5 по 3, т.е. n = 5, k = 3.
Для нахождения сочетания есть готовая формула:
Подставим наши значения в формулу:
Пример реализации этой формулы на Java:
long C(int n,int k){
return fact(n) / (fact(k) * fact(n-k));
}
long fact(int num){
long val = 1;
for (int i = 2; i <= num; i++) {
val *= i;
}
return val;
}
Пример использования:
System.out.println(C(5,3));//возвратит 10
Вычисляя факториалы в формуле, мы проводим вычисления в числителе и знаменателе, и можно заметить, что некоторые операция умножения можно сократить.
Усовершенствованная версия:
long C(int n,int k){
int res = 1;
for (int i = n - k + 1; i <= n; i++) {
res *= i;
}
for (int i = 2; i <= k; i++) {
res /= i;
}
return res;
}
Основная сложность при расчетах - это вычисление факториала. Вычисление факториала числа - очень затратная операция, особенно, если у вас задача с расчетом большого кол-во сочетаний из
n по
k. Можно, конечно, кэшировать факториалы, но в формуле производятся и другие математические операции.
Кроме приведенной выше формулы с факториалами существует другой способ нахождения сочетания из
n по
k. Способ заключается в построении треугольника Паскаля, из которого уже берутся готовые значения.
Классический вид треугольника Паскаля:
Как строится треугольник? Треугольник строится построчно сверху вниз. На вершине всегда единица. Каждый элемент в треугольнике получается сложением двух элементом, между которыми и под которыми лежит данный элемент. Причем боковые элементы получаются равными 1.
В программе мы будем хранить треугольник Паскаля в двумерном массиве, поэтому он несколько видоизменится:
Элементы треугольника - это и есть наши искомые кол-ва сочетаний из
n по
k:
Теперь приступим к реализации
Треугольник будем хранить в двумерном массиве
C[][].
Нужно определиться с типом массива, так как числа будут получаться большими, будет переполнение переменных, а вы не заметите.
Приведу таблицу типов и предельных значений, после которых будет переполнение в элементах массива.
| Тип массива | Безопасный предел
|
|---|
| int | при n <= 33
|
| long | при n <= 66
|
| BigInteger | ограничено оперативной памятью
(ниже будет рассмотрено более подробно)
|
Реализация для
int и
long одинаковая, поэтому рассмотрим только
long , а вот для
BigInteger немного отличается.
Реализация с использованием long-массива:
public class PascalTriangle {
private int ubound;
private long C[][];
//инициализация треугольника
public PascalTriangle(int ubound){
if(ubound > 66){
throw new RuntimeException("Data overflow");
}
this.ubound = ubound;
C = new long[ubound+1][ubound+1];
for (int n = 0; n <= ubound; n++) {
//первый и последний элемент в строке равен 1
C[n][0] = C[n][n] = 1;
//далее вычисляем внутреннюю часть
for (int k = 1; k < n; k++) {
C[n][k] = C[n-1][k-1] + C[n-1][k];
}
}
}
//вывод треугольника в консоль
public void show(){
for (int n = 0; n <= ubound; n++) {
for (int k = 0; k <= n; k++) {
System.out.print(C[n][k] + " ");
}
System.out.println();
}
}
//метод, возвращающий кол-во сочетаний из n по k
public long get(int n,int k){
return C[n][k];
}
}
Пример использования:
PascalTriangle pas = new PascalTriangle(66);
//pas.show();
System.out.println(pas.get(5, 3));//результат 10
Теперь рассмотрим случай с
BigInteger.
BigInteger - это прекрасный класс Java по работе с длинными числами. Все числа хранятся внутри класса, а математические операции производятся с помощью методов класса. Например, операция сложения, которую мы применим в коде, производится с помощью метода
add.
public class BigPascalTriangle {
private int ubound;
private BigInteger C[][];
//инициализация треугольника
public BigPascalTriangle(int ubound){
this.ubound = ubound;
C = new BigInteger[ubound+1][ubound+1];
for (int n = 0; n <= ubound; n++) {
//первый и последний элемент в строке равен 1
C[n][0] = C[n][n] = BigInteger.ONE;
//далее вычисляем внутреннюю часть
for (int k = 1; k < n; k++) {
C[n][k] = C[n-1][k-1].add(C[n-1][k]);//аналог C[n][k] = C[n-1][k-1] + C[n-1][k] для длинной арифметики
}
}
}
//вывод треугольника в консоль
public void show(){
for (int n = 0; n <= ubound; n++) {
for (int k = 0; k <= n; k++) {
System.out.print(C[n][k] + " ");
}
System.out.println();
}
}
//метод, возвращающий кол-во сочетаний из n по k
public BigInteger get(int n,int k){
return C[n][k];
}
}
Пример использования:
BigPascalTriangle pas = new BigPascalTriangle(100);
pas.show();
System.out.println(pas.get(5, 3));//результат 10
Теперь о минусах, точнее минусе.
Построение треугольника требует затрат оперативной памяти.
Для массива
long при
n <= 66 - это неощутимо.
Но для реализации с
BigInteger - ощутимо, и при не хватке памяти будет выброшена ошибка:
java.lang.OutOfMemoryError: Java heap space
Ниже я приведу табличку с примерными ограничениями.
Внимание! Данные приведены только с учетом построения треугольника, без учета того, что вы можете хранить в программе еще другие данные. Также данные могут отличаться, т.к. на приграничных значениях программа может то выбрасывать исключение, то не выбрасывать. Время построения треугольника тоже варьируется. Поэтому данные примерные!
| Оперативная память | Допустимое значение | Время построения треугольника
|
|---|
| 256 МБ | n = 1700 | 840 мс
|
| 512 МБ | n = 2150 | 1200 мс
|
| 1024 МБ | n = 2960 | 3700 мс
|
| 2048 МБ | n = 3470 | 7200 мс
|
| 4096 МБ | n = 4340 | 16000 мс
|
p.s. Треугольник Паскаля можно применять для решения и других задач.
В заключении приведу цитату Мартина Гарднера о треугольнике Паскаля:
Треугольник Паскаля так прост, что выписать его сможет даже десятилетний ребенок. В то же время он таит в себе неисчерпаемые сокровища и связывает воедино различные аспекты математики, не имеющие на первый взгляд между собой ничего общего. Столь необычные свойства позволяют считать треугольник Паскаля одной из наиболее изящных схем во всей математике.
Добавить комментарий