Форум программистов, компьютерный форум, киберфорум
Visual Basic
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.97/30: Рейтинг темы: голосов - 30, средняя оценка - 4.97
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
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
01.11.2012, 15:18
Ответы с готовыми решениями:

В промежутке от A до B найти числа, в записи которых в двоичной системе ровно 2 единиц
Необходимо реализовать функцию которая подсчитывает количество чисел, в двоичной записи которых ровно 2 единицы в заданном диапазоне; ...

Подсчитать количество единиц в записи данного числа в двоичной системе
дано натуральное число n. подсчитать количество единиц в записи данного числа в двоичной системе

Посчитать сколько единиц есть в записи числа в двоичной системе счисления
Дано число N в десятичной системе счисления. Нужно посчитать сколько единиц есть в записи этого числа в двоичной системе счисления. ...

12
15155 / 6428 / 1731
Регистрация: 24.09.2011
Сообщений: 9,999
01.11.2012, 16:26
Цитата Сообщение от Flaker Посмотреть сообщение
ее нельзя делать перебором всех чисел, так как времени это займет слишком много...
Вы на арифмометре считаете?
Без претензии на скорость, но оригинально
Visual Basic
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Sub bb()
Dim a&, b&, k&, i&, j&, m&, n&, s$
a = 10: b = 20: k = 2
For i = a To b
    s = Oct(i)
    n = 0
    For j = 1 To Len(s)
        Select Case Mid$(s, j, 1)
        Case "1", "2", "4": n = n + 1
        Case "3", "5", "6": n = n + 2
        Case "7": n = n + 3
        End Select
    Next
    If n = k Then m = m + 1
Next
MsgBox m
End Sub
Добавлено через 12 минут
Можно ускорить в 3 раза (от 0 до миллиона: пред. вариант 5с, этот 1,5с)
Visual Basic
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Sub bb()
Dim a&, b&, k&, i&, j&, m&, n&, s$
a = 10: b = 20: k = 2
For i = a To b
    s = Oct(i)
    n = 0
    For j = 1 To Len(s)
        Select Case CLng(Mid$(s, j, 1))
        Case 1, 2, 4: n = n + 1
        Case 3, 5, 6: n = n + 2
        Case 7: n = n + 3
        End Select
        If n > k Then GoTo nxt_num
    Next
    If n = k Then m = m + 1
nxt_num:
Next
MsgBox m
End Sub
0
3 / 3 / 1
Регистрация: 07.07.2012
Сообщений: 90
01.11.2012, 17:09  [ТС]
Казанский, спасибо) Разобрал твой пример, я бы так впринцепе и делал, если бы не упор на время(

Дело в том, что B может быть 10^9... И перебор такого кол-ва чисел идет слишком длительное время...

P.S.
s = Oct(i)
Только мне в двоичной надо)
0
Супер-модератор
Эксперт функциональных языков программированияЭксперт Python
 Аватар для Catstail
38203 / 21135 / 4310
Регистрация: 12.02.2012
Сообщений: 34,740
Записей в блоге: 14
01.11.2012, 19:52
Цитата Сообщение от Flaker Посмотреть сообщение
10^9...
- а в каком типе данных ты хранишь такие целые?
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
Цитата Сообщение от Flaker Посмотреть сообщение
Правда я Paschal вобще не знаю
Перевод:
Visual Basic
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
Option Explicit
Dim a&, b&, minn&, maxx&, col& ':longint;
 
Sub proc(a)
Dim t&
t = 1: minn = 0: maxx = 0
While a > 0
  If (a Mod 2) = 1 Then
    minn = maxx: maxx = t
  End If
  a = a \ 2
  t = t + 1
Wend
If minn = 0 Then
  minn = maxx - 2: maxx = maxx - 1
End If
End Sub
 
Function func() As Long
Dim i&, res&
If minn < 1 Then
  func = 0
Else
  res = minn
  For i = maxx - 1 To 2 Step -1
    res = res + i - 1
    func = res
  Next
End If
End Function
 
Sub main()
a = 0: b = 1000000000
col = 0
 proc a - 1
 col = col - func()
 proc b
 col = col + func()
Debug.Print col
End Sub
Но он же только для двух единиц работает, кажется



Цитата Сообщение от Catstail Посмотреть сообщение
а в каком типе данных ты хранишь такие целые?
Так вроде Long'а (макс=2.147483647E+9) вполне достаточно
1
15155 / 6428 / 1731
Регистрация: 24.09.2011
Сообщений: 9,999
01.11.2012, 23:37
Цитата Сообщение от Flaker Посмотреть сообщение
Разобрал твой пример, ... s = Oct(i) Только мне в двоичной надо)
Не разобрал, значит

Конечно, при больших b это задача на комбинаторику: b задает число "клеток" (разрядов двоичного числа), и задача сводится к тому, чтобы расставить заданное число единиц всеми способами в этих клетках, отбросив варианты, которые не попадают в диапазон a...b.
0
3 / 3 / 1
Регистрация: 07.07.2012
Сообщений: 90
01.11.2012, 23:53  [ТС]
Цитата Сообщение от Казанский Посмотреть сообщение
Не разобрал, значит
Хм... А ты не мог бы прокоментировать поподробней твой код тогда, пожалуйста, мне действительно важно разобраться с этим.




Цитата Сообщение от Казанский Посмотреть сообщение
варианты, которые не попадают в диапазон a...b.
А как можно определить попадает ли число в диапазон [a;b]?

Вот на пример:
a = 8
b = 50
k = 2

число есть 10010002. Вот как определить, входит ли оно в заданный диапазон?




Апострофф, ты не мог бы тоже расставить комментарии в коде, который ты перевел с Pascal. Спасибо большое кстати)
0
15155 / 6428 / 1731
Регистрация: 24.09.2011
Сообщений: 9,999
04.11.2012, 01:08
Цитата Сообщение от Flaker Посмотреть сообщение
А ты не мог бы прокоментировать поподробней твой код
Да не стОит его комментировать. Это скорее прикол, чем реальный код для решения этой задачи.
Да, в VB нет функции Bin, но есть Oct и Hex, которые возвращают текст, связанный с двоичным представлением числа. В коде полученное 8-ричное число разбивается на цифры (каждая цифра - 3 бита исходного числа) и к счетчику единиц прибавляется соотв. число.
Та же процедура с традиционным переводом числа в двоичный код с помощью целочисленного деления работает в ~2 раза быстрее:
Visual Basic
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
Sub bb1()
Dim a&, b&, k&, i&, j&, m&, n&
    'a - начало диапазона
    'b - конец диапазона
    'k - число единиц в двоичном представлении
    'i - счетчик цикла от a до b
    'j - переменная для перевода i в двоичное
    'm - счетчик чисел
    'n - счетчик единиц
Dim t!: t = Timer
'a = 10: b = 20: k = 2
a = 0: b = 1000000: k = 2
For i = a To b
    j = i
    n = 0
    While j
        If j Mod 2 Then n = n + 1: If n > k Then GoTo nxt_num
        j = j \ 2
    Wend
    If n = k Then m = m + 1
nxt_num:
Next
Debug.Print m, Timer - t
End Sub
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 по счету, в данном ниже коде)

Visual Basic
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
Option Explicit
Dim a, b, k, z, l, start, curPos, lastPos, statickNum As Double
Dim j As Double
Dim StartTimer As Double
Dim EndTimer As Double
 
Private Sub Command1_Click()
a = 10 'Ограничение снизу
b = 1500 'Ограничение сверху
k = 2  'Кол-во единиц требуется найти
l = 0
curPos = 0
StartTimer = Timer
 
For start = a To b
    statickNum = bin(start)
    j = statickNum
    l = 0
    curPos = 0
    While j
        curPos = curPos + 1
        If getMod(j, 10) = 1 Then
            l = l + 1
            If curPos <> Len(CStr(statickNum)) Then
                lastPos = curPos
            Else
            
            End If
        End If
        j = Int(j \ 10) 'Ошибка тут!!!!!!!!!!!!!!!!!!!!!!!!!!!
    Wend
Next start
EndTimer = Timer
 
Print "Execution time in seconds: ", EndTimer - StartTimer
End Sub
P.S. Если нужен вобще поолный код, могу предоставить...
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
Написал рекурсивную функцию для перебора комбинаций бит
код модуля с функцией
Visual Basic
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
Option Explicit
 
Dim bitVal&(0 To 30), e&(), n&, m&, aa&, bb&, kk&
 
    'bitVal - "вес" соотв. бита: bitVal(0)=1, bitVal(1)=2, bitVal(2)=4 и т.д.
    'e - позиции единиц, перебираются в циклах
    'N - позиция старшего бита числа b
    'm - счетчик чисел
    'aa&, bb&, kk& - дубликаты a,b,k на уровне модуля
 
Function Flaker&(a&, b&, k&)
'Возващает количество чисел в интервале a...b,
'которые содержат k единиц в двоичной записи
 
'Dim i&, j&, k&
 
'заполняем массив bitVal и одновременно определяем N
bitVal(0) = 1
For n = 1 To 30
    bitVal(n) = bitVal(n - 1) * 2
    If bitVal(n) > b Then
        n = n - 1: Exit For
    ElseIf bitVal(n) = b Then Exit For
    End If
Next
If n = 31 Then n = 30
'подготавливаем запуск рекурсивной процедуры
aa = a: bb = b: kk = k
ReDim e(0 To k)
e(0) = n + 1
m = 0
MoveBit 1, 0
Flaker = m
End Function
 
Private Function MoveBit(nBit&, sum&) As Boolean
'процедура передвигает в цикле бит с номером nBit
'и прибавляет "вес" соотв. бита к числу (сумме бит)
'возвращает True, если число превысило b, т.е. конец счета
 
Dim i&, j&
If nBit < kk Then 'не последний бит
    For e(nBit) = kk - nBit To e(nBit - 1) - 1
        If MoveBit(nBit + 1, sum + bitVal(e(nBit))) Then _
            MoveBit = True: Exit Function
    Next
Else 'последний бит
    For e(nBit) = kk - nBit To e(nBit - 1) - 1
        i = sum + bitVal(e(kk))
        If i >= aa Then
            If i <= bb Then
                m = m + 1
            Else: MoveBit = True: Exit Function
            End If
        End If
    Next
'        For i = 1 To k: Debug.Print e(i);: Next
'        Debug.Print , r + 2 ^ (e(k))
'    Next
End If
End Function
Скорость работы зависит не столько от величины чисел a и b, сколько от числа единиц. Вот тест нахождения кол-ва чисел с разным числом единиц в диапазоне от миллиарда до макс. числа типа Long:
Visual Basic
1
2
3
4
5
6
7
8
9
Sub test1()
Dim i&, t!
Debug.Print "число ед.", "кол-во чисел", "время, сек (P3-500)"
For i = 1 To 31 ' Step -1
    t = Timer
    Debug.Print i, Flaker(1000000000, 2147483647, i), Timer - t
        '2147483647 =2^31-1, макс. число типа Long
Next
End Sub
Результаты
Code
1
2
3
4
5
6
7
8
9
10
11
число ед.     кол-во чисел  время, сек (P3-500)
 1             1             0 
 2             30            0 
 3             435           0 
 4             4061          0,03125 
 5             27431         0,1914063 
 6             142831        0,9492188 
 7             596377        3,726563 
 8             2050793       12,17969 
 9             5919147       34,28125 
 10            14540269      82,27734
Если запустить в обратную сторону
Code
1
2
3
4
5
6
7
8
9
10
число ед.     кол-во чисел  время, сек (P3-500)
 31            1             0 
 30            31            0 
 29            462           1,171875E-02 
 28            4408          0,0703125 
 27            30258         0,390625 
 26            159225        1,753906 
 25            668370        6,367188 
 24            2299299       19,60156 
 23            6609398       51,92578
Также погонял сравнение результатов этой функции и "тривиальной" в диапазоне a,b до миллиона:
код модуля с "тривиальной" функцией и тестовой процедурой
Visual Basic
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
Function Fl1(a&, b&, k&)
Dim i&, j&, m&, n&
    'a - начало диапазона
    'b - конец диапазона
    'k - число единиц в двоичном представлении
    'i - счетчик цикла от a до b
    'j - переменная для перевода i в двоичное
    'm - счетчик чисел
    'n - счетчик единиц
'Dim t!: t = Timer
'a = 10: b = 20: k = 2
'a = 0: b = 1000000: k = 2
For i = a To b
    j = i
    n = 0
    While j
        If j Mod 2 Then n = n + 1: If n > k Then GoTo nxt_num
        j = j \ 2
    Wend
    If n = k Then m = m + 1
nxt_num:
Fl1 = m
Next
'Debug.Print m, Timer - t
End Function
 
Sub test()
Const L& = 1000000
Dim a&, b&, i&, j&, k&, m&, n&
 
Do
    a = Rnd * L \ 2
    b = a + Rnd * (L - a)
    k = 1 + Int(Rnd * 10)
    i = Fl1(a, b, k)
    j = Flaker(a, b, k)
    Debug.Print a, b, k, i, j
    If i <> j Then Stop
Loop
    
End Sub
Результаты совпадают.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
10.11.2012, 15:17
Помогаю со студенческими работами здесь

Вывести все натуральные числа, не превосходящие N, в двоичной записи которых К единиц
помогите пожалуйста!!!! На вас одна надежда!!! Сессия горит

Найти количество единиц в двоичной записи числа
#include &lt;iostream&gt; # include&lt;stdio.h&gt; #include&lt;conio.h&gt; using namespace std; int Count(unsigned a) { return a ? (a &amp; 1) +...

Среди простых чисел найти те, в двоичной записи которых максимальное число единиц
среди простых чисел не превосходящих N найти такие в двоичной записи которых максимальное число единиц

Найти количество чисел от 1 до N, у которых места единиц в двоичной записи образуют арифметическую прогрессию
Найти количество чисел от 1 до N, у которых места единиц в двоичной записи образуют арифметическую прогрессию. Ограничение по времени на...

Вывести все десятичные числа, в двоичной записи которых число нулей на 2 превосходит число единиц
Есть вот такая прога на Си, которая выводит все десятичные числа, в двоичной записи которых число нулей на 2 превосходит число единиц. ...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
13
Ответ Создать тему
Новые блоги и статьи
Знаешь почему 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
Алгоритм из решения ниже применим как для типовых, так и для нетиповых документов на самых различных конфигурациях. Задача: при копировании документа очищать определенные реквизиты и табличную. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru