Python циклы, массивы

Question

Python циклы, массивы

Маргарита Просвирнова Знаток (251), на голосовании 1 год назад

Добрый день.
Помогите пожалуйста с задаче! Понимаю, как решить, но не понимаю как код написать

В одном городе на Земле живут Циклопы (мифические существа с одним глазом). У большинства Циклопов есть проблемы со зрением, поэтому им рекомендовано носить контактные линзы. При этом, если Циклопу рекомендовано ношение линз в К диоптрий, его устроят линзы в К-1, К, К+1 диоптрии. Циклопы очень боятся, что о них узнают люди, поэтому заказывают линзы в обычных человеческих магазинах парами одинаковой оптической силы. Один Циклоп решил собирать заказы и оптимизировать процесс закупки линз так, чтобы покупать как можно меньше пар, при этом удовлетворить все поступившие заказы.
Требуется написать алгоритм на любом языке программирования, выводящий минимальное количество пар, необходимых для удовлетворения всех поступивших заказов.
Например, для 5-ти Циклопов с диоптриями [1, -1, 2, З, -3], достаточно купить З пары линз (О диоптрий удовлетворят 1-го и 2-го Циклопов, 2 или З диоптрия удовлетворят 3-го и 4-го Циклопов, -2 или -3 или -4 диоптрии удовлетворят 5-го Циклопа, но 1 линза будет не задействована —это нормально).

Начала так:
n = int(input("Кол-во циклопов: "))
from random import randint
N = sorted([randint(-6, 6) for x in range(n)]*2) # Длина массива равна количеству циклопов *2, т.к. в очках по 2 линзы
print("Все линзы: ", N)

Дальше, по логике так:
Циклопу нужна только одна линза из пары, значит, оставшаяся линза может подойти следующему циклопу из списка.
Сравниваем значение рекомендованной ему линзы со значением рекомендованной линзы для предыдущего циклопа. Если разница между ними не больше двух, то одна пара линз подойдёт для обоих циклопов. Счётчик должен увеличится на единицу, чтобы не посчитать повторно "следующего" циклопа на следующей итерации цикла.
Если разница между значениями рекомендованных линз больше двух, то для второго циклопа в сравниваемой паре циклопов уже не подходит линза и переходим к рассмотрению уже его и следующего за ним циклопа.

Но как написать код?

Answer 1

Есть один тут человек..
Попробую ему ссылку передать

Answer 2

GPT4:
Прежде всего, у вас есть хороший набросок алгоритма, и я помогу вам сформулировать его в виде кода. Вот один из возможных способов написания алгоритма на Python:
def min_lens_pairs(dioptries):
dioptries = sorted(dioptries)
count = 0
i = 0
while i < len(dioptries):
count += 1
curr_dioptrie = dioptries[i]
while i < len(dioptries) and dioptries[i] <= curr_dioptrie + 2:
i += 1
return count

n = int(input("Кол-во циклопов: "))
from random import randint
dioptries = [randint(-6, 6) for x in range(n)]
print("Диоптрии для циклопов: ", dioptries)

result = min_lens_pairs(dioptries)
print("Минимальное количество пар линз: ", result)

Этот код сначала сортирует список диоптрий, затем итерирует по нему, находит подходящие линзы для каждого Циклопа и учитывает их в счетчике. Если очередной Циклоп может использовать линзы, подходящие для предыдущего, алгоритм учитывает это, и счетчик не увеличивается.

Обратите внимание, что я изменил переменную N на dioptries для лучшей читаемости и убрал умножение на 2, так как вам нужно просто учесть диоптрии для каждого Циклопа, а не количество линз.