Форум программистов, компьютерный форум CyberForum.ru

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

Восстановить пароль Регистрация
 
dinbo
0 / 0 / 0
Регистрация: 03.11.2016
Сообщений: 18
04.11.2016, 10:09     Комбинаторика, вычислить число сочетаний C(N, K) #1
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я задача
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
04.11.2016, 10:09     Комбинаторика, вычислить число сочетаний C(N, K)
Посмотрите здесь:

Вычислить количество сочетаний по формуле C++
C++ Число сочетаний
Комбинаторика! Число сочитаний C++
найти число сочетаний из n элементов по m C++
Комбинаторика, перебор всех сочетаний C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Peoples
714 / 374 / 339
Регистрация: 06.02.2016
Сообщений: 986
Записей в блоге: 10
Завершенные тесты: 3
04.11.2016, 10:59     Комбинаторика, вычислить число сочетаний C(N, K) #2
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
0 / 0 / 0
Регистрация: 03.11.2016
Сообщений: 18
04.11.2016, 15:24  [ТС]     Комбинаторика, вычислить число сочетаний C(N, K) #3
можете решить без map? я пока не знаюэтот класс
gru74ik
Модератор
 Аватар для gru74ik
2999 / 1312 / 164
Регистрация: 20.02.2013
Сообщений: 3,740
Записей в блоге: 15
04.11.2016, 15:57     Комбинаторика, вычислить число сочетаний C(N, K) #4
Цитата Сообщение от dinbo Посмотреть сообщение
я пока не знаюэтот класс
Узнайте:

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


Ну и ещё тут и тут можно глянуть.
dinbo
0 / 0 / 0
Регистрация: 03.11.2016
Сообщений: 18
04.11.2016, 16:02  [ТС]     Комбинаторика, вычислить число сочетаний C(N, K) #5
а вы не можете решить без этого класса? ну, пожалуйста😭🙄промто в классе мы этого не проходили
Peoples
714 / 374 / 339
Регистрация: 06.02.2016
Сообщений: 986
Записей в блоге: 10
Завершенные тесты: 3
04.11.2016, 16:05     Комбинаторика, вычислить число сочетаний C(N, K) #6
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;
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
04.11.2016, 20:03     Комбинаторика, вычислить число сочетаний C(N, K)
Еще ссылки по теме:

Число сочетаний из n по k C++
C++ Вычислить число сочетаний из n по m
Комбинаторика.Подсчитать число размещений с повторениями C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
dinbo
0 / 0 / 0
Регистрация: 03.11.2016
Сообщений: 18
04.11.2016, 20:03  [ТС]     Комбинаторика, вычислить число сочетаний C(N, K) #7
int *a=new int[m]; зачем это? как можно это по-другому написать?

Добавлено через 29 минут
Peoples, int *a=new int[m]; зачем это, можешь заменить это чем-то простым
Yandex
Объявления
04.11.2016, 20:03     Комбинаторика, вычислить число сочетаний C(N, K)
Ответ Создать тему
Опции темы

Текущее время: 07:43. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru