Задача Последовательность Хэмминга

@kroshkamyshka · Регистрация: 23.01.2022

Студворк — интернет-сервис помощи студентам

Добрый день! Программа не удовлетворяет условию: Ограничение времени 1 секунда
Задача:
Если числа имеют среди делителей только 2, 3 и 5 в любой степени, то, расположенные по возрастанию, они образуют последовательность Хэмминга. Выведите n-е число последовательности.

Первые 10 чисел такие: 2, 3, 4, 5, 6, 8, 9, 10, 12, 15.
мой код:

Python
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
def hamming(x):
    if x == 1:
        return 1
    if x % 2 == 0:
        return hamming(x / 2)
    if x % 3 == 0:
        return hamming(x / 3)
    if x % 5 == 0:
        return hamming(x / 5)
    
    
def hamnum(x):
    if x == 1:
        return 1
    if hamming(x):
        return x
    return 0
 
 
a = set()
n = int(input())        
for i in range(1, 100000):
    a.add(hamnum(i))
a = sorted(list(a))
del a[0]
del a[0]
print(a[n - 1])

Помогите доработать код, пожалуйста

@Gdez · 09.02.2022, 18:47

kroshkamyshka, Напечатайте в порядке возрастания первые 1000 чисел, которые не имеют простых делителей кроме 2 3 5

@миша100 · 12.12.2025, 17:13

Мой учитель по информатике решил эту задачу так

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
n = int(input())
counter = 1
d = 2
while counter < n:
    d += 1
    k = d
    while k % 2 == 0:
        k //= 2
    while k % 3 == 0:
        k //= 3
    while k % 5 == 0:
        k //= 5
    if k == 1:
        counter += 1
print(d)

@Catstail · 13.12.2025, 06:23

миша100, алгоритмически это решение правильное, но при больших n работать будет страшно долго

Новые блоги и статьи Все статьи Все блоги /
1С: Программный отбор элементов справочника по группе Maks 22.03.2026 Установка программного отбора элементов справочника "Номенклатура" из модуля формы документа. В качестве фильтра для отбора справочника служит группа номенклатуры. Отбор по наименованию группы. . .	Как я обхитрил таблицу Word Alexander-7 21.03.2026 Когда мигает курсор у внешнего края таблицы, и нам надо перейти на новую строку, а при нажатии Enter создается новый ряд таблицы с ячейками, то мы вместо нервных нажатий Энтеров мы пишем любые буквы. . .	Krabik - рыболовный бот для WoW 3.3.5a AmbA 21.03.2026 без регистрации и смс. Это не торговля, приложение не содержит рекламы. Выполняет свою непосредственную задачу - автоматизацию рыбалки в WoW - и ничего более. Однако если админы будут против -. . .	1С: Программный отбор элементов справочника по значению перечисления Maks 21.03.2026 Установка программного отбора элементов справочника "Сотрудники" из модуля формы документа. В качестве фильтра для отбора служит предопределенное значение перечислений. Процедура. . .
Переходник USB-CAN-GPIO Eddy_Em 20.03.2026 Достаточно давно на работе возникла необходимость в переходнике CAN-USB с гальваноразвязкой, оный и был разработан. Однако, все меня терзала совесть, что аж 48-ногий МК используется так тупо: просто. . .	Оттенки серого Argus19 18.03.2026 Оттенки серого Нашёл в интернете 3 прекрасных модуля: Модуль класса открытия диалога открытия/ сохранения файла на Win32 API; Модуль класса быстрого перекодирования цветного изображения в оттенки. . .	SDL3 для Desktop (MinGW): Рисуем цветные прямоугольники с помощью рисовальщика SDL3 на Си и C++ 8Observer8 17.03.2026 Содержание блога Финальные проекты на Си и на C++: finish-rectangles-sdl3-c. zip finish-rectangles-sdl3-cpp. zip	Символические и жёсткие ссылки в Linux. algri14 15.03.2026 Существует два типа ссылок — символические и жёсткие. Ссылка в Linux — это запись в каталоге, которая может указывать либо на inode «файла-ИСТОЧНИКА», тогда это будет «жёсткая ссылка» (hard link),. . .

@Gdez 8851 / 4502 / 1864 Регистрация: 27.03.2020 Сообщений: 7,317
	09.02.2022, 18:47
	kroshkamyshka, Напечатайте в порядке возрастания первые 1000 чисел, которые не имеют простых делителей кроме 2 3 5 0

@Catstail Супер-модератор 38193 / 21126 / 4309 Регистрация: 12.02.2012 Сообщений: 34,732 Записей в блоге: 14
	13.12.2025, 06:23
	миша100, алгоритмически это решение правильное, но при больших n работать будет страшно долго 0