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

@mv-alexeenko · Регистрация: 18.05.2021

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

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

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

Ограничение на вывод 1 сек.
Можно использовать только пройденный материал - написание функций и использование множества не допускаются.
Все до 400-го элемента укладывается в заданные временные рамки, 500 - й элемент ищет за 2,5 секунды, 1000 - й за 2,5 минуты, как можно ускорить? Или есть другой вариант поиска последовательности Хемминга? Прошу не отсылать на готовые варианты кода, например этот по скорости уступает моему.

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import time
n = int(input())
start = time.time()
c = 1
n1 = 0
n3 = 0
while True:
    if n1 == n:
        break
    n2 = 0
    c += 1
    for i in range(1, int(c ** 0.5) + 1):
        if c % i == 0 and ((i % 2 != 0 and i % 3 != 0 and i % 5 != 0 and i != 1)
                           or (((c // i) % 2 != 0) and ((c // i) % 3 != 0) and ((c // i) % 5 != 0))):
            n2 += 1
            break
    if n2 != 0:
        continue
    n3 = c
    n1 += 1
end = time.time()
print(n3, end-start)

Добавлено через 50 минут
Не знаю, как изменить сообщение в теме. Особая благодарность Вадиму Тукаеву, его код натолкнул на мысль. Простота в понимании последовательности Хемминга. Вот код который удовлетворяет всем условиям:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
n = int(input())
# start = time.time()
s = list(range(2, 6))
n1 = 0
while n1 < n:
    n2 = min(s)
    s.remove(n2)
    # n1 += [n2]
    n1 += 1
    for i in range(2, 6):
        if n2 * i not in s:
            s.append(n2 * i)
# n1.sort()
# end = time.time()
print(n2)

@Red white socks · 20.12.2022, 13:20

Хороший алгоритм.

Новые блоги и статьи Все статьи Все блоги /
Оттенки серого 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),. . .	[Owen Logic] Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ФедосеевПавел 14.03.2026 Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ВВЕДЕНИЕ Выполняя задание на управление насосной группой заполнения резервуара,. . .
делаю науч статью по влиянию грибов на сукцессию anaschu 13.03.2026 прикрепляю статью	SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .	Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .

@Red white socks 4523 / 1899 / 336 Регистрация: 18.01.2021 Сообщений: 3,489
	20.12.2022, 13:20
	Хороший алгоритм. 0