Ранее я задавал этот вопрос:
Рассмотрим сетку целых чисел размером n на n. Задача состоит в том, чтобы провести прямую линию через сетку так, чтобы сумма частей, включающих верхний левый угол, давала максимально возможное число. Вот изображение оптимального решения с оценкой 45:
Квадрат включаем в суммируемую часть, если его середина находится выше или на линии. «Выше» означает часть, включающую верхний левый угол сетки. (Чтобы прояснить это определение, отметим, что ни одна линия не может начинаться точно в верхнем левом углу сетки.)
Задача — выбрать линию, максимизирующую сумму части, включающей верхний левый квадрат. Линия должна идти прямо от одной стороны к другой. Линия может начинаться или заканчиваться в любом месте стороны, а не только в целых точках.
Был приведен код, который находит оптимальную оценку.
импортировать numpy как np импортные фракции защита best_line (сетка): п, м = сетка.форма D = [(di, dj) для di в диапазоне(-(n - 1), n) для dj в диапазоне(-(n - 1), n)] наклон наклона (d): ди, dj = d если dj == 0: вернуть float('inf'), если di
