|
|
||||||
Комбинаторика! Число сочитаний08.08.2012, 19:55. Показов 5906. Ответов 40
Метки нет (Все метки)
Доброго времени суток. Так как я глубоко начинающий программист, столкнулся с проблемой решения задач по комбинаторике (на данный момент формула числа сочитаний). Каким образом можно записать эту формулу на С++, знаю имееться много способов (через рекурсию и т.д.)? Можете, пожалуйста, написать реализацию и объяснить? Вот пример через рекурсию, но никак не пойму принцип работы, объясните? Сама задача вот, на тестах неверный ответ, а на других лимит времени исчерпан, проверил не правильный ответ на нечетных числах и на числе 2, объясните, пожалуйста, принцип рекурсии здесь, а не просто решите задачу! Пожалуйста
![]()
), поэтому буду часто спрашивать. Обидно ведь, когда посылают на олимпиаду, а там все задачи на листочке решил (математически), а как написать программу не знаешь
0
|
||||||
| 08.08.2012, 19:55 | |
|
Ответы с готовыми решениями:
40
Комбинаторика, вычислить число сочетаний C(N, K) Комбинаторика.Подсчитать число размещений с повторениями Нажатие сочитаний клавиш |
|
|
|||||||
| 13.08.2012, 16:20 | |||||||
, вот ещё раз мой же код под ручной ввод(в котором абсолютно ничего не менял)
0
|
|||||||
|
|
||||||
| 13.08.2012, 16:36 [ТС] | ||||||
|
-=ЮрА=-, это я все понял! Единственное что я поменял так это, не ручной ввод и все + подстроился под задачу, в ней вводиться n k( вообще не к чему), я создаю левую переменную s=n/2, как надо по задачи и остальное не трогаю меняю лишь k на s! Наверно что-то не так с s=n/2 и сдесь идет сбой вычисления?
Вот мой код еще раз: (гляньте, пожалуйста)
0
|
||||||
|
|
||
| 13.08.2012, 16:59 | ||
|
mr_free, ты понимаешь что всегда подставляешь N и S = N/2, смысл вообще ввода переменной k???Уже готовый код привёл готовый код в посте 21, поставим вопрос по другом - что тебя не устаривает в его отработке?
Добавлено через 1 минуту
0
|
||
|
|
||||||||||
| 14.08.2012, 11:05 | ||||||||||
|
Пораскинув ещё раз мозгами пришёл к выводу что число способов равно просто факториалу числа ящиков, а не числу сочетаний Смотри по примеру в той ссылке 4 шара 3 ящика Шары 1 2 3 4 Возможные варианты размещений
0
|
||||||||||
| 14.08.2012, 17:57 | |
|
0
|
|
| 14.08.2012, 20:45 | ||||||
|
Не по теме:
0
|
||||||
|
4728 / 2549 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
|
| 19.08.2012, 23:53 | |
|
mr_free, а как можно использовать число сочетаний для решения этой задачи? (или я что-то не понял или Вы ошибаетесь в выборе алгоритма решения)
0
|
|
|
576 / 559 / 47
Регистрация: 16.12.2011
Сообщений: 1,389
|
|
| 20.08.2012, 21:28 | |
|
Ребят, а каким алгоритмом такие задачи решаются? Где есть сумма или общее кол-во каких-либо объектов, и эти объекты надо распределить по ячейкам. При этом известна максимальная вместительность ячейки.
У меня в голове никак не выстраивается что-то быстрое... неужели нужно искать все возможные распределения и дальше к каждому из них применять формулу перестановок с повторами? Интересен именно подход, а не код. Но если вам проще кинуть код, то пусть так)
0
|
|
|
|
|||
| 20.08.2012, 22:04 [ТС] | |||
|
Вопрос о решении данной задачи все еще актуален! Добавлено через 1 минуту
0
|
|||
|
576 / 559 / 47
Регистрация: 16.12.2011
Сообщений: 1,389
|
|
| 20.08.2012, 22:09 | |
|
Если это простая комбинаторика, то почему же вы до сих пор не решили задачу?
А ведь valeriikozlov уже решил...
0
|
|
|
|
|
| 20.08.2012, 22:18 | |
|
0
|
|
|
4728 / 2549 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
|||
| 20.08.2012, 22:39 | |||
|
mr_free, Вы лучше для начала попробуйте придумать, как можно посчитать: сколько всего существует вариантов разложения X конфет в Y коробках. То есть, два разложения конфет по сундучкам считаются разными, если хотя бы в одном из сундучков количество конфет в первом разложении отличается от количества конфет в другом разложении (в том же сундучке). Для начала пробуйте высчитать без этих ограничений:
X=3, Y=5. Ответ: 35. или X=5, Y=4. Ответ: 56. Как можно высчитать эти (такие) ответы, быстро, без перебора? Если найдете нормальный алгоритм, для расчета таких ответов, то следующий шаг будет такой: Как узнать сколько из всех вариантов разложений для заданных X и Y имеется вариантов, когда в каком-нибудь сундучке (я не ошибся - именно в сундучке, а не в сундучках), количество конфет превышает N/2. Последний этап будет: подключить длинную арифметику. Пример: N=1000, S=1000, ответ: 1024075813494744857167581251490412522198 2124439906985169101913188358740931010418 7791446649709130510310073238315999901184 6207740899002262396009023774884630789281 5064483171603235742557619544636123663673 1045053576951106236563312734910523583661 2770147622256399178723838234258353603921 3526664993762733874137629681710876238552 7851350783015038442741536912522107608110 8514101607313422650615851177916309826191 7143114586562195512522648945399405073476 8013400256487859155469474414825833159918 2919206592334557117607816972121503458966 9720284543290084537888341433005226492014 8378983717511003499693031191564903557456 0
2
|
|||
|
|
|
| 20.08.2012, 22:59 [ТС] | |
|
valeriikozlov, спасибо за разложение решения по полочкам, завтра если не получиться отпишусь и спрошу. Ох, теперь меня загрузили, я как раз получил ответ от преподавателя, и вы прям изложили, тоже что написал и он. Спасибо, обдумаю!
0
|
|
|
быдлокодер
1724 / 911 / 106
Регистрация: 04.06.2008
Сообщений: 5,705
|
|
| 20.08.2012, 23:15 | |
|
0
|
|
| 20.08.2012, 23:15 | |
|
Помогаю со студенческими работами здесь
40
Комбинаторика. Найти число целых положительных чисел.
Комбинаторика. Комбинаторика Комбинаторика Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
Новые блоги и статьи
|
|||
|
Камера Toupcam IUA500KMA
Eddy_Em 12.02.2026
Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
|
И ясному Солнцу
zbw 12.02.2026
И ясному Солнцу,
и светлой Луне.
В мире
покоя нет
и люди
не могут жить в тишине.
А жить им немного лет.
|
«Знание-Сила»
zbw 12.02.2026
«Знание-Сила»
«Время-Деньги»
«Деньги -Пуля»
|
SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров
8Observer8 12.02.2026
Содержание блога
Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .
|
|
SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image)
8Observer8 11.02.2026
Содержание блога
Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .
|
SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image
8Observer8 10.02.2026
Содержание блога
Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .
|
Установка Qt-версии Lazarus IDE в Debian Trixie Xfce
volvo 10.02.2026
В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .
|
SDL3 для Web (WebAssembly): Работа со звуком через SDL3_mixer
8Observer8 08.02.2026
Содержание блога
Пошагово создадим проект для загрузки звукового файла и воспроизведения звука с помощью библиотеки SDL3_mixer. Звук будет воспроизводиться по клику мышки по холсту на Desktop и по. . .
|