Задача на динамику или комбинаторику11.08.2011, 11:50. Показов 6070. Ответов 33
Метки нет (Все метки)
Условие
Для заданных натуральных чисел N и K требуется вычислить количество чисел от 1 до N, имеющих в двоичной записи ровно K нулей. два натуральных числа через пробел N и K, не превышающие 10^9
На этой задаче мой решения не проходят по времени. Можно услышать ваше мнение по поводу решения этой задачи?
0
|
|
| 11.08.2011, 11:50 | |
|
Ответы с готовыми решениями:
33
Задача на комбинаторику
Задача про фишки на комбинаторику |
|
|
||||||||||||
| 11.08.2011, 16:00 | ||||||||||||
0
|
||||||||||||
| 11.08.2011, 16:06 [ТС] | |||
|
у 100 - два нуля, 1000 - 3, а надо 1. Потому что k=1! Добавлено через 1 минуту Добавлено через 1 минуту Если есть задача - найдется и решение
0
|
|||
|
|
|||||||
| 11.08.2011, 16:09 | |||||||
1
|
|||||||
|
Higher
|
|||||||
| 11.08.2011, 16:27 | |||||||
|
Таки я был прав, треугольник Паскаля рулит! К сожалению, понятно объяснить вряд ли смогу, сам только сегодня его строить научился, но тем не менее код проходит все тесты практически мгновенно.
1
|
|||||||
|
9 / 8 / 1
Регистрация: 05.08.2011
Сообщений: 56
|
|
| 11.08.2011, 18:28 | |
|
Набросал программку
. Я так понял, главная задача: перевод большого натурального (хотя бы)числа из десятичного представления в двоичное (хотя бы 32 бит). Моя функция c10to2 это и делает, причем число бит и размер исходного числа для алгоритма не важны (в демо версии упрощено до 200 бит). В Chislo1 необходимо ввести побайтно исходное число N. После работы функций для решения задачи (пока частичного) можно посмотреть регистр BL. В нем будет число нулевых битов в данном числе (К). Число упаковано в переменную Result в слошную цепочку битов слева направо. Пока так . Если треба доделать задачу до конца, т.е. состряпать интерфейсик и процедуру перебора чисел - не проблема, только сообщите .
1
|
|
|
Higher
|
||
| 11.08.2011, 18:33 | ||
|
У вас не получится за секунду перебрать и проверить все возможные числа. Поэтому эта задача решается комбинаторикой и динамическим программированием. И да, это сложная олимпиадная задача =)
1
|
||
|
9 / 8 / 1
Регистрация: 05.08.2011
Сообщений: 56
|
|
| 15.08.2011, 00:06 | |
|
Покажите мне эти две строчки, да еще для числа произвольной длины
. А что каксается задачидля всех N не превышающих 10^9, то попробую на ассемблере уложится в секунду даже на двушке .
0
|
|
|
Higher
|
||
| 15.08.2011, 07:28 | ||
|
Просто перебор до 10^9 полсекунды примерно занимает, а если еще и переводить каждый раз в двоичную сс и проверять строку, то по времени никак не уложитесь =)
0
|
||
|
9 / 8 / 1
Регистрация: 05.08.2011
Сообщений: 56
|
|
| 15.08.2011, 09:29 | |
|
За ночку создал алгоритм обратного перевода из двоичной в десятичную для чисел 200-бит (демо
версия). Пришлось "идти" через 16-тиричную систему. Прога наполовину готова. Думаю еще день-два и выложу. Что касается собственно задачи, то зачем каждый раз переводить в двоичку, можно перевести один раз, а затем добавлять по 1. Вообще-то тут пахнет 64-битной арифметикой . Если нужны будутарифметические процедуры для таких чисел сообщите .
0
|
|
|
1069 / 848 / 60
Регистрация: 30.04.2011
Сообщений: 1,659
|
|
| 15.08.2011, 10:09 | |
|
diagon прав. Не нужен здесь перебор.
Надо взять N и посмотреть, сколько битов оно занимает. Например, M битов. Тогда надо считать число сочетаний из M-1 по К. К нулей могут быть в любом порядке среди младших M-1 битов, так как старший бит должен быть 1. А число сочетаний считается по треугольнику Паскаля.
1
|
|
|
848 / 190 / 18
Регистрация: 01.08.2011
Сообщений: 505
|
||
| 15.08.2011, 10:30 | ||
|
11100, 10110 и т.д., а эти числа уже превышают число N. Добавлено через 12 минут Этот метод подойдет, если суммировать сочетания Вот D то как раз и надо ухитриться подсчитать, а D - все числа с K нулями, не превышающие числа N, и со старшим единичным битом на M-ой позиции
2
|
||
|
9 / 8 / 1
Регистрация: 05.08.2011
Сообщений: 56
|
|
| 17.08.2011, 05:57 | |
|
Добил прогу
. Выкладываю (рабочая версия, могут быть огрехи ). Как и ранее, числа запакованыслева направо. В двоичных и 16-тиричных первый байт содержит фактическую длину числа. Вывод К и времени в 16-тиричке, т.к. лень было доделывать вывод в 10-тичной.
1
|
|
| 17.08.2011, 05:57 | |
|
Задача на динамику задача на комбинаторику Задача на комбинаторику Задача на комбинаторику
Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
Новые блоги и статьи
|
|||
|
Книги по геймдизайну, левел-дизайну, игровым механикам и проектированию игрового опыта
8Observer8 08.11.2026
Содержание блога | English Version
1. 2003 - 06 - Designing Virtual Worlds (1st Edition)
Автор: Richard A. Bartle | Объем: 768 стр.
Ссылки: Amazon
. . .
|
Родители токсичные абьюзеры по отношению к своим детям ругают их оскорбляют не любят
zorxor 08.11.2026
Жить в атмосфере постоянных оскорблений, критики и холодности со стороны родителей — это тяжелое и болезненное испытание, которое оставляет глубокие эмоциональные раны. Токсичное и абьюзивное. . .
|
Как только я захожу к себе в свою комнату я сразу же с себя снимаю свои трусы. Ответ от Джемени ИИ.
zorxor 08.11.2026
Джемени, как только я захожу к себе в свою комнату я сразу же с себя снимаю свои трусы.
Многие люди, возвращаясь домой, сразу переодеваются в максимально свободную одежду или вовсе предпочитают. . .
|
Паттерн очереди действий/команд (Action / Command Queue). Система очереди действий и кат-сцен с SDL3 Callbacks, cglm и OpenGL
8Observer8 07.11.2026
Содержание блога | English Version
Руководство для начинающих по реализации паттерна очереди действий/ команд (Action / Command Queue) на C++ (C++20) с использованием официального SDL3 Callbacks. . .
|
|
Проверка полного ФИО в типовом справочнике
Maks 07.11.2026
Решение реализовано в конфигурации КА2, на примере справочника "КонтактныеЛицаПартнеров".
Задача:
Запрет инициалов.
Не допускаеть использование сокращений вида "И. И. ", "И. И. ", "И И" и. . .
|
Про "Windows must die!"
kumehtar 04.11.2026
Знаете, чет накатило. . . .
Когда-то это было почти боевым кличем: мол, нормальный человек сидит на DOS, OS/ 2 или Linux, а вот это вот - Must Die. А теперь человек произносит «мастдай» с усмешкой - и. . .
|
Красочные поля с номером страницы svg+background-image
russiannick 04.11.2026
Красочные поля с номером страницы не менее важны чем в эпоху бумажных книг.
Посему спешу представить почтеннейшей публике этот важный инструмент который эти поля и формирует.
В процессе разработки. . .
|
Вступаем в новую фазу генерации favicons, векторную.
russiannick 02.11.2026
Теперь нет нужды скрывать что используется простой svg. Исходный код изображения помещаем в поле и жмем кнопку. Исходник преобразуется в вид корректный для помещения в favicon или в url(). Нажатие. . .
|