|
|
|
|
|
|
|
Вернуться
| 1 Григорьевых Данил Павлович, 15 ноября 2008 г. 16:48:19 | |
|
Я понимаю так: позиция возможна, если все выбранные буквы "Y", и невозможна если ХОТЯ БЫ одна (из выбранных) "N". Поэтому если в программе заменить букву "Y" на "N", то она посчитает не кол-во неправильных ситуаций. Я Вас не понимаю наверно... объясните пожалуйста
|
|
|
| 2 Григорьевых Данил Павлович, 10 ноября 2008 г. 17:28:21 | |
Мой рекурсивный перебор только лишь до 35-ого доходил :) Я что-то не понял, а как T считать за 40 миллионов?
Тот же рекурсивный алгоритм с возвратом. Перебор осуществляется только тех вариантов расстановки танцующих, которые могут танцевать. Можно перебирать либо возможные пары, либо невозможные. Вот и выбираем тех, кого меньше и перебираем их. Только, боюсь, это все-равно не поможет...
|
|
|
| 3 Беляев Сергей Николаевич, 10 ноября 2008 г. 6:02:53 | |
|
Динамическое программирование на самом деле. Рекурсивный перебор всех вариантов умирает, т.к. вариантов пар может быть более 80 миллионов! Это легко показать: при N=10 M=10 и K=8 и факте, что все танцевать могут со всеми получаем, что число пар равно C(8,10)*C(8,10)*8!=81648000. При грамотной рекурсивной реализации можно свести к 40 миллионам, но не факт, что и это поможет, хотя попробовать интересно. Скажу подробнее о 40 млн.: этого можно достичь, если изначально определять, что выгоднее искать: пары, которые могут танцевать или пары, которые не могут (зависит от того, чего больше в таблице: символов N или символов Y). Если пар, которые не могут танцевать меньше, чем которые могут, то находим их. Пусть это будет T, тогда в качестве ответа будет значение C(K,M)*C(K,N)*(min(M,N)!)-T. Ну а динамическое решение работает быстро, только до него очень сложно додуматься. Я, например, не додумался. Попробуйте теперь вы :) Ах, да... Вам пробовать не на чем :)
|
|
|
| 4 Масюк Олег Юрьевич, 09 ноября 2008 г. 19:00:58 | |
|
По-моему это паросочетание
|
|
|
Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!
| | | |
