|
|
||||||
Комбинаторика! Число сочитаний08.08.2012, 19:55. Показов 5853. Ответов 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
Комбинаторика. Найти число целых положительных чисел.
Комбинаторика. Комбинаторика Комбинаторика Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
Новые блоги и статьи
|
|||
|
Установка Android SDK, NDK, JDK, CMake и т.д.
8Observer8 25.01.2026
Содержание блога
Перейдите по ссылке: https:/ / developer. android. com/ studio и в самом низу страницы кликните по архиву "commandlinetools-win-xxxxxx_latest. zip"
Извлеките архив и вы увидите. . .
|
Вывод текста со шрифтом TTF на Android с помощью библиотеки SDL3_ttf
8Observer8 25.01.2026
Содержание блога
Если у вас не установлены Android SDK, NDK, JDK, и т. д. то сделайте это по следующей инструкции: Установка Android SDK, NDK, JDK, CMake и т. д.
Сборка примера
Скачайте. . .
|
Использование SDL3-callbacks вместо функции main() на Android, Desktop и WebAssembly
8Observer8 24.01.2026
Содержание блога
Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
|
моя боль
iceja 24.01.2026
Выложила интерполяцию кубическими сплайнами www. iceja. net
REST сервисы временно не работают, только через Web.
Написала за 56 рабочих часов этот сайт с нуля. При помощи perplexity. ai PRO , при. . .
|
|
Модель сукцессии микоризы
anaschu 24.01.2026
Решили писать научную статью с неким РОманом
|
http://iceja.net/ математические сервисы
iceja 20.01.2026
Обновила свой сайт http:/ / iceja. net/ , приделала Fast Fourier Transform экстраполяцию сигналов. Однако предсказывает далеко не каждый сигнал (см ограничения http:/ / iceja. net/ fourier/ docs ). Также. . .
|
http://iceja.net/ сервер решения полиномов
iceja 18.01.2026
Выкатила http:/ / iceja. net/ сервер решения полиномов (находит действительные корни полиномов методом Штурма).
На сайте документация по API, но скажу прямо VPS слабенький и 200 000 полиномов. . .
|
Расчёт переходных процессов в цепи постоянного тока
igorrr37 16.01.2026
/ *
Дана цепь(не выше 3-го порядка) постоянного тока с элементами R, L, C, k(ключ), U, E, J. Программа находит переходные токи
и напряжения на элементах схемы классическим методом(1 и 2 з-ны. . .
|