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

Комбинаторика! Число сочитаний - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 20, средняя оценка - 4.95
mr_free
 Аватар для mr_free
69 / 3 / 0
Регистрация: 08.08.2012
Сообщений: 223
Записей в блоге: 1
08.08.2012, 19:55     Комбинаторика! Число сочитаний #1
Доброго времени суток. Так как я глубоко начинающий программист, столкнулся с проблемой решения задач по комбинаторике (на данный момент формула числа сочитаний). Каким образом можно записать эту формулу на С++, знаю имееться много способов (через рекурсию и т.д.)? Можете, пожалуйста, написать реализацию и объяснить? Вот пример через рекурсию, но никак не пойму принцип работы, объясните? Сама задача вот, на тестах неверный ответ, а на других лимит времени исчерпан, проверил не правильный ответ на нечетных числах и на числе 2, объясните, пожалуйста, принцип рекурсии здесь, а не просто решите задачу! Пожалуйста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream.h>
#include <stdio.h>
int rec(int n, int k)
{
    if(n==k)
        return 1;
    if(k==1)
        return n;
    return rec(n-1, k-1)+rec(n-1, k);
}
 
int main()
{
    int n, k;
    cin>>n>>k;
    k=n/2;
    cout<<rec(n,k);
 
 
return 0;
}
П.с. Простите что задаю столь глупый вопрос, но увы никто не может мне объснить (поскольку таких просто нет, мой учитель в лицее не имеет желания работать, все приходиться розпрашивать, но почти всегда ответ один: "Ты этого не знаешь иди почитай эту книгу!", я уже прочитал за эти 2 года огромное количество книг, начиная от основ программирования и заканчивая дискретной математикой. А два других учителя, пока никак со мной не связаны из вузов. Вот и не знаю как же мне программистом стать, если никто не может объяснить!), поэтому буду часто спрашивать. Обидно ведь, когда посылают на олимпиаду, а там все задачи на листочке решил (математически), а как написать программу не знаешь
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.08.2012, 19:55     Комбинаторика! Число сочитаний
Посмотрите здесь:

комбинаторика C++
Комбинаторика C++
C++ Комбинаторика на С++
комбинаторика в программировании C++
C++ Комбинаторика
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
-=ЮрА=-
Заблокирован
Автор FAQ
13.08.2012, 16:20     Комбинаторика! Число сочитаний #21
Цитата Сообщение от mr_free Посмотреть сообщение
-=ЮрА=-, также само работает программа, а это я изменял от безвыходности, поскольку не сильно понимаю сокращенные записи!
- я не знаю что ты менял и почему у нас разные отработки, вот ещё раз мой же код под ручной ввод(в котором абсолютно ничего не менял)
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
34
#include <iostream>
using namespace std;
 
double fact(unsigned long n);
double C   (unsigned long n, unsigned long k);
 
int main()
{
    int N = 0;
    int S = 0;
    cout<<"Enter N S : ";;
    if(!(cin>>N>>S))
       cout<<"Error in input\n";
    else
       cout<<"Input  : "<<N<<" "<<S<<endl;
    if(N < S)
       cout<<"Incorrect input params\n";
    else
       cout<<"Output : "<<C(N, S)<<endl;
    return 0;
}
 
double fact(unsigned long n)
{
    double c = (n < 1) ?  1 : n;
    if(1  < (n -= 1))
        c *= fact(n);
    return c;
}
 
double C(unsigned long n, unsigned long k)
{
    return fact(n)/(fact(k)*fact(n - k));
}
Миниатюры
Комбинаторика! Число сочитаний  
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
-=ЮрА=-
Заблокирован
Автор FAQ
13.08.2012, 16:23     Комбинаторика! Число сочитаний #22
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
double fact(unsigned long n)
{
* * double c = (n < 1) ? *1 : n;
* * if(1 *< (n -= 1))
* * * * c *= fact(n);
* * return c;
}
- это расчёт факториала
Это расчёт числа сочетаний
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
return fact(n)/(fact(k)*fact(n - k));
n!/(k!*(n - k)!)
mr_free
 Аватар для mr_free
69 / 3 / 0
Регистрация: 08.08.2012
Сообщений: 223
Записей в блоге: 1
13.08.2012, 16:36  [ТС]     Комбинаторика! Число сочитаний #23
-=ЮрА=-, это я все понял! Единственное что я поменял так это, не ручной ввод и все + подстроился под задачу, в ней вводиться n k( вообще не к чему), я создаю левую переменную s=n/2, как надо по задачи и остальное не трогаю меняю лишь k на s! Наверно что-то не так с s=n/2 и сдесь идет сбой вычисления?
Вот мой код еще раз: (гляньте, пожалуйста)
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
using namespace std;
double fact(unsigned long n);
double C   (unsigned long n, unsigned long s);
int main()
{
    unsigned long n,k;
    cin>>n>>k;
    unsigned long s=n/2;
    cout<<C(n,s);
    return 0;
}
double fact( unsigned long n)
{  double c = (n < 1) ?  1 : n;
    if(1  < (n -= 1))
        c *= fact(n);
    return c;
}
double C (unsigned long n, unsigned long s)
{
    return fact(n)/fact(s)*fact(n-s);
}
-=ЮрА=-
Заблокирован
Автор FAQ
13.08.2012, 16:59     Комбинаторика! Число сочитаний #24
mr_free, ты понимаешь что всегда подставляешь N и S = N/2, смысл вообще ввода переменной k???Уже готовый код привёл готовый код в посте 21, поставим вопрос по другом - что тебя не устаривает в его отработке?

Добавлено через 1 минуту
Цитата Сообщение от mr_free Посмотреть сообщение
cin>>n>>k;
* * unsigned long s=n/2;
cout<<C(n,s);
- вот как у тебя участвует в расчётах k
mr_free
 Аватар для mr_free
69 / 3 / 0
Регистрация: 08.08.2012
Сообщений: 223
Записей в блоге: 1
13.08.2012, 21:15  [ТС]     Комбинаторика! Число сочитаний #25
k в расчетах не участвует, в условие просто дано k, а в дальнейшем при ришение оно не где не используеться!
-=ЮрА=-
Заблокирован
Автор FAQ
14.08.2012, 11:05     Комбинаторика! Число сочитаний #26
Цитата Сообщение от mr_free Посмотреть сообщение
k в расчетах не участвует, в условие просто дано k, а в дальнейшем при ришение оно не где не используеться!
да нет тут ты не прав
Пораскинув ещё раз мозгами пришёл к выводу что число способов равно просто факториалу числа ящиков, а не числу сочетаний
Смотри по примеру в той ссылке 4 шара 3 ящика
Шары 1 2 3 4
Возможные варианты размещений
ящик1 1 4 12 12 1 2
ящик2 23 23 3 4 2 1
ящик3 4 1 4 3 34 34
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
#include <iostream>
using namespace std;
 
double fact(unsigned long n);
 
int main()
{
    int N = 0;
    int S = 0;
    cout<<"Enter N S : ";;
    if(!(cin>>N>>S))
       cout<<"Error in input\n";
    else
       cout<<"Input  : "<<N<<" "<<S<<endl;
    if(N < S)
       cout<<"Incorrect input params\n";
    else
       cout<<"Output : "<<fact(S)<<endl;
    return 0;
}
 
double fact(unsigned long n)
{
    double c = (n < 1) ?  1 : n;
    if(1  < (n -= 1))
        c *= fact(n);
    return c;
}
Миниатюры
Комбинаторика! Число сочитаний  
mr_free
 Аватар для mr_free
69 / 3 / 0
Регистрация: 08.08.2012
Сообщений: 223
Записей в блоге: 1
14.08.2012, 17:49  [ТС]     Комбинаторика! Число сочитаний #27
-=ЮрА=-, только там конфеты и я отправил два ваших варианта решения, но в этих решениях ответ засчитан только один (первый)! Что не так?
-=ЮрА=-
14.08.2012, 17:57
  #28

Не по теме:

Цитата Сообщение от mr_free Посмотреть сообщение
-=ЮрА=-, только там конфеты и я отправил два ваших варианта решения, но в этих решениях ответ засчитан только один (первый)! Что не так?
- ну я бегло тогда условие читанул, конфеты шары, какая разница. Напиши конкретно какие результаты защитаны какие не защитаны...

mr_free
 Аватар для mr_free
69 / 3 / 0
Регистрация: 08.08.2012
Сообщений: 223
Записей в блоге: 1
14.08.2012, 18:06  [ТС]     Комбинаторика! Число сочитаний #29
Из 50 тестов засчитано одно, вывода какой именно тест засчитан нет, наверное, это 4 3!

-=ЮрА=-, Какие есть размышления?
-=ЮрА=-
14.08.2012, 20:45
  #30

Не по теме:

Цитата Сообщение от mr_free Посмотреть сообщение
Из 50 тестов засчитано одно, вывода какой именно тест засчитан нет, наверное, это 4 3!
- http://www.e-olimp.com/problems/65
Пример входных данных
4 3
Пример выходных данных
6
Посмотри на отработку последнего кода!

valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
19.08.2012, 23:53     Комбинаторика! Число сочитаний #31
mr_free, а как можно использовать число сочетаний для решения этой задачи? (или я что-то не понял или Вы ошибаетесь в выборе алгоритма решения)
I.M.
 Аватар для I.M.
564 / 547 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
20.08.2012, 21:28     Комбинаторика! Число сочитаний #32
Ребят, а каким алгоритмом такие задачи решаются? Где есть сумма или общее кол-во каких-либо объектов, и эти объекты надо распределить по ячейкам. При этом известна максимальная вместительность ячейки.
У меня в голове никак не выстраивается что-то быстрое... неужели нужно искать все возможные распределения и дальше к каждому из них применять формулу перестановок с повторами?
Интересен именно подход, а не код. Но если вам проще кинуть код, то пусть так)
mr_free
 Аватар для mr_free
69 / 3 / 0
Регистрация: 08.08.2012
Сообщений: 223
Записей в блоге: 1
20.08.2012, 22:04  [ТС]     Комбинаторика! Число сочитаний #33
Цитата Сообщение от valeriikozlov Посмотреть сообщение
mr_free, а как можно использовать число сочетаний для решения этой задачи? (или я что-то не понял или Вы ошибаетесь в выборе алгоритма решения)
Какие ваши предложения, а то общаясь в теме мы так и не решили поставленую задачу, я предложил число сочетании, а Юра предложил факториал, но оба решения привели только до решения на 10%?
Вопрос о решении данной задачи все еще актуален!

Добавлено через 1 минуту
Цитата Сообщение от I.M. Посмотреть сообщение
Ребят, а каким алгоритмом такие задачи решаются? Где есть сумма или общее кол-во каких-либо объектов, и эти объекты надо распределить по ячейкам. При этом известна максимальная вместительность ячейки.
У меня в голове никак не выстраивается что-то быстрое... неужели нужно искать все возможные распределения и дальше к каждому из них применять формулу перестановок с повторами?
Интересен именно подход, а не код. Но если вам проще кинуть код, то пусть так)
Это простая комбинаторика! Что-то я не понял сути вопроса, можно по-точнее?
I.M.
 Аватар для I.M.
564 / 547 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
20.08.2012, 22:09     Комбинаторика! Число сочитаний #34
Если это простая комбинаторика, то почему же вы до сих пор не решили задачу?
А ведь valeriikozlov уже решил...
mr_free
 Аватар для mr_free
69 / 3 / 0
Регистрация: 08.08.2012
Сообщений: 223
Записей в блоге: 1
20.08.2012, 22:14  [ТС]     Комбинаторика! Число сочитаний #35
Ну, хоть с того что я начинающий... А простая как я считаю, по формуле и без дополнительных манипуляций!
И с чего видно что он решил?
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
20.08.2012, 22:18     Комбинаторика! Число сочитаний #36
Цитата Сообщение от mr_free Посмотреть сообщение
И с чего видно что он решил?
http://www.e-olimp.com/problems-statistic/65
mr_free
 Аватар для mr_free
69 / 3 / 0
Регистрация: 08.08.2012
Сообщений: 223
Записей в блоге: 1
20.08.2012, 22:39  [ТС]     Комбинаторика! Число сочитаний #37
Thinker, ага, значит действительно что-то не так решаю! Простите, если что не так!
Так все же как надо решать?
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
20.08.2012, 22:39     Комбинаторика! Число сочитаний #38
Цитата Сообщение от mr_free Посмотреть сообщение
Какие ваши предложения, а то общаясь в теме мы так и не решили поставленую задачу, я предложил число сочетании, а Юра предложил факториал, но оба решения привели только до решения на 10%?
Задача, о которой идет речь в этой теме, не из простых. Решить ее не получится, используя только факториал (перестановки) или число сочетаний.

mr_free, Вы лучше для начала попробуйте придумать, как можно посчитать: сколько всего существует вариантов разложения X конфет в Y коробках. То есть, два разложения конфет по сундучкам считаются разными, если хотя бы в одном из сундучков количество конфет в первом разложении отличается от количества конфет в другом разложении (в том же сундучке).
Для начала пробуйте высчитать без этих ограничений:
В один сундучок помещается не более чем N/2 конфет.
Например дано:
X=3, Y=5. Ответ: 35.
или X=5, Y=4. Ответ: 56.
Как можно высчитать эти (такие) ответы, быстро, без перебора?
Если найдете нормальный алгоритм, для расчета таких ответов, то следующий шаг будет такой:
Как узнать сколько из всех вариантов разложений для заданных X и Y имеется вариантов, когда в каком-нибудь сундучке (я не ошибся - именно в сундучке, а не в сундучках), количество конфет превышает N/2.
Последний этап будет: подключить длинную арифметику. Пример: N=1000, S=1000, ответ:
1024075813494744857167581251490412522198212443990698516910191318835874093101041877914466497091305103100732383159999011846207740899002262396009023774884630789281506448317160323574255761954463612366367310450535769511062365633127349105235836612770147622256399178723838234258353603921352666499376273387413762968171087623855278513507830150384427415369125221076081108514101607313422650615851177916309826191714311458656219551252264894539940507347680134002564878591554694744148258331599182919206592334557117607816972121503458966972028454329008453788834143300522649201483789837175110034996930311915649035574560
mr_free
 Аватар для mr_free
69 / 3 / 0
Регистрация: 08.08.2012
Сообщений: 223
Записей в блоге: 1
20.08.2012, 22:59  [ТС]     Комбинаторика! Число сочитаний #39
valeriikozlov, спасибо за разложение решения по полочкам, завтра если не получиться отпишусь и спрошу. Ох, теперь меня загрузили, я как раз получил ответ от преподавателя, и вы прям изложили, тоже что написал и он. Спасибо, обдумаю!
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.08.2012, 23:15     Комбинаторика! Число сочитаний
Еще ссылки по теме:

Комбинаторика C++
C++ Комбинаторика. Сочетания
Комбинаторика.Подсчитать число размещений с повторениями C++

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

Или воспользуйтесь поиском по форуму:
kravam
быдлокодер
 Аватар для kravam
1512 / 872 / 44
Регистрация: 04.06.2008
Сообщений: 5,271
20.08.2012, 23:15     Комбинаторика! Число сочитаний #40
Цитата Сообщение от valeriikozlov Посмотреть сообщение
сколько всего существует вариантов разложения X конфет в Y коробках
mr_free, лови, сам решал когда-то
Дано: X камней, надо разложить эти камни по Y кучкам
Yandex
Объявления
20.08.2012, 23:15     Комбинаторика! Число сочитаний
Ответ Создать тему
Опции темы

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