|
3 / 3 / 1
Регистрация: 07.07.2012
Сообщений: 90
|
|
В промежутке от A до B найти числа, в записи которых в двоичной системе ровно K единиц01.11.2012, 15:18. Показов 5899. Ответов 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 превосходит число единиц Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
Новые блоги и статьи
|
|||
|
Знаешь почему 90% людей редко бывают счастливыми?
kumehtar 14.04.2026
Потому что они ждут. Ждут выходных, ждут отпуска, ждут удачного момента. . .
а удачный момент так и не приходит.
|
Фиксация колонок в отчете СКД
Maks 14.04.2026
Фиксация колонок в СКД отчета типа Таблица.
Задача: зафиксировать три левых колонки в отчете.
Процедура ПриКомпоновкеРезультата(ДокументРезультат, ДанныеРасшифровки, СтандартнаяОбработка)
/ / . . .
|
Настройки VS Code
Loafer 13.04.2026
{
"cmake. configureOnOpen": false,
"diffEditor. ignoreTrimWhitespace": true,
"editor. guides. bracketPairs": "active",
"extensions. ignoreRecommendations": true,
. . .
|
Оптимизация кода на разграничение прав доступа к элементам формы
Maks 13.04.2026
Алгоритм из решения ниже реализован на нетиповом документе, разработанного в конфигурации КА2.
Задачи, как таковой, поставлено не было, проделанное ниже исключительно моя инициатива.
Было так:. . .
|
|
Контроль заполнения и очистка дат в зависимости от значения перечислений
Maks 12.04.2026
Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2.
Задача: реализовать контроль корректности заполнения дат назначения. . .
|
Архитектура слоя интернета для сервера-слоя.
Hrethgir 11.04.2026
В продолжение https:/ / www. cyberforum. ru/ blogs/ 223907/ 10860. html
Знаешь что я подумал? Раз мы все источники пишем в голове ветки, то ничего не мешает добавить в голову такой источник, который сам. . .
|
Подстановка значения реквизита справочника в табличную часть документа
Maks 10.04.2026
Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2.
Задача: при выборе сотрудника (справочник Сотрудники) в ТЧ документа. . .
|
Очистка реквизитов документа при копировании
Maks 09.04.2026
Алгоритм из решения ниже применим как для типовых, так и для нетиповых документов на самых различных конфигурациях.
Задача: при копировании документа очищать определенные реквизиты и табличную. . .
|