1 | ||||||
Комбинаторика! Число сочитаний08.08.2012, 19:55. Показов 4893. Ответов 40
Метки нет (Все метки)
Доброго времени суток. Так как я глубоко начинающий программист, столкнулся с проблемой решения задач по комбинаторике (на данный момент формула числа сочитаний). Каким образом можно записать эту формулу на С++, знаю имееться много способов (через рекурсию и т.д.)? Можете, пожалуйста, написать реализацию и объяснить? Вот пример через рекурсию, но никак не пойму принцип работы, объясните? Сама задача вот, на тестах неверный ответ, а на других лимит времени исчерпан, проверил не правильный ответ на нечетных числах и на числе 2, объясните, пожалуйста, принцип рекурсии здесь, а не просто решите задачу! Пожалуйста
0
|
08.08.2012, 19:55 | |
Ответы с готовыми решениями:
40
Комбинаторика, вычислить число сочетаний C(N, K) Комбинаторика.Подсчитать число размещений с повторениями Нажатие сочитаний клавиш Комбинаторика. Найти число целых положительных чисел. |
Комп_Оратор)
|
||||||
08.08.2012, 20:21 | 2 | |||||
Принцип рекурсии состоит в том, что функции разрешено вызывать самую себя. Функция возвращающая значение - выражение результат которого подставляется в место вызова. В классическом примере - подсчете факториала, функция вызывается до тех пор пока аргумент не станет 1 и не наткнется на первое условие выхода из функции (нерекурсивная ветвь алгоритма).
1
|
08.08.2012, 20:47 [ТС] | 3 |
Коротко и ясно, спасибо! Сам буду в следуйщий раз писать короче, а то написал прям статью! Сейчас по колдую, но вроде стало ясно А вот ссылка на саму задачу http://www.e-olimp.com/problems/65
Но лишь одно смущает, скорость работы, может есть вариант более быстрый? Добавлено через 4 минуты Да, и ваш вариант лобовой и не верный, аж четыре ошибки! Что не так? Добавлено через 3 минуты Да, и что за переменная m?
0
|
Комп_Оратор)
|
||||||
08.08.2012, 21:02 | 4 | |||||
извините не компилировал.
вот с исправлениями:
1
|
08.08.2012, 21:35 [ТС] | 5 |
Разобрался со всем спасибо Но теперь хотелось бы еще подстроиться под задачу! Тесты теперь вообще не проходят, неверный ответ+ ошибка компиляции, как избавиться от ошибки компиляции? http://www.e-olimp.com/solutions/733293
Не верный ответ я знаю почему, поскольку не учел нечетные числа, но там есть тест с двойкой, и он видимо тоже не проходит, что нет так?
0
|
Заблокирован
|
|
10.08.2012, 16:58 | 7 |
mr_free, вот пройди почитай
https://www.cyberforum.ru/blogs/34326/blog232.html тебе надо СSN/2 Добавлено через 4 минуты http://liveworkspace.org/code/... 4a590ae0a7
1
|
10.08.2012, 18:41 [ТС] | 8 |
Я знаю какая формула мне нужна (можно было посмотреть самое первое сообщение, сам код)!
Добавлено через 4 минуты Но вообщем спасибо Будет время проверю! Посмотрите, пожалуйста, мой же вопрос (Работа со звуком! Ошибка! SOS!), может поможете?!
0
|
10.08.2012, 20:51 | 9 | |||||
вы просто неправильно используйте условия выхода из рекурсии. вашу функцию надо немного переделать
0
|
быдлокодер
1724 / 911 / 106
Регистрация: 04.06.2008
Сообщений: 5,679
|
|
10.08.2012, 22:11 | 10 |
Не советую использовать рекурсию в подобных задачах. Так, чисто для себя если, чтобы РАЗРОБРАТЬСЯ что и как, не более того.
0
|
Заблокирован
|
||||||
10.08.2012, 22:41 | 11 | |||||
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 [ТС] | 12 |
Благодарю, и простите что не отписался о том что разобрался!
-=ЮрА=-, а почему вам не понравился ответ на том ресурсе? вы имеете в виду e-olimp? Да, и еще почему в данных задачах не стоит использовать рекурсию? Хм, что-то я не понял ответа 4? Ответ не правильный у вас поскольку число 3 не испьлзуеться при ришении задачи, это просто не нужный параметр,
0
|
|
12.08.2012, 20:45
#13
|
Не по теме: - это была фраза karavam и я просто не стал её критиковать, по причине игнорирования мной данного пользователя. В том виде котором рекурсию подаля я её можно использовать. Ну а так да, рекурсия - это дело тонокое и надо так сказать для него "набить руку" (при сбое или недоработки логики окончания рекурсия может приводить к зацикливаниюалгоритма без какой-либо возможности что либо остановить в работающем "зацикленном" алгоритме)
0
|
быдлокодер
1724 / 911 / 106
Регистрация: 04.06.2008
Сообщений: 5,679
|
||||||
13.08.2012, 05:31 | 14 | |||||
Стека жрёт много. Смотрим количество сочетаний без возврата и без учёта порядка. Рекурсия+ цикл:
...Я сделал, чтобы глубина рекурсии была не больше kolichestvo_drugih_chisel. Это фигня, это очень мало. Стек не переполнится. Но ведь это я СДЕЛАЛ. (Видишь, использовал ЦИКЛ+ рекурсию). А можно было бы и не сделать, обойтись одной рекурсией и пиши пропало, ступеньки вылетели бы туда непонятно куда и крах программы. И да, время отладки она вылетала у меня не раз и не два из-за переполнения стека (ошибка трудноуловимая). А если ты вместо рекурсии используешь цикл, одной проблемой меньше.
0
|
13.08.2012, 14:20 [ТС] | 15 | |||||
Хм, а ведь действительно так Вот наконец выдолась свободная минутка и можно дорешать задачу и подумать над замечанием! Благодарю за помощь! Если будут вопросы, обязательно задам!
P.s. тема пока не закрыта! Добавлено через 2 часа 15 минут Вот сейчас решаю задачку и вроде все сделал правильно, но при вводе любых четных чисел (n), всегда выводиться n! Что не так пишу, прошу делать замечания на представленом коде и не вносить другие переменные и т.п.? Подскажите, пожалуйста, с этим и вопрос снят!
kravam, интересно а как насчет быстродействия даного метода? точность как я понял горантирована!
0
|
|
13.08.2012, 14:50
#16
|
0
|
быдлокодер
1724 / 911 / 106
Регистрация: 04.06.2008
Сообщений: 5,679
|
|||||||||||||||||||||
13.08.2012, 16:01 | 18 | ||||||||||||||||||||
Не ну как- точность гарантирована настолько, насколько она вообще может быт гарантирована при работаешь с дробными числами (если работаешь с ними). Не более, но и не менее.
Насчёт скорости- чёрт его знает, откровеннно говоря. Тут надо хорошо разбираться в этом чтобы делать какие-то выводы. Вот подсчёт факориала рекурсией
Но это только предположения. Ничто не мешает компилятору задействовать ячейку памяти для данной задачи (под возвращаемое значение) и тогда скорость упадёт. Ну и так далее. +++++++++++++++++++++++++++++++++++++++++++++++++++ Уж лучше проверь руками. Наверное, есть какие-то специальные функции чтобы узнать, сколько времени длится та или иная программа. Но я парень простой, я бы сделал примерно так:
0
|
13.08.2012, 16:18 [ТС] | 20 |
-=ЮрА=-, также само работает программа, а это я изменял от безвыходности, поскольку не сильно понимаю сокращенные записи!
Добавлено через 6 минут Забылся там, после этого изменения будет такой ответ для тестов: Код
Вводим 4 2 Получаем 24
0
|
13.08.2012, 16:18 | |
13.08.2012, 16:18 | |
Помогаю со студенческими работами здесь
20
Программа для вычисления числа сочитаний из N по M Комбинаторика. Комбинаторика Комбинаторика Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |