Гид по технологиям

Как вычислить сочетания nCr (C(n, r)) — примеры на Python, C++, JavaScript, C и Java

• 4 min read • Алгоритмы • Обновлено 05 Jan 2026
nCr: вычисление сочетаний в Python, C++, JS, C и Java
nCr: вычисление сочетаний в Python, C++, JS, C и Java

Несколько доминошек, показывающих разные комбинации точек

Сочетание — математическая концепция, описывающая выбор нескольких объектов, в котором их порядок не важен. Базовая формула даёт число действительных сочетаний.

В этой статье вы научитесь вычислять nCr на Python, C++, JavaScript, C и Java. В каждом примере приведён пример вывода для нескольких значений.

Как вычислить nCr

Используйте следующую формулу сочетаний:

nCr = n! / (r! * (n-r)!)

Где:

n = общее количество
C = сочетание
r = количество выбираемых элементов
! = факториал

Условие задачи

Даны значения n и r. Нужно вычислить nCr.

Пример 1: n = 10, r = 5 => nCr = 10! / (5! * 5!) = 252.

Пример 2: n = 8, r = 0 => nCr = 1.

C++ программа для вычисления nCr

Ниже — C++ программа, вычисляющая значение nCr (оригинальный код сохранён):

// C++ program to calculate the value of nCr  
#include   
using namespace std;  
  
// Function to calculate the factorial of a number  
int factorial(int num)  
{  
    if (num<=1)  
    {  
        return 1;  
    }  
    return num*factorial(num-1);  
}  
  
// Function to calculate the value of nCr  
int calculate_nCr(int n, int r)  
{  
    return factorial(n) / (factorial(r) * factorial(n - r));  
}  
  
  
int main()  
{  
    int n1 = 10;  
    int r1 = 5;  
    cout << "n: " << n1 << ", r: " << r1 << endl;  
    cout << "Value of nCr: " << calculate_nCr(n1, r1) << endl;  
  
    int n2 = 3;  
    int r2 = 2;  
    cout << "n: " << n2 << ", r: " << r2 << endl;  
    cout << "Value of nCr: " << calculate_nCr(n2, r2) << endl;  
  
    int n3 = 1;  
    int r3 = 1;  
    cout << "n: " << n3 << ", r: " << r3 << endl;  
    cout << "Value of nCr: " << calculate_nCr(n3, r3) << endl;  
  
    int n4 = 8;  
    int r4 = 0;  
    cout << "n: " << n4 << ", r: " << r4 << endl;  
    cout << "Value of nCr: " << calculate_nCr(n4, r4) << endl;  
  
    int n5 = 4;  
    int r5 = 4;  
    cout << "n: " << n5 << ", r: " << r5 << endl;  
    cout << "Value of nCr: " << calculate_nCr(n5, r5) << endl;  
  
    return 0;  
}

Вывод:

n: 10, r: 5  
Value of nCr: 252  
n: 3, r: 2  
Value of nCr: 3  
n: 1, r: 1  
Value of nCr: 1  
n: 8, r: 0  
Value of nCr: 1  
n: 4, r: 4  
Value of nCr: 1

Важно: рекурсивный факториал прост для понимания, но быстро приводит к переполнению и глубокой рекурсии при больших n. Ниже — альтернативы.

Python программа для вычисления nCr

Python-реализация (оригинальный код сохранён):

# Python program to calculate the value of nCr  
  
# Function to calculate the factorial of a number  
def factorial(num):  
    if num<=1:  
        return 1  
    return num*factorial(num-1)  
  
# Function to calculate the value of nCr  
def calculate_nCr(n, r):  
    return factorial(n) // (factorial(r) * factorial(n - r))  
  
n1 = 10  
r1 = 5  
print("n:", n1, ",r:", r1)  
print("Value of nCr:", calculate_nCr(n1, r1))  
  
n2 = 3  
r2 = 2  
print("n:", n2, ",r:", r2)  
print("Value of nCr:", calculate_nCr(n2, r2))  
  
n3 = 1  
r3 = 1  
print("n:", n3, ",r:", r3)  
print("Value of nCr:", calculate_nCr(n3, r3))  
  
n4 = 8  
r4 = 0  
print("n:", n4, ",r:", r4)  
print("Value of nCr:", calculate_nCr(n4, r4))  
  
n5 = 4  
r5 = 4  
print("n:", n5, ",r:", r5)  
print("Value of nCr:", calculate_nCr(n5, r5))

Вывод (тот же, что и в примерах выше).

Совет: в Python 3.8+ есть встроенная функция math.comb(n, r), которая корректно обрабатывает большие n и эффективнее рекурсивного факториала.

JavaScript программа для вычисления nCr

JavaScript-реализация (оригинальный код сохранён):

// JavaScript program to calculate the value of nCr  
  
// Function to calculate the factorial of a number  
function factorial(num) {  
    if (num<=1) {  
        return 1;  
    }  
    return num*factorial(num-1);  
}  
  
// Function to calculate the value of nCr  
function calculate_nCr(n, r) {  
    return factorial(n) / (factorial(r) * factorial(n - r));  
}  
  
var n1 = 10;  
var r1 = 5;  
document.write("n: " + n1 + ", r:" + r1 + "  \n");  
document.write("Value of nCr: " + calculate_nCr(n1, r1) + "  \n");  
  
var n2 = 3;  
var r2 = 2;  
document.write("n: " + n2 + ", r:" + r2 + "  \n");  
document.write("Value of nCr: " + calculate_nCr(n2, r2) + "  \n");  
  
var n3 = 1;  
var r3 = 1;  
document.write("n: " + n3 + ", r:" + r3 + "  \n");  
document.write("Value of nCr: " + calculate_nCr(n3, r3) + "  \n");  
  
var n4 = 8;  
var r4 = 0;  
document.write("n: " + n4 + ", r:" + r4 + "  \n");  
document.write("Value of nCr: " + calculate_nCr(n4, r4) + "  \n");  
  
var n5 = 4;  
var r5 = 4;  
document.write("n: " + n5 + ", r:" + r5 + "  \n");  
document.write("Value of nCr: " + calculate_nCr(n5, r5) + "  \n");

Вывод совпадает с примерами выше.

Примечание: для очень больших n используйте BigInt и итеративную формулу (см. раздел «Альтернативные подходы»).

C программа для вычисления nCr

C-реализация (оригинальный код сохранён):

// C program to calculate the value of nCr  
#include   
  
// Function to calculate the factorial of a number  
int factorial(int num)  
{  
    if (num<=1)  
    {  
        return 1;  
    }  
    return num*factorial(num-1);  
}  
  
// Function to calculate the value of nCr  
int calculate_nCr(int n, int r)  
{  
    return factorial(n) / (factorial(r) * factorial(n - r));  
}  
  
  
int main()  
{  
    int n1 = 10;  
    int r1 = 5;  
    printf("n: %d, r: %d \n", n1, r1);  
    printf("Value of nCr: %d \n", calculate_nCr(n1, r1));  
  
    int n2 = 3;  
    int r2 = 2;  
    printf("n: %d, r: %d \n", n2, r2);  
    printf("Value of nCr: %d \n", calculate_nCr(n2, r2));  
  
    int n3 = 1;  
    int r3 = 1;  
    printf("n: %d, r: %d \n", n3, r3);  
    printf("Value of nCr: %d \n", calculate_nCr(n3, r3));  
  
    int n4 = 8;  
    int r4 = 0;  
    printf("n: %d, r: %d \n", n4, r4);  
    printf("Value of nCr: %d \n", calculate_nCr(n4, r4));  
  
    int n5 = 4;  
    int r5 = 4;  
    printf("n: %d, r: %d \n", n5, r5);  
    printf("Value of nCr: %d \n", calculate_nCr(n5, r5));  
  
    return 0;  
}

Java программа для вычисления nCr

Java-реализация (оригинальный код сохранён):

// Java program to calculate the value of nCr  
public class Main  
{  
    // Function to calculate the factorial of a number  
    static int factorial(int num) {  
        if (num <= 1) {  
            return 1;  
        }  
        return num * factorial(num - 1);  
    }  
  
    // Function to calculate the value of nCr  
    static int calculate_nCr(int n, int r) {  
        return factorial(n) / (factorial(r) * factorial(n - r));  
    }  
    public static void main(String[] args) {  
  
        int n1 = 10;  
        int r1 = 5;  
        System.out.println("n: " + n1 + ", r: " + r1);  
        System.out.println("Value of nCr: " + calculate_nCr(n1, r1));  
  
        int n2 = 3;  
        int r2 = 2;  
        System.out.println("n: " + n2 + ", r: " + r2);  
        System.out.println("Value of nCr: " + calculate_nCr(n2, r2));  
  
        int n3 = 1;  
        int r3 = 1;  
        System.out.println("n: " + n3 + ", r: " + r3);  
        System.out.println("Value of nCr: " + calculate_nCr(n3, r3));  
  
        int n4 = 8;  
        int r4 = 0;  
        System.out.println("n: " + n4 + ", r: " + r4);  
        System.out.println("Value of nCr: " + calculate_nCr(n4, r4));  
  
        int n5 = 4;  
        int r5 = 4;  
        System.out.println("n: " + n5 + ", r: " + r5);  
        System.out.println("Value of nCr: " + calculate_nCr(n5, r5));  
    }  
}

Вывод для всех приведённых примеров одинаков: 252, 3, 1, 1, 1 соответственно.

Альтернативные подходы и когда их использовать

  • Итеративная (мультипликативная) формула. Надёжнее, чем вычислять факториалы полностью:
result = 1
for i in 1..r:
    result = result * (n - r + i) / i

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

  • Паскалева треугольник (динамическое программирование): полезен, когда нужно вычислить множество nCr для разных r при фиксированном n.

  • Библиотеки больших чисел: Python math.comb (Python 3.8+), Java BigInteger (для больших значений), Boost.Multiprecision в C++, GMP для C, BigInt в JavaScript.

  • Числа с плавающей точкой (double): использовать осторожно — потеря точности для больших значений.

Ментальные модели и эвристики

  • nCr симметрично: C(n, r) = C(n, n-r). Поэтому всегда выбирайте r = min(r, n-r) для оптимизации.
  • Малые r: мультипликативная формула выполняется быстро и безопасно.
  • Много запросов на небольшие n: предвычислите Паскалев треугольник.

Пограничные случаи и ошибки

  • r < 0 или r > n — обычно nCr считается равным 0 (или это ошибка ввода).
  • n или r нецелые — комбинации определяются для целых; для нецелых нужна другая теория.
  • Переполнение при факториалах: факториал быстро выходит за пределы 32/64 бит.

Критерии приёмки

  1. Для тестов (n=10,r=5), (3,2), (1,1), (8,0), (4,4) программа должна выводить 252, 3, 1, 1, 1.
  2. Для n до 60 и 64-битных целых результат должен быть корректным при использовании unsigned long long (при аккуратной реализации).
  3. Для очень больших n использовать BigInteger/библиотеки произвольной точности и/или math.comb.

Быстрое руководство по выбору метода (практический чеклист)

  • Нужны единичные вычисления, n <= 20: можно использовать рекурсивный факториал.
  • n большое, но r маленькое: мультипликативная формула + уменьшение r до min(r, n-r).
  • Много запросов для одного n: строить Паскалев треугольник.
  • Очень большие значения: использовать библиотеки больших чисел (BigInteger, Boost.Multiprecision, GMP).

Пример потокового принятия решения (Mermaid)

flowchart TD
  A[Нужно вычислить nCr?] --> B{r < 0 или r > n}
  B -- Да --> C[Вернуть 0 или ошибку]
  B -- Нет --> D{r == 0 или r == n}
  D -- Да --> E[Вернуть 1]
  D -- Нет --> F{n маленький и нет требований по точности}
  F -- Да --> G[Рекурсивный факториал OK]
  F -- Нет --> H{r маленькое}
  H -- Да --> I[Мультипликативная формула]
  H -- Нет --> J{Много запросов по одному n}
  J -- Да --> K[Паскаль]
  J -- Нет --> L[Использовать библиотеки больших чисел]

Быстрые советы по языкам

  • Python: используйте math.comb(n, r) (Python 3.8+) для корректности и производительности.
  • Java: для больших значений используйте BigInteger и последовательный продукт с делением.
  • C++: для больших значений применяйте boost::multiprecision::cpp_int или реализуйте мультипликативную формулу с проверкой переполнения.
  • JavaScript: при больших значениях используйте BigInt и аккуратно делите, чтобы избежать дробной арифметики.
  • C: используйте GMP или другие сторонние библиотеки для произвольной точности.

Краткое резюме

  • Формула nCr = n! / (r! * (n-r)!) — корректна, но вычисление факториалов напрямую не всегда практично.
  • Для надёжности используйте мультипликативную формулу, оптимизацию r -> min(r, n-r), или стандартные библиотеки (math.comb, BigInteger, Boost, GMP).
  • Тесты и критерии приёмки помогают проверить корректность на граничных случаях.

Важно: выбирайте метод исходя из диапазона n, требований к производительности и наличия библиотек для больших чисел.

Поделиться: X/Twitter Facebook LinkedIn Telegram
Автор
Редакция

Похожие материалы

Пересылка почты Outlook ↔ Gmail: полное руководство
Почта

Пересылка почты Outlook ↔ Gmail: полное руководство

Как узнать, что пора менять батарейку AirTag
Гаджеты

Как узнать, что пора менять батарейку AirTag

Как удалить устройства из Google Home
Умный дом

Как удалить устройства из Google Home

Вернуть «Open command window here» в Windows 11
Windows

Вернуть «Open command window here» в Windows 11

Подключение Bluetooth-наушников к Wear OS
Гаджеты

Подключение Bluetooth-наушников к Wear OS

Запустить успешную страницу на Patreon
Монетизация

Запустить успешную страницу на Patreon