|
|
|
|
|
|
|
| 21 Cihad OGE, 09 ноября 2009 г. 10:05:49 |
Должен ли я рассчитать C (1000000000,500000000)? Требуется ли?
Нет, что вы! Тем более запись неверная. Обычно в C(k,n) k<=n. Буквально у вас это должно быть равно нулю. Но если их поменять, то получится очень большое число, которое конечно же вычислять немыслимо.
|
|
|
| 22 Соболев Евгений, 21 марта 2009 г. 15:27:45 |
| Алгоритм вкратце можно описать следующим образом: 1) перевожу число в двоичную систему; 2) если k>числа разрядов - выводить 0; 3) Ищу количество чисел с меньшим числом разрядов и с ровно k нулями; 4) ищу числа с таким же количеством разрядов, это делаю так: ищу только такие числа, у которых первые i разрядов совпадают с исходным числом (причем только тогда когда i+1 символ это 1, чтобы его можно было заменить на 0 и получить строго меньшее число). 5) если нулей в исходном числе ровно k - прибавляю к ответу 1.
|
|
|
| 23 Шипелов Роман Борисович, 19 марта 2009 г. 4:20:19 |
11 часов на задачу убил...а сначала она показалась легкой...
А мне до сих пор легкой кажется :)
|
|
|
| 24 Людвиченко Виталий Андреевич, 05 марта 2009 г. 20:45:00 |
Реально! там все равно в конце последний разряд в лоб надо. а предыдушие можно акториалиами
Больше че то я не придумал
Если под "в лоб" понимается какой то перебор весьма большого промежутка чисел, то это здесь не подойдет, тут все решается комбинаторикой.
|
|
|
| 25 Бобер Александр Дмитриевич, 11 мая 2007 г. 21:29:59 |
Оптимально-это рекурсивно или через логарифмы? Все равно "хвостик" между степенью двойки и N надо бить в "лоб"!
Это комбинаторика понимаете ли... В лоб бить не нужно.
|
|
|
| 26 Кузнецов Георгий Сергеевич, 04 апреля 2007 г. 13:41:48 |
При малых n моя программа бысро работает. А при n=1000000000 и k=1 программа 10 минут думала(пока я её не вырубил).
Ну оно и понятно :) Что вы так просто ее решить хотите? Здесь простым полным перебором не обойтись! Тут нужно использовать комбинаторику, да еще и оптимально вычислять C(k,n).
|
|
|
Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!
| | | |
