|
3 / 3 / 1
Регистрация: 07.07.2012
Сообщений: 90
|
|
В промежутке от A до B найти числа, в записи которых в двоичной системе ровно K единиц01.11.2012, 15:18. Показов 5901. Ответов 12
Метки нет (Все метки)
Помогите найти оптимальный алгоритм решения:
Условие: В числах от A до B включительно найти числа, в которых, в записи их в двоичной системе ровно K единиц Допустим при A = 10, B = 20, K = 2, чисел таких будет 5 штук. 10=10102; 12=11002; 17=100012; 20=101002 Вот вобщем то задачка, но ее нельзя делать перебором всех чисел, так как времени это займет слишком много... Уважаемые знатоки, подскажите оптимальный алгоритм для этого)
0
|
|
| 01.11.2012, 15:18 | |
|
Ответы с готовыми решениями:
12
В промежутке от A до B найти числа, в записи которых в двоичной системе ровно 2 единиц
Посчитать сколько единиц есть в записи числа в двоичной системе счисления |
|
15155 / 6428 / 1731
Регистрация: 24.09.2011
Сообщений: 9,999
|
||||||||||||
| 01.11.2012, 16:26 | ||||||||||||
![]() Без претензии на скорость, но оригинально ![]()
Можно ускорить в 3 раза (от 0 до миллиона: пред. вариант 5с, этот 1,5с)
0
|
||||||||||||
|
3 / 3 / 1
Регистрация: 07.07.2012
Сообщений: 90
|
||
| 01.11.2012, 17:09 [ТС] | ||
|
Казанский, спасибо) Разобрал твой пример, я бы так впринцепе и делал, если бы не упор на время(
Дело в том, что B может быть 10^9... И перебор такого кол-ва чисел идет слишком длительное время... P.S.
0
|
||
|
3 / 3 / 1
Регистрация: 07.07.2012
Сообщений: 90
|
|
| 01.11.2012, 20:27 [ТС] | |
|
Вероятно в Double надо...
Дело в том, что это чисто теоретическое ограничение, так как задача оллимпиадная, и не совсем прикладная... Вы всетаки считаете, что у Казанского наиболее оптимальный алгоритм? Вот еще кое что по теме откопал Смотреть топик valeriikozlov'а. (Правда я Paschal вобще не знаю, да и алгоритм тяжеловат для меня)
0
|
|
|
9908 / 3928 / 742
Регистрация: 11.10.2011
Сообщений: 5,908
|
||||||||
| 01.11.2012, 21:05 | ||||||||
![]()
1
|
||||||||
|
15155 / 6428 / 1731
Регистрация: 24.09.2011
Сообщений: 9,999
|
||
| 01.11.2012, 23:37 | ||
![]() Конечно, при больших b это задача на комбинаторику: b задает число "клеток" (разрядов двоичного числа), и задача сводится к тому, чтобы расставить заданное число единиц всеми способами в этих клетках, отбросив варианты, которые не попадают в диапазон a...b.
0
|
||
|
3 / 3 / 1
Регистрация: 07.07.2012
Сообщений: 90
|
|||
| 01.11.2012, 23:53 [ТС] | |||
|
Вот на пример: a = 8 b = 50 k = 2 число есть 10010002. Вот как определить, входит ли оно в заданный диапазон? Апострофф, ты не мог бы тоже расставить комментарии в коде, который ты перевел с Pascal. Спасибо большое кстати)
0
|
|||
|
15155 / 6428 / 1731
Регистрация: 24.09.2011
Сообщений: 9,999
|
|||||||
| 04.11.2012, 01:08 | |||||||
|
Да, в VB нет функции Bin, но есть Oct и Hex, которые возвращают текст, связанный с двоичным представлением числа. В коде полученное 8-ричное число разбивается на цифры (каждая цифра - 3 бита исходного числа) и к счетчику единиц прибавляется соотв. число. Та же процедура с традиционным переводом числа в двоичный код с помощью целочисленного деления работает в ~2 раза быстрее:
1
|
|||||||
|
3 / 3 / 1
Регистрация: 07.07.2012
Сообщений: 90
|
|
| 04.11.2012, 10:07 [ТС] | |
|
Спасибо)
0
|
|
|
3 / 3 / 1
Регистрация: 07.07.2012
Сообщений: 90
|
||||||
| 06.11.2012, 08:30 [ТС] | ||||||
|
Товарищи, подскажите, почему у меня ошибка overflow в строке "j = Int(j \ 10)"? (30 по счету, в данном ниже коде)
0
|
||||||
|
9908 / 3928 / 742
Регистрация: 11.10.2011
Сообщений: 5,908
|
|
| 06.11.2012, 08:58 | |
|
Деление нацело (\) не работает с числами, превышающими max от Long=2147483647
Замените на простое деление (/), тем более, что Int как раз доделывает то, что запрашиваете.
0
|
|
|
15155 / 6428 / 1731
Регистрация: 24.09.2011
Сообщений: 9,999
|
||||||||||||||||||||||||||
| 10.11.2012, 15:17 | ||||||||||||||||||||||||||
|
Написал рекурсивную функцию для перебора комбинаций бит
код модуля с функцией
код модуля с "тривиальной" функцией и тестовой процедурой
0
|
||||||||||||||||||||||||||
| 10.11.2012, 15:17 | |
|
Помогаю со студенческими работами здесь
13
Вывести все натуральные числа, не превосходящие N, в двоичной записи которых К единиц Найти количество единиц в двоичной записи числа
Найти количество чисел от 1 до N, у которых места единиц в двоичной записи образуют арифметическую прогрессию Вывести все десятичные числа, в двоичной записи которых число нулей на 2 превосходит число единиц Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
| Опции темы | |
|
|
Новые блоги и статьи
|
|||
|
Отчёт о затраченных материалах за определенный период с макетом печатной формы
Maks 21.04.2026
Отчёт из решения ниже размещён в конфигурации КА2.
Задача: разработка отчёта по затраченным материалам за определённый период, с возможностью вывода печатной формы отчёта с шапкой и подвалом.
В. . .
|
Отчёт о спецтехнике находящейся в ремонте
Maks 20.04.2026
Отчёт из решения ниже размещен в конфигурации КА2.
Задача: отобразить спецтехнику, которая на данный момент находится в ремонте.
Есть нетиповой документ "Заявка на ремонт спецтехники" который. . .
|
Памятка для бота и "визитка" для читателей "Semantic Universe Layer (Слой семантической вселенной)"
Hrethgir 19.04.2026
Сгенерировано для краткого описания по случаю сборки и компиляции скелета серверного приложения. И пусть после этого скажут, что статьи сгенерированные AI - туфта и не интересно. И это не реклама -. . .
|
Запрет удаления строк ТЧ документа при определённом условии
Maks 19.04.2026
Алгоритм из решения ниже реализован на примере нетипового документа "Аккумуляторы", разработанного в конфигурации КА2. У данного документа есть ТЧ, в которой в зависимости от прав доступа. . .
|
|
Модель заражения группы наркоманов
alhaos 17.04.2026
Условия задачи сформулированы тут
Суть:
- Группа наркоманов из 10 человек.
- Только один инфицирован ВИЧ.
- Колются одной иглой.
- Колются раз в день.
- Колются последовательно через. . .
|
Мысли в слух. Про "навсегда".
kumehtar 16.04.2026
Подумалось тут, что наверное очень глупо использовать во всяких своих установках понятие "навсегда". Это очень сильное понятие, и я только начинаю понимать край его смысла, не смотря на то что давно. . .
|
My Business CRM
MaGz GoLd 16.04.2026
Всем привет, недавно возникла потребность создать CRM, для личных нужд. Собственно программа предоставляет из себя базу данных клиентов, в которой можно фиксировать звонки, стадии сделки, а также. . .
|
Знаешь почему 90% людей редко бывают счастливыми?
kumehtar 14.04.2026
Потому что они ждут. Ждут выходных, ждут отпуска, ждут удачного момента. . .
а удачный момент так и не приходит.
|