Задача следующая: нужно сформировать массив целых чисел A[100] в возрастающем порядке множества М, который определяется такими правилами:
1 принадлежит М. Если х принадлежит М, то числа y=2x+1 и z=3x+1 также принадлежат M. Никакое другое число не принадлежит М
Проблема в том, что если решать задачу "в лоб", то последовательность возрастающей не будет: 1, 3, 4, 7, 10, 9, 13... Также нельзя сортировать массив. Есть какие-то идеи, как это сделать максимально эффективно?
ну можно решить в лоб -
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)
Создаёте очередь по приоритетам
Вставляете в неё 1
Пока не набрали нужный результат:
Извлекли минимум x
Вставили в очередь 2x+1 и 3x+1
Добавили x к результату
Последовательность будет возрастающей если ррешая в лоб вы не будите добавлять элементы которые не удовлетворяют условию возрастания. По сути вам нужно сравнивать последний полученный с последним добавленным. Ведь в задаче не говориться добавить все полученные. Добавить числа удовлетворяющие условию.
