Бесцельно напрягая мозг

[shoorick]

Зачем образование я в муках получал?

Тимур Шаов

Разнообразия ради (чтоб мозги не заплесневели) пытаюсь решить задачку: дано c звёздочек, хочется их разместить, как на американском флаге: в n рядов и m столбцов, а в промежутках — ещё (n−1)·(m−1). Задача сводится к целочисленному решению уравнения
(n−1)·(m−1) + n·m = c
Кроме того, что (n−1)·(m−1) + n·m = 2·n·m−n−m+1 — нифига не помню. Зачем мне целый семестр читали дискретное программирование? Всё равно кроме полного перебора ничего не придумывается...

исходя из условий задачи, получаем:
n ∈ ℕ
m ∈ ℕ
2 ≤ n ≤ (c+1)/3
2 ≤ m ≤ (c+1)/3

А дальше — никак. Опять хочется полный перебор устроить...

Comments

[golub.livejournal.com]

Экий же ты затейник :)

Я что-то не очень понял, что в задаче дано, а что найти. Чего ты ищешь-то - n и m?

[yurikl.livejournal.com]

а если бы была задача по проще - просто разместить в n рядов и m столбцов (без промежутков), то как бы решал? Вроде только полный перебор (ищем хоть один делитель c). А здесь почти тоже самое.

Если проще

[shoorick.livejournal.com]

Ну когда просто разместить в n×m — не трудно: найти все делители (это, кстати, не полный перебор — есть достаточно простой алгоритм), а потом остаётся лишь попробовать сочетания...

Re: Если проще

[yurikl.livejournal.com]

как это не полный перебор? ну, может быть, и не полный (можно напрячься и подсократить его), но всё равно перебор ;). Эффективно искать делители пока не научились. И не факт, что научимся.

[oless.livejournal.com]

/воодушевленно исписывая решениями третий лист формата А4/

Если есть хоть какая-то зависимость между n и m, то систему из 2 уравнений с тремя неизвестными можно решить, зная, что m и n положительные целые числа, но если это одно уравнение с тремя неизвестными - кроме как перебором, я не знаю, как.

2 неизвестных

[shoorick.livejournal.com]

Неизвестных всего две: n и m.
c — это константа.

Re: 2 неизвестных

[oless.livejournal.com]

А!
Вот оно что!

Тогда я решу, как время появится, путем замены переменной.

Смотря какое c

[shoorick.livejournal.com]

Перебрал варианты с 1≤n-1≤8 и 1≤m-1≤8
При c=30 задача не имеет целочисленного решения.
Пришлось вместо звёздочек нарисовать шарики :-)

[oless.livejournal.com]

Я сидел, ломал мозг целый вечер, привлек жену, по образованию математика, вот что надумал:
Чтобы было без перебора надо добавить зависимость между n и m, например - ширина флага минимум в 2 раза больше высоты.
Тогда n>=m/2
Выражаем из равенства m через n, подставляем в неравенство.
Приводим всё к квадратному неравенству, решаем.

хе-хе

[oless.livejournal.com]

Для тридцати не имеет, надо было 29 сделать и одну звезду поверх )

[logicz.livejournal.com]

Начнём с того, что без конкретного С задача не имеет смысла.
Далее в подавляющем большинстве случаев звёздочек может не хватить на такое размещение, но тогда тебя может быть устраивает и не до конца замощённая, наиболее близкая к идеальному замощению?
Третье, не имеет смысла (я так думаю) решение, когда n > 3m или 3n > m

А что если тебе развернуть задачу? Скажем надо замостить площадь m*n по указаной схеме и сколько звёздочек понадобиться? Тогда у тебя уже есть готовая формула.