|
|
||||||
Комбинаторика! Число сочитаний08.08.2012, 19:55. Показов 6057. Ответов 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
Комбинаторика. Найти число целых положительных чисел.
Комбинаторика. Комбинаторика Комбинаторика Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
| Опции темы | |
|
|
Новые блоги и статьи
|
|||
|
Хитросплетение родственных связей пантеона греческих богов.
russiannick 14.05.2026
Однооконник, позволяющий узреть и изучить отдельных героев древней Греции.
<!DOCTYPE html>
<html lang="ru">
<head>
<meta charset="UTF-8">
<meta http-equiv="X-UA-Compatible". . .
|
[golang] Угол между стрелками часов
alhaos 12.05.2026
По заданным значениям часа и минуты необходимо определить значение меньшего угла между стрелками аналогового циферблата часов.
import "math"
func angleClock(hour int, minutes int) float64 {
. . .
|
Debian 13: Установка Lazarus QT5
ВитГо 09.05.2026
Эта инструкция моя компиляция инструкций volvo
https:/ / www. cyberforum. ru/ blogs/ 203668/ 10753. html
и его же старой инструкции по установке Lazarus с gtk2. . .
|
Нейросеть на алгоритме "эстафета хвоста" как перспектива.
Hrethgir 06.05.2026
На десерт, когда запущу сервер.
Статья тут https:/ / habr. com/ ru/ articles/ 1030914/ . Автор я сам, нейросеть только помогает в вопросах которые мне не известны - не знаю людей которые знали-бы. . .
|
|
Асинхронный приём данных из COM-порта
Argus19 01.05.2026
Асинхронный приём данных из COM-порта
Купил на aliexpress термопринтер QR701. Он оказался странным. Поключил к Arduino Nano. Был очень удивлён. Наотрез отказывается печатать русские буквы. Чтобы. . .
|
попытка написать игровой сервер на C++
pyirrlicht 29.04.2026
попытка написать игровой сервер на плюсах с открытым бесконечным миром.
возможно получится прикрутить интерпретатор питон для кастомизации игровой логики.
что есть на текущий момент:. . .
|
Контроль уникальности выбранного документа-основания при изменении реквизита
Maks 28.04.2026
Алгоритм из решения ниже разработан на примере нетипового документа "ЗаявкаНаРемонтСпецтехники", разработанного в КА2.
Задача: уведомлять пользователя, если указанная заявка (документ-основание). . .
|
Благородство как наказание
Maks 24.04.2026
У хорошего человека отношения с женщинами всегда складываются трудно. А я человек хороший. Заявляю без тени смущения, потому что гордиться тут нечем. От хорошего человека ждут соответствующего. . .
|