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

Как вычислить сочетания 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
Автор
Редакция

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

RDP: полный гид по настройке и безопасности
Инфраструктура

RDP: полный гид по настройке и безопасности

Android как клавиатура и трекпад для Windows
Гайды

Android как клавиатура и трекпад для Windows

Советы и приёмы для работы с PDF
Документы

Советы и приёмы для работы с PDF

Calibration в Lightroom Classic: как и когда использовать
Фото

Calibration в Lightroom Classic: как и когда использовать

Отключить Siri Suggestions на iPhone
iOS

Отключить Siri Suggestions на iPhone

Рисование таблиц в Microsoft Word — руководство
Office

Рисование таблиц в Microsoft Word — руководство