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

@mr_free · Регистрация: 08.08.2012

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

Доброго времени суток. Так как я глубоко начинающий программист, столкнулся с проблемой решения задач по комбинаторике (на данный момент формула числа сочитаний). Каким образом можно записать эту формулу на С++, знаю имееться много способов (через рекурсию и т.д.)? Можете, пожалуйста, написать реализацию и объяснить? Вот пример через рекурсию, но никак не пойму принцип работы, объясните? Сама задача вот, на тестах неверный ответ, а на других лимит времени исчерпан, проверил не правильный ответ на нечетных числах и на числе 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 года огромное количество книг, начиная от основ программирования и заканчивая дискретной математикой. А два других учителя, пока никак со мной не связаны из вузов. Вот и не знаю как же мне программистом стать, если никто не может объяснить!

), поэтому буду часто спрашивать. Обидно ведь, когда посылают на олимпиаду, а там все задачи на листочке решил (математически), а как написать программу не знаешь

valeriikozlov · 22.08.2012, 04:27

Сообщение от 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], т.е. всего две строки (одна для хранения значений предыдущей строки, во второй расчитывал значение очередной строки).
Ну и не забудьте про длинную арифметику.

Новые блоги и статьи Все статьи Все блоги /
Запустил конкурс "тем и промптов для текстовых квестов созданных почти чисто ИИ" Adler 06.10.2026 Всем привет! За последние три-четыре дня я создал более 16 текстовых квестовых игр используя преимущественно по одному запросу к ИИ на игру. Мне так понравилось смотреть все ветки/ сцены во всех. . .	ИИ не может найти нужный язык в списке Supersumestria 05.10.2026 Я ему даю вот такое изображение и прошу найти и подчеркнуть немецкий язык. Возвращает он вот это: https:/ / i. **********/ vqBWLe2. png Нужную строчку в 3й колонке просто выдумал. . Это. . .	Новая последняя моя музыка в SUNO zorxor 05.10.2026 Здравствуйте, дорогие мои друзья! С большой радостью я хотел бы представить вам свою новую последнею музыку, которую сгенерировала мне по моей просьбе нейросеть SUNO. С уважением, zorxor. Это. . .	Программный домашний кинотеатр russiannick 27.09.2026 Сподобился на программный домашний кинотеатр. В качестве ЯВУ по традиции выбрал js. В помощники взял Яндекс-Алису. Было создано три зала на разные интересы. исторические и ретро сериал Хичкок. . .
Беседа с ИИ о программистах, недопускающих к созданию и правке кода генеративные ИИ и причины этого zorxor 21.09.2026 Раньше я радовался или получал некоторые эмоции, пусть небольшие, но всё же, от самого процесса написания кода, рекомпиляции и запуска, видя постепенное развитие программы и прочее. А теперь лень. . .	Мобильное приложение ColorStep pavlinmavlin 17.09.2026 Реализовал приложение Красный, Зеленый, Синий в Unity3d + c#. Название изменил на ColorStep. Приложение прошло модерацию и теперь доступно для скачивания. Делал его сам, шаг за шагом — и вот,. . .	Запрет дублирования строк в табличной части Maks 13.09.2026 Реализация из решения ниже выполнена на нетиповом справочнике "Нормы ТО" с табличной часть "Виды ТО", разработанного в КА2, со следующими реквизитами: - ВидТО (СправочникСсылка. ВидыТО); - ВидГСМ. . .	Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Jin X 06.09.2026 Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Работая с форумом и нейросетями в браузере часто хочется что-то подкорректировать или добавить какого-то функционала. Ниже прикреплён. . .