Как вычислить nPr — перестановки
Перестановка — это расположение объектов, в котором важен порядок выбора. В этой статье объяснено, как вычислить значение nPr и приведены реализации на Python, C++, JavaScript, C и Java.
Формула и объяснение
Используйте следующую формулу перестановок:
nPr = (n!)/(n-r)!Где:
n = общее количество элементов
P = перестановка
r = число выбираемых элементов
! = факториалКлючевая идея (умственная модель): nPr — это количество упорядоченных выборок длины r без повторений; это эквивалентно перемножению r чисел от n вниз.
Проблема
Даны значения n и r. Нужно вычислить nPr.
Примеры:
- Пример 1: n = 10, r = 5. nPr = 10! / 5! = 30240.
- Пример 2: n = 3, r = 2. nPr = 3! / 1! = 6.
- Пример 3: n = 8, r = 0. nPr = 8! / 8! = 1.
Быстрый способ вручную (мини-метод)
- Если r == 0 → ответ 1.
- Если r > n или r < 0 → некорректные данные (обработать как ошибку).
- Вычислить произведение: n (n-1) … * (n-r+1).
- Использовать целые типы đủ большой ёмкости (long long / BigInteger) или библиотеки для больших чисел.
Важно: не вычисляйте n! и (n-r)! полностью, если n велико — это приводит к переполнению и лишней работе.
Примеры программ (с сохранением исходных реализаций)
C++ Программа для вычисления nPr
// C++ program to calculate the value of nPr
#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 nPr
int calculate_nPr(int n, int r)
{
return factorial(n) / factorial(n - r);
}
int main()
{
int n1 = 10;
int r1 = 5;
cout << "n: " << n1 << ", r: " << r1 << endl;
cout << "Value of nPr: " << calculate_nPr(n1, r1) << endl;
int n2 = 3;
int r2 = 2;
cout << "n: " << n2 << ", r: " << r2 << endl;
cout << "Value of nPr: " << calculate_nPr(n2, r2) << endl;
int n3 = 1;
int r3 = 1;
cout << "n: " << n3 << ", r: " << r3 << endl;
cout << "Value of nPr: " << calculate_nPr(n3, r3) << endl;
int n4 = 8;
int r4 = 0;
cout << "n: " << n4 << ", r: " << r4 << endl;
cout << "Value of nPr: " << calculate_nPr(n4, r4) << endl;
int n5 = 4;
int r5 = 4;
cout << "n: " << n5 << ", r: " << r5 << endl;
cout << "Value of nPr: " << calculate_nPr(n5, r5) << endl;
return 0;
} Вывод:
n: 10, r: 5
Value of nPr: 30240
n: 3, r: 2
Value of nPr: 6
n: 1, r: 1
Value of nPr: 1
n: 8, r: 0
Value of nPr: 1
n: 4, r: 4
Value of nPr: 24Связано: What Is Recursion and How Do You Use It?
Python Программа для вычисления nPr
# Python program to calculate the value of nPr
# 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 nPr
def calculate_nPr(n, r):
return factorial(n) // factorial(n - r)
n1 = 10
r1 = 5
print("n:", n1, ",r:", r1)
print("Value of nPr:", calculate_nPr(n1, r1))
n2 = 3
r2 = 2
print("n:", n2, ",r:", r2)
print("Value of nPr:", calculate_nPr(n2, r2))
n3 = 1
r3 = 1
print("n:", n3, ",r:", r3)
print("Value of nPr:", calculate_nPr(n3, r3))
n4 = 8
r4 = 0
print("n:", n4, ",r:", r4)
print("Value of nPr:", calculate_nPr(n4, r4))
n5 = 4
r5 = 4
print("n:", n5, ",r:", r5)
print("Value of nPr:", calculate_nPr(n5, r5))
Вывод:
n: 10, r: 5
Value of nPr: 30240
n: 3, r: 2
Value of nPr: 6
n: 1, r: 1
Value of nPr: 1
n: 8, r: 0
Value of nPr: 1
n: 4, r: 4
Value of nPr: 24Связано: How to Find All Factors of a Natural Number in C++, Python, and JavaScript
JavaScript Программа для вычисления nPr
// JavaScript program to calculate the value of nPr
// 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 nPr
function calculate_nPr(n, r) {
return factorial(n) / factorial(n - r);
}
var n1 = 10;
var r1 = 5;
document.write("n: " + n1 + ", r:" + r1 + " \n");
document.write("Value of nPr: " + calculate_nPr(n1, r1) + " \n");
var n2 = 3;
var r2 = 2;
document.write("n: " + n2 + ", r:" + r2 + " \n");
document.write("Value of nPr: " + calculate_nPr(n2, r2) + " \n");
var n3 = 1;
var r3 = 1;
document.write("n: " + n3 + ", r:" + r3 + " \n");
document.write("Value of nPr: " + calculate_nPr(n3, r3) + " \n");
var n4 = 8;
var r4 = 0;
document.write("n: " + n4 + ", r:" + r4 + " \n");
document.write("Value of nPr: " + calculate_nPr(n4, r4) + " \n");
var n5 = 4;
var r5 = 4;
document.write("n: " + n5 + ", r:" + r5 + " \n");
document.write("Value of nPr: " + calculate_nPr(n5, r5) + " \n");Вывод:
n: 10, r: 5
Value of nPr: 30240
n: 3, r: 2
Value of nPr: 6
n: 1, r: 1
Value of nPr: 1
n: 8, r: 0
Value of nPr: 1
n: 4, r: 4
Value of nPr: 24C Программа для вычисления nPr
// C program to calculate the value of nPr
#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 nPr
int calculate_nPr(int n, int r)
{
return factorial(n) / factorial(n - r);
}
int main()
{
int n1 = 10;
int r1 = 5;
printf("n: %d, r: %d \n", n1, r1);
printf("Value of nPr: %d \n", calculate_nPr(n1, r1));
int n2 = 3;
int r2 = 2;
printf("n: %d, r: %d \n", n2, r2);
printf("Value of nPr: %d \n", calculate_nPr(n2, r2));
int n3 = 1;
int r3 = 1;
printf("n: %d, r: %d \n", n3, r3);
printf("Value of nPr: %d \n", calculate_nPr(n3, r3));
int n4 = 8;
int r4 = 0;
printf("n: %d, r: %d \n", n4, r4);
printf("Value of nPr: %d \n", calculate_nPr(n4, r4));
int n5 = 4;
int r5 = 4;
printf("n: %d, r: %d \n", n5, r5);
printf("Value of nPr: %d \n", calculate_nPr(n5, r5));
return 0;
} Вывод:
n: 10, r: 5
Value of nPr: 30240
n: 3, r: 2
Value of nPr: 6
n: 1, r: 1
Value of nPr: 1
n: 8, r: 0
Value of nPr: 1
n: 4, r: 4
Value of nPr: 24Java Программа для вычисления nPr
// Java program to calculate the value of nPr
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 nPr
static int calculate_nPr(int n, int r) {
return factorial(n) / 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 nPr: " + calculate_nPr(n1, r1));
int n2 = 3;
int r2 = 2;
System.out.println("n: " + n2 + ", r: " + r2);
System.out.println("Value of nPr: " + calculate_nPr(n2, r2));
int n3 = 1;
int r3 = 1;
System.out.println("n: " + n3 + ", r: " + r3);
System.out.println("Value of nPr: " + calculate_nPr(n3, r3));
int n4 = 8;
int r4 = 0;
System.out.println("n: " + n4 + ", r: " + r4);
System.out.println("Value of nPr: " + calculate_nPr(n4, r4));
int n5 = 4;
int r5 = 4;
System.out.println("n: " + n5 + ", r: " + r5);
System.out.println("Value of nPr: " + calculate_nPr(n5, r5));
}
}Вывод:
n: 10, r: 5
Value of nPr: 30240
n: 3, r: 2
Value of nPr: 6
n: 1, r: 1
Value of nPr: 1
n: 8, r: 0
Value of nPr: 1
n: 4, r: 4
Value of nPr: 24Когда подход с факториалом не годится (кратко)
- Большие n приводят к переполнению стандартных типов (int, long).
- Рекурсивный factorial может переполнить стек при больших n.
- Если r > n или r < 0 — результат некорректен.
- Для вещественных аргументов используйте функции гамма, но это уже другая задача.
Альтернативные подходы
- Итеративное произведение: compute = 1; for i from 0 to r-1: compute *= (n - i). Это экономит память и время по сравнению с вычислением полных факториалов.
- Использовать BigInteger / bigints для точности при больших значениях.
- В статистике/комбинаторике иногда применяют логарифмы факториалов для работы с очень большими числами.
Практические рекомендации для разработчика и студента
Checklist (студент):
- Пойми формулу nPr и реализуй её итеративно.
- Обработай случаи r = 0, r > n, отрицательные r.
- Пойми сложность O(r).
Checklist (разработчик):
- Используй 64-bit или BigInteger, если n и r могут быть большими.
- Предпочитай итеративный или стримовый метод для экономии операций.
- Добавь тесты на граничные случаи.
Факты и оценки (факт-бокс)
- Сложность по времени: O(r) при итеративном методе.
- Сложность по памяти: O(1) (итеративно).
- nPr = 1, если r = 0 или r = n = 0 по соглашению (в зависимости от контекста).
- Переполнение — основной практический риск.
Принцип решения (SOP)
- Проверить входы: целые, 0 ≤ r ≤ n.
- Если r == 0 → вернуть 1.
- Итерировать i от 0 до r-1 и умножать результат на (n-i).
- Вернуть результат (используя подходящий тип данных).
Краткий глоссарий
- nPr: число перестановок n по r — упорядоченные выборки без повторений.
- Факториал (n!): произведение всех натуральных чис от 1 до n.
Решение наглядно: дерево решения (Mermaid)
flowchart TD
A[Есть n и r?] --> B{r < 0 или r > n?}
B -- Да --> C[Ошибка: некорректные входные данные]
B -- Нет --> D{r == 0}
D -- Да --> E[Вернуть 1]
D -- Нет --> F[Вычислить произведение n*'n-1'*...*'n-r+1']
F --> G[Вернуть результат]Краткое резюме
- nPr = n! / (n-r)! — базовая формула; на практике удобнее вычислять как произведение r множителей.
- Для корректности и производительности избегайте вычисления полных факториалов и учитывайте переполнение.
- Используйте bigint/BigInteger при больших n.
Связано: What Is a Fibonacci Sequence and How Do You Print One in Python, C++, and JavaScript?
Немного о том, как программирование влияет на мозг
Подобно творчеству, программирование влияет на мозг: улучшает способность к решению задач и структурированному мышлению. Это не прямая инструкция по вычислению nPr, но полезный побочный эффект изучения алгоритмов.
Автор
Редакция
Похожие материалы
Почта
Пересылка почты Outlook ↔ Gmail: полное руководство
Гаджеты
Как узнать, что пора менять батарейку AirTag
Умный дом
Как удалить устройства из Google Home
Windows
Вернуть «Open command window here» в Windows 11
Гаджеты
Подключение Bluetooth-наушников к Wear OS
Монетизация