Комбинаторика, вычислить число сочетаний C(N, K)

@dinbo · Регистрация: 03.11.2016

Студворк — интернет-сервис помощи студентам

When I was in army, sometimes (about once a week) our unit was faced a charming alternative:

most of the hands are to be sent to fields for weeding cabbage and potato;
few people were to be left in charge of the quarters, cleaning, washing, drying etc.
Surely there always were many variants to choose the people for each of two occupations.

So here we have an example of Combinations - different ways of choosing several elements from the given set (not regarding the order). For example, if the boy have 4 candies (of different kinds) and should take only 2 of them, leaving others to his younger sister, he have the following variants:

A B C D - four sorts of candies

A+B, A+C, A+D, B+C, B+D, C+D - six way to choose a pair of them.
How many combinations of K elements from the set of N exist (assuming all N elements are different). It could be easily found that the math formula is:

N!
------------- = C(N, K) - the number of different combinations
K! * (N - K)!
Where X! is the factorial of X, i.e. product 1 * 2 * 3 * ... * X.

Problem statement
You are to calculate exactly this value C(N, K) for given N and K. Note that though some languages (Python and Java for example) have built-in long arithmetics, it would be good if you'll find a way to minimize intermediate results in calculations. It would be crucial for C/C++ sometimes.

If it is too simple for you, please try to write program for Enumerating Combinations task!

Input data will contain the amount of test-cases.
Next lines will contain one test-case each in form of two values (N K).
Answer should contain C(N, K) for each case.

Example:

input data:
3
3 0
4 2
5 2

answer:
1 6 10
пожалуйста решите эту задачу, заранее спасибо) сайт-codeabbey.com 128я задача

@Peoples · 04.11.2016, 10:59

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
#include <vector>
#include <map>
using namespace std;
unsigned int fact(int);
int combination(int, int);
 
int main() {
    int m;
    cin>>m;
    multimap<int,int>ma;
    for(int i=0; i!=m; i++) {
        int l,q;
        cin>>l>>q;
        ma.insert(pair<int,int>(l,q));
    }
    for(multimap<int,int>::iterator iter=ma.begin(); iter!=ma.end(); iter++) {
        cout<<combination(iter->first,iter->second)<<" ";
    }
    return 0;
}
 
int combination(int n, int k) {
    return fact(n)/(fact(k)*fact(n-k));
}
 
unsigned int fact(int x) {
    unsigned int p=1;
    for(int i=1; i<=x; i++) {
        p*=i;
    }
    return p;
}

@dinbo · 04.11.2016, 15:24 **[ТС]**

можете решить без map? я пока не знаюэтот класс

@sourcerer · 04.11.2016, 15:57

Сообщение от dinbo

я пока не знаюэтот класс

Узнайте:

Николаи Джосаттис "Стандартная библиотека C++. Справочное руководство", 2014 год, 2-е издание, глава 7 "Контейнеры STL", подраздел 7.8 "Отображения и мультиотображения", страница 364.

Ну и ещё тут и тут можно глянуть.

@dinbo · 04.11.2016, 16:02 **[ТС]**

а вы не можете решить без этого класса? ну, пожалуйста😭🙄промто в классе мы этого не проходили

@Peoples · 04.11.2016, 16:05

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
using namespace std;
unsigned int fact(int);
int combination(int, int);
 
int main() {
    int m;
    cin>>m;
    int *a=new int[m];
    for(int i=0; i!=m; i++) {
        int l,q;
        cin>>l>>q;
        a[i]=combination(l,q);
    }
    for(int i=0; i!=m; i++) {
        cout<<a[i]<<" ";
    }
    delete[]a;
    return 0;
}
 
int combination(int n, int k) {
    return fact(n)/(fact(k)*fact(n-k));
}
 
unsigned int fact(int x) {
    unsigned int p=1;
    for(int i=1; i<=x; i++) {
        p*=i;
    }
    return p;
}

@dinbo · 04.11.2016, 20:03 **[ТС]**

int *a=new int[m]; зачем это? как можно это по-другому написать?

Добавлено через 29 минут
Peoples, int *a=new int[m]; зачем это, можешь заменить это чем-то простым

@valery7 · 13.05.2018, 11:34

dinbo, это выделение памяти. Чем простым заменить?.. Очень странный вопрос. Если вы изучаете C, то заменить надо будет на malloc.

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .	SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .	SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .	SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .	Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .	SDL3 для Android: Загрузка PNG с альфа-каналом с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .

@dinbo 0 / 0 / 0 Регистрация: 03.11.2016 Сообщений: 18

	Комбинаторика, вычислить число сочетаний C(N, K) 04.11.2016, 10:09. Показов 4783. Ответов 7 Метки нет (Все метки) When I was in army, sometimes (about once a week) our unit was faced a charming alternative: most of the hands are to be sent to fields for weeding cabbage and potato; few people were to be left in charge of the quarters, cleaning, washing, drying etc. Surely there always were many variants to choose the people for each of two occupations. So here we have an example of Combinations - different ways of choosing several elements from the given set (not regarding the order). For example, if the boy have 4 candies (of different kinds) and should take only 2 of them, leaving others to his younger sister, he have the following variants: A B C D - four sorts of candies A+B, A+C, A+D, B+C, B+D, C+D - six way to choose a pair of them. How many combinations of K elements from the set of N exist (assuming all N elements are different). It could be easily found that the math formula is: N! ------------- = C(N, K) - the number of different combinations K! * (N - K)! Where X! is the factorial of X, i.e. product 1 * 2 * 3 * ... * X. Problem statement You are to calculate exactly this value C(N, K) for given N and K. Note that though some languages (Python and Java for example) have built-in long arithmetics, it would be good if you'll find a way to minimize intermediate results in calculations. It would be crucial for C/C++ sometimes. If it is too simple for you, please try to write program for Enumerating Combinations task! Input data will contain the amount of test-cases. Next lines will contain one test-case each in form of two values (N K). Answer should contain C(N, K) for each case. Example: input data: 3 3 0 4 2 5 2 answer: 1 6 10 пожалуйста решите эту задачу, заранее спасибо) сайт-codeabbey.com 128я задача 0

@dinbo 0 / 0 / 0 Регистрация: 03.11.2016 Сообщений: 18
	04.11.2016, 15:24 [ТС]
	можете решить без map? я пока не знаюэтот класс 0

@dinbo 0 / 0 / 0 Регистрация: 03.11.2016 Сообщений: 18
	04.11.2016, 16:02 [ТС]
	а вы не можете решить без этого класса? ну, пожалуйста😭🙄промто в классе мы этого не проходили 0

@dinbo 0 / 0 / 0 Регистрация: 03.11.2016 Сообщений: 18
	04.11.2016, 20:03 [ТС]
	int a=new int[m]; зачем это? как можно это по-другому написать? Добавлено через 29 минут* Peoples, int *a=new int[m]; зачем это, можешь заменить это чем-то простым 0

@valery7 1 / 1 / 1 Регистрация: 11.04.2018 Сообщений: 45
	13.05.2018, 11:34
	dinbo, это выделение памяти. Чем простым заменить?.. Очень странный вопрос. Если вы изучаете C, то заменить надо будет на malloc. 0