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

Вычисление nCr — формула и примеры кода

• 3 min read • Программирование • Обновлено 17 Dec 2025
Вычисление nCr — формула и примеры кода
Вычисление nCr — формула и примеры кода

Ряд домино с разными комбинациями точек

Что такое комбинация (nCr)

Комбинация — это способ выбрать r объектов из n, когда порядок выбора не важен. Формула:

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

Определения в одну строку:

  • n — общее число элементов.
  • r — число элементов в каждом наборе.
  • ! — факториал: произведение всех целых от 1 до числа (0! = 1).

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

Даны n и r. Нужно вычислить nCr (количество различных комбинаций из r элементов).

Примеры:

  • n = 10, r = 5 → nCr = 252
  • n = 8, r = 0 → nCr = 1

Важное замечание

Важно: вычисление факториалов напрямую быстро приводит к очень большим числам и переполнению целых типов. Для небольших n (например, n ≤ 20 при 64-битных целых) обычный метод с факториалами работает, но для больших n используйте альтернативные подходы (см. раздел “Когда метод факториалов не подходит”).

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

// C++ program to calculate the value of nCr
#include 
using namespace std;

// Function to calculate the factorial of a number
long long factorial(int num) {
    if (num <= 1) {
        return 1;
    }
    return num * factorial(num - 1);
}

// Function to calculate the value of nCr
long long 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

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

# 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))

Вывод:

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

Примечание: в современных версиях Python (3.8+) есть встроенная функция math.comb(n, r), которая безопасна и эффективна для больших n.

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

// 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 + "
");
document.write("Value of nCr: " + calculate_nCr(n1, r1) + "
");

var n2 = 3;
var r2 = 2;
document.write("n: " + n2 + ", r:" + r2 + "
");
document.write("Value of nCr: " + calculate_nCr(n2, r2) + "
");

var n3 = 1;
var r3 = 1;
document.write("n: " + n3 + ", r:" + r3 + "
");
document.write("Value of nCr: " + calculate_nCr(n3, r3) + "
");

var n4 = 8;
var r4 = 0;
document.write("n: " + n4 + ", r:" + r4 + "
");
document.write("Value of nCr: " + calculate_nCr(n4, r4) + "
");

var n5 = 4;
var r5 = 4;
document.write("n: " + n5 + ", r:" + r5 + "
");
document.write("Value of nCr: " + calculate_nCr(n5, r5) + "
");

Вывод в браузере аналогичен предыдущим примерам.

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

// C program to calculate the value of nCr
#include 

// Function to calculate the factorial of a number
long long factorial(int num) {
    if (num <= 1) {
        return 1;
    }
    return num * factorial(num - 1);
}

// Function to calculate the value of nCr
long long 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: %lld \n", calculate_nCr(n1, r1));

    int n2 = 3;
    int r2 = 2;
    printf("n: %d, r: %d \n", n2, r2);
    printf("Value of nCr: %lld \n", calculate_nCr(n2, r2));

    int n3 = 1;
    int r3 = 1;
    printf("n: %d, r: %d \n", n3, r3);
    printf("Value of nCr: %lld \n", calculate_nCr(n3, r3));

    int n4 = 8;
    int r4 = 0;
    printf("n: %d, r: %d \n", n4, r4);
    printf("Value of nCr: %lld \n", calculate_nCr(n4, r4));

    int n5 = 4;
    int r5 = 4;
    printf("n: %d, r: %d \n", n5, r5);
    printf("Value of nCr: %lld \n", calculate_nCr(n5, r5));

    return 0;
}

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

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

// Java program to calculate the value of nCr
public class Main {
    // Function to calculate the factorial of a number
    static long factorial(int num) {
        if (num <= 1) {
            return 1;
        }
        return num * factorial(num - 1);
    }

    // Function to calculate the value of nCr
    static long 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));
    }
}

Вывод аналогичен предыдущим примерам.

Когда метод с факториалами не подходит

  • Переполнение целых типов при больших n.
  • Медленная рекурсивная реализация факториала при больших n (стек).

Альтернативы:

  • Итеративная мультипликативная формула: вычислять результат как произведение (n - r + 1) … n делённое на r!. Это сокращает промежуточные значения.
  • Стандартные библиотеки: math.comb в Python (3.8+), BigInteger в Java для больших чисел, в C++ — boost::multiprecision::cpp_int.
  • Использовать дроби или деление на каждом шаге, чтобы уменьшать числовую нагрузку.

Пример мультипликативного подхода (псевдокод):

result = 1
for i in 1..r:
    result = result * (n - r + i) / i
return result

Это снижает риск переполнения и обычно быстрее.

Мини-чёт: тесты и критерии приёмки

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

  • Функция возвращает целое >= 1 для 0 ≤ r ≤ n.
  • nCr(n, 0) = 1 и nCr(n, n) = 1.
  • Для небольших n совпадает с известными значениями (например, n=10, r=5 → 252).

Тестовые случаи:

  • (n=0, r=0) → 1
  • (n=5, r=0) → 1
  • (n=5, r=5) → 1
  • (n=10, r=1) → 10
  • (n=10, r=5) → 252
  • граничные значения: r > n → ошибку или 0 по соглашению (обработать вход)

Чек-лист для разработчика и QA

Для разработчика:

  • Обработать входы: r < 0, n < 0, r > n.
  • Выбрать тип числа (int64/BigInteger) в зависимости от n.
  • Добавить юнит-тесты для граничных случаев.

Для QA:

  • Проверить корректность для нескольких r при фиксированном n.
  • Замерить время и память при растущем n.
  • Проверить поведение при переполнении.

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

  • Формула nCr = n! / (r! * (n-r)!) — базовая.
  • Для небольших n прямая реализация с факториалом работает.
  • Для больших n используйте мультипликативный подход, math.comb (Python) или большие целые (BigInteger/boost).

Важно: выберите алгоритм в зависимости от ожидаемых входных значений и ограничений по памяти/времени.

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

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

Не появляется экран входа в Windows 10 — решения
Windows

Не появляется экран входа в Windows 10 — решения

Добавить перенос строки в Excel — 3 способа
Excel

Добавить перенос строки в Excel — 3 способа

Стабилизация видео в DaVinci Resolve — полное руководство
Видеомонтаж

Стабилизация видео в DaVinci Resolve — полное руководство

Проверить качество воздуха рядом — быстро и точно
Здоровье

Проверить качество воздуха рядом — быстро и точно

Как сбросить Kindle Fire до заводских настроек
Руководство

Как сбросить Kindle Fire до заводских настроек

Добавить панели настроек в Dock macOS
macOS

Добавить панели настроек в Dock macOS