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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 20, средняя оценка - 4.95
mr_free
69 / 3 / 0
Регистрация: 08.08.2012
Сообщений: 223
Записей в блоге: 1
#1

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

08.08.2012, 19:55. Просмотров 2560. Ответов 40
Метки нет (Все метки)

Доброго времени суток. Так как я глубоко начинающий программист, столкнулся с проблемой решения задач по комбинаторике (на данный момент формула числа сочитаний). Каким образом можно записать эту формулу на С++, знаю имееться много способов (через рекурсию и т.д.)? Можете, пожалуйста, написать реализацию и объяснить? Вот пример через рекурсию, но никак не пойму принцип работы, объясните? Сама задача вот, на тестах неверный ответ, а на других лимит времени исчерпан, проверил не правильный ответ на нечетных числах и на числе 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 года огромное количество книг, начиная от основ программирования и заканчивая дискретной математикой. А два других учителя, пока никак со мной не связаны из вузов. Вот и не знаю как же мне программистом стать, если никто не может объяснить!), поэтому буду часто спрашивать. Обидно ведь, когда посылают на олимпиаду, а там все задачи на листочке решил (математически), а как написать программу не знаешь
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.08.2012, 19:55
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Комбинаторика! Число сочитаний (C++):

Комбинаторика, вычислить число сочетаний C(N, K) - C++
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...

Комбинаторика.Подсчитать число размещений с повторениями - C++
#pragma hdstop #pragma argsused #include &lt;math.h&gt; #include &lt;tchar.h&gt; #include &lt;iostream.h&gt; #include &lt;conio.h&gt; Long double fact...

Комбинаторика - C++
Доброго всем времени суток!Помогите пожалуйста с решением такой задачи.Дана последовательность вещественных чисел.Пользователь вводит...

Комбинаторика на С++ - C++
Нужно составить программу, или скорее функцию, которая для заданного натурального числа k выводит все возможные произведения k чисел с...

Комбинаторика - C++
От пользователя требуется ввести n. Результат должен быть таким:

комбинаторика - C++
Здравствуйте! Я решаю задачи по дискретной математике на языке С.В интернете масса примеров задач на тему комбинаторики, но на языке...

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

Добавлено через 1 минуту
Цитата Сообщение от I.M. Посмотреть сообщение
Ребят, а каким алгоритмом такие задачи решаются? Где есть сумма или общее кол-во каких-либо объектов, и эти объекты надо распределить по ячейкам. При этом известна максимальная вместительность ячейки.
У меня в голове никак не выстраивается что-то быстрое... неужели нужно искать все возможные распределения и дальше к каждому из них применять формулу перестановок с повторами?
Интересен именно подход, а не код. Но если вам проще кинуть код, то пусть так)
Это простая комбинаторика! Что-то я не понял сути вопроса, можно по-точнее?
0
I.M.
564 / 547 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
20.08.2012, 22:09 #34
Если это простая комбинаторика, то почему же вы до сих пор не решили задачу?
А ведь valeriikozlov уже решил...
0
mr_free
69 / 3 / 0
Регистрация: 08.08.2012
Сообщений: 223
Записей в блоге: 1
20.08.2012, 22:14  [ТС] #35
Ну, хоть с того что я начинающий... А простая как я считаю, по формуле и без дополнительных манипуляций!
И с чего видно что он решил?
0
Thinker
Эксперт C++
4226 / 2200 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
20.08.2012, 22:18 #36
Цитата Сообщение от mr_free Посмотреть сообщение
И с чего видно что он решил?
http://www.e-olimp.com/problems-statistic/65
0
mr_free
69 / 3 / 0
Регистрация: 08.08.2012
Сообщений: 223
Записей в блоге: 1
20.08.2012, 22:39  [ТС] #37
Thinker, ага, значит действительно что-то не так решаю! Простите, если что не так!
Так все же как надо решать?
0
valeriikozlov
Эксперт C++
4670 / 2496 / 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
2
mr_free
69 / 3 / 0
Регистрация: 08.08.2012
Сообщений: 223
Записей в блоге: 1
20.08.2012, 22:59  [ТС] #39
valeriikozlov, спасибо за разложение решения по полочкам, завтра если не получиться отпишусь и спрошу. Ох, теперь меня загрузили, я как раз получил ответ от преподавателя, и вы прям изложили, тоже что написал и он. Спасибо, обдумаю!
0
kravam
быдлокодер
1695 / 882 / 45
Регистрация: 04.06.2008
Сообщений: 5,459
20.08.2012, 23:15 #40
Цитата Сообщение от valeriikozlov Посмотреть сообщение
сколько всего существует вариантов разложения X конфет в Y коробках
mr_free, лови, сам решал когда-то
Дано: X камней, надо разложить эти камни по Y кучкам
0
valeriikozlov
Эксперт C++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
22.08.2012, 04:27 #41
Цитата Сообщение от kravam Посмотреть сообщение
mr_free, лови, сам решал когда-то
Эти способы считают правильно, но не пройдут по времени. Опишу здесь один способ, который подходит для этой задачи (метод динамического программирования). Я приведу пример вычислений в пределах 1..10 конфет, 1..10 ящиков.
Создаем массив a[10][10]. Для удобства индексацию массива буду называть так: нулевой индекс (номер) строки (столбца) буду называть первым индексом (номером), соответственно первый индекс (номер) массива буду называть вторым...
Пусть номер строки будет обозначать количество конфет, а номер столбца будет обозначать количество ящиков. Тогда изначально массив a[][] заполняем так:
Первый столбец заполняем 1. Первую строку заполняем так: 1 2 3 4 .... (значение элемента первой строки равно номеру столбца).
Затем основное заполнение массива:
C++
1
2
3
for(i=2; i<11; i++)// здесь индексация начинается со значения 2 и заканчивается значением 10 (по мною оговоренному условию - что нумерация (индексация) строк и столбцов начинается с 1, а не с 0). Будьте внимательны при реализации кода!!!
    for(j=2; j<11; j++)
        a[i][j]=a[i-1][j]+a[i][j-1];
В итоге получим массив с помощью которого очень быстро можно узнать сколько вариантов размещения X конфет в Y ящиках. Ответом будет являться значение a[X][Y].
Теперь как считать ответ для этой задачи. Рассмотрим (и разберемся) на примере N=6, S=5.
Всего вариантов размещения 6 конфет в 5 ящиках 210 (это значение берем из массива a[][]).
Теперь вычислим сколько из этих вариантов "плохие" (когда в каком-либо ящике больше 3 конфет). Рассмотрим варианты для 1-го ящика:
- В первом ящике все 6 конфет. В остальных 4-х ящиках 0 конфет. Это 1 "плохой" вариант.
- В первом ящике 5 конфет. В остальных 4-х ящиках 1 конфета. Это 4 "плохих" варианта (значение находим в массиве a[1][4]).
- В первом ящике 4 конфеты. В остальных 4-х ящиках 2 конфеты. Это 10 "плохих" варианта (значение находим в массиве a[2][4]).
Итого для первого ящика имеем 15 плохих варианта. Всего ящиков у нас 5. Значит плохих вариантов всего будет 15*5=75.
Ответ на вопрос: сколько вариантов размещения 6 конфет в 5 ящиках: 210-75=135.
Можно подвести итог: для того чтобы посчитать сколько вариантов размещения X конфет в Y ящиках. нужно вычислить:
a[X][Y] - (a[N/2-1][Y-1] + a[N/2-2][Y-1] + ..... + a[1][Y-1] + 1) * S
При реализации такого варианта с помощью массива размером 1000*1000 окажется что памяти не хватает. Но не обязательно заводить этот массив полностью. Я реализовывал решение с помощью массива a[2][1000], т.е. всего две строки (одна для хранения значений предыдущей строки, во второй расчитывал значение очередной строки).
Ну и не забудьте про длинную арифметику.
2
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
22.08.2012, 04:27
Привет! Вот еще темы с ответами:

Комбинаторика - C++
Помогите написать алгоритм для вычисления количество непустых последовательностей из ряда чисел. Или кинте ссылочку, где почитать. Что я...

Комбинаторика - C++
Здравствуйте все. В данный момент дпополнительно решил заняться комбинаторикой, столкнулся с задачей, и никак не могу её решить.Суть...

Перестановка.(Комбинаторика) - C++
Прошу помощи. Объясните пожалуйста тугодуму этот код. Какой день его пытаюсь понять. Не как не могу в нём разобраться. Вроде знаю как...

Комбинаторика в программировании - C++
есть алфавит длинны Х; длинна слова Y; написать код(лучше на с++) который будет составлять и выводить все возможные варианты слов. ...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
22.08.2012, 04:27
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru