Помогите сформировать массив целых чисел А

Question

Задача следующая: нужно сформировать массив целых чисел A[100] в возрастающем порядке множества М, который определяется такими правилами:

1 принадлежит М. Если х принадлежит М, то числа y=2x+1 и z=3x+1 также принадлежат M. Никакое другое число не принадлежит М

Проблема в том, что если решать задачу "в лоб", то последовательность возрастающей не будет: 1, 3, 4, 7, 10, 9, 13... Также нельзя сортировать массив. Есть какие-то идеи, как это сделать максимально эффективно?

Answer 1

Последовательность будет возрастающей если ррешая в лоб вы не будите добавлять элементы которые не удовлетворяют условию возрастания. По сути вам нужно сравнивать последний полученный с последним добавленным. Ведь в задаче не говориться добавить все полученные. Добавить числа удовлетворяющие условию.

Answer 2

ну можно решить в лоб -

arr = []
i = 1

while len(arr) < 100:
    if is_M(i) is True:
        arr.append(i)
        
    i += 1

т.е. последовательно перебираем все натуральные числа и проверяем - являются ли они членами множества М

ну а проверить число - является ли оно элементом множества гораздо проще, чем находить такие числа - например, надо просто обратно до 1 спуститься

самый простой алгоритм проверки - рекурсивный в лоб с 2 ветками

например, весь код может быть таким:

def is_M(i):
  if i == 1:
    return True

  value = i - 1
    
  if value % 2 == 0 and is_M(value // 2) is True:
    return True

  if value % 3 == 0 and is_M(value // 3) is True:
    return True

  return False


arr = []
i = 1

while len(arr) < 100:
    if is_M(i) is True:
        arr.append(i)

    i += 1

print(arr)

Answer 3

Создаёте очередь по приоритетам
Вставляете в неё 1
Пока не набрали нужный результат:
    Извлекли минимум x
    Вставили в очередь 2x+1 и 3x+1
    Добавили x к результату

БЛОГ НА HUSL

Помогите сформировать массив целых чисел А

Ответы (3 шт):