|
|
||||||
Комбинаторика! Число сочитаний08.08.2012, 19:55. Показов 5913. Ответов 40
Метки нет (Все метки)
Доброго времени суток. Так как я глубоко начинающий программист, столкнулся с проблемой решения задач по комбинаторике (на данный момент формула числа сочитаний). Каким образом можно записать эту формулу на С++, знаю имееться много способов (через рекурсию и т.д.)? Можете, пожалуйста, написать реализацию и объяснить? Вот пример через рекурсию, но никак не пойму принцип работы, объясните? Сама задача вот, на тестах неверный ответ, а на других лимит времени исчерпан, проверил не правильный ответ на нечетных числах и на числе 2, объясните, пожалуйста, принцип рекурсии здесь, а не просто решите задачу! Пожалуйста
![]()
), поэтому буду часто спрашивать. Обидно ведь, когда посылают на олимпиаду, а там все задачи на листочке решил (математически), а как написать программу не знаешь
0
|
||||||
| 08.08.2012, 19:55 | |
|
Ответы с готовыми решениями:
40
Комбинаторика, вычислить число сочетаний C(N, K) Комбинаторика.Подсчитать число размещений с повторениями Нажатие сочитаний клавиш |
|
Комп_Оратор)
|
||||||
| 08.08.2012, 20:21 | ||||||
Принцип рекурсии состоит в том, что функции разрешено вызывать самую себя. Функция возвращающая значение - выражение результат которого подставляется в место вызова. В классическом примере - подсчете факториала, функция вызывается до тех пор пока аргумент не станет 1 и не наткнется на первое условие выхода из функции (нерекурсивная ветвь алгоритма).
1
|
||||||
|
|
||
| 08.08.2012, 20:47 [ТС] | ||
А вот ссылка на саму задачу http://www.e-olimp.com/problems/65Но лишь одно смущает, скорость работы, может есть вариант более быстрый? Добавлено через 4 минуты Да, и ваш вариант лобовой и не верный, аж четыре ошибки! Что не так? Добавлено через 3 минуты Да, и что за переменная m?
0
|
||
|
Комп_Оратор)
|
|||||||
| 08.08.2012, 21:02 | |||||||
![]() вот с исправлениями:
1
|
|||||||
|
|
|
| 08.08.2012, 21:35 [ТС] | |
|
Разобрался со всем спасибо
Но теперь хотелось бы еще подстроиться под задачу! Тесты теперь вообще не проходят, неверный ответ+ ошибка компиляции, как избавиться от ошибки компиляции? http://www.e-olimp.com/solutions/733293Не верный ответ я знаю почему, поскольку не учел нечетные числа, но там есть тест с двойкой, и он видимо тоже не проходит, что нет так?
0
|
|
|
|
|
| 10.08.2012, 16:58 | |
|
mr_free, вот пройди почитай
https://www.cyberforum.ru/blogs/34326/blog232.html тебе надо СSN/2 Добавлено через 4 минуты http://liveworkspace.org/code/... 4a590ae0a7
1
|
|
|
|
|
| 10.08.2012, 18:41 [ТС] | |
|
Я знаю какая формула мне нужна (можно было посмотреть самое первое сообщение, сам код)!
Добавлено через 4 минуты Но вообщем спасибо Будет время проверю! Посмотрите, пожалуйста, мой же вопрос (Работа со звуком! Ошибка! SOS!), может поможете?!
0
|
|
|
|
|||||||
| 10.08.2012, 20:51 | |||||||
0
|
|||||||
|
быдлокодер
1724 / 911 / 106
Регистрация: 04.06.2008
Сообщений: 5,705
|
|
| 10.08.2012, 22:11 | |
|
Не советую использовать рекурсию в подобных задачах. Так, чисто для себя если, чтобы РАЗРОБРАТЬСЯ что и как, не более того.
0
|
|
|
|
||||||
| 10.08.2012, 22:41 | ||||||
|
mr_free, по вашему вопросу, ещё раз приведу свой код, дабы вы поняли что в своём тесте я поставил
N = 65 а S = 5 Теперь смотрите отработку под N = 4 S = 3 http://liveworkspace.org/code/... a9571c5fc7 Если хотите более понятный в плане логики код, тогда вот он, считает он также
![]() PS:Корректная формула числа сочетаний здесь http://ru.wikipedia.org/wiki/Сочетание
1
|
||||||
|
|
||
| 12.08.2012, 20:33 [ТС] | ||
|
Благодарю, и простите что не отписался о том что разобрался!
-=ЮрА=-, а почему вам не понравился ответ на том ресурсе? вы имеете в виду e-olimp? Да, и еще почему в данных задачах не стоит использовать рекурсию? Хм, что-то я не понял ответа 4? Ответ не правильный у вас поскольку число 3 не испьлзуеться при ришении задачи, это просто не нужный параметр,
0
|
||
| 12.08.2012, 20:45 | ||
|
Не по теме:
0
|
||
|
быдлокодер
1724 / 911 / 106
Регистрация: 04.06.2008
Сообщений: 5,705
|
|||||||
| 13.08.2012, 05:31 | |||||||
...Я сделал, чтобы глубина рекурсии была не больше kolichestvo_drugih_chisel. Это фигня, это очень мало. Стек не переполнится. Но ведь это я СДЕЛАЛ. (Видишь, использовал ЦИКЛ+ рекурсию). А можно было бы и не сделать, обойтись одной рекурсией и пиши пропало, ступеньки вылетели бы туда непонятно куда и крах программы. И да, время отладки она вылетала у меня не раз и не два из-за переполнения стека (ошибка трудноуловимая). А если ты вместо рекурсии используешь цикл, одной проблемой меньше.
0
|
|||||||
|
|
||||||
| 13.08.2012, 14:20 [ТС] | ||||||
|
Хм, а ведь действительно так
Вот наконец выдолась свободная минутка и можно дорешать задачу и подумать над замечанием! Благодарю за помощь! Если будут вопросы, обязательно задам!P.s. тема пока не закрыта! Добавлено через 2 часа 15 минут Вот сейчас решаю задачку и вроде все сделал правильно, но при вводе любых четных чисел (n), всегда выводиться n! Что не так пишу, прошу делать замечания на представленом коде и не вносить другие переменные и т.п.? Подскажите, пожалуйста, с этим и вопрос снят!
kravam, интересно а как насчет быстродействия даного метода? точность как я понял горантирована!
0
|
||||||
| 13.08.2012, 14:50 | |
|
0
|
|
|
быдлокодер
1724 / 911 / 106
Регистрация: 04.06.2008
Сообщений: 5,705
|
||||||||||||||||||||||
| 13.08.2012, 16:01 | ||||||||||||||||||||||
|
Насчёт скорости- чёрт его знает, откровеннно говоря. Тут надо хорошо разбираться в этом чтобы делать какие-то выводы. Вот подсчёт факориала рекурсией
Но это только предположения. Ничто не мешает компилятору задействовать ячейку памяти для данной задачи (под возвращаемое значение) и тогда скорость упадёт. Ну и так далее. ++++++++++++++++++++++++++++++++++++++++ +++++++++++ Уж лучше проверь руками. Наверное, есть какие-то специальные функции чтобы узнать, сколько времени длится та или иная программа. Но я парень простой, я бы сделал примерно так:
0
|
||||||||||||||||||||||
|
|
|||
| 13.08.2012, 16:06 | |||
|
0
|
|||
|
|
||||||
| 13.08.2012, 16:18 [ТС] | ||||||
|
-=ЮрА=-, также само работает программа, а это я изменял от безвыходности, поскольку не сильно понимаю сокращенные записи!
Добавлено через 6 минут Забылся там, после этого изменения будет такой ответ для тестов:
0
|
||||||
| 13.08.2012, 16:18 | |
|
Помогаю со студенческими работами здесь
20
Комбинаторика. Найти число целых положительных чисел.
Комбинаторика. Комбинаторика Комбинаторика Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
Новые блоги и статьи
|
|||
|
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами
8Observer8 20.02.2026
Содержание блога
Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .
|
Конвертировать закладки radiotray-ng в m3u-плейлист
damix 19.02.2026
Это можно сделать скриптом для PowerShell. Использование
. \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json>
Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом.
# Check if. . .
|
Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI
Eddy_Em 18.02.2026
Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так:
https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347
Основана на STM32F303RBT6.
На борту пять. . .
|
Камера 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. Пошагово создадим проект для загрузки изображения. . .
|