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

[shoorick]

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

Comments

[golub]

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

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

[yurikl]

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

Если проще

[shoorick]

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

Re: Если проще

[yurikl]

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

[oless]

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

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

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

[shoorick]

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

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

[oless]

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

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

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

[shoorick]

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

[logicz]

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

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