Математический форум Math Help Planet
Обсуждение и решение задач по математике, физике, химии, экономике Теоретический раздел |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
новый онлайн-сервис число, сумма и дата прописью |
|
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Страница 1 из 1 |
[ Сообщений: 5 ] |
|
Автор | Сообщение | |
---|---|---|
AZbest |
|
|
Жадный алгоритм не дает нужного резльтата. Нарпимер для прямоугольника 5 на 6 по жадному дает 6 штук (1 - 5х5 и 5 - 1х1). Но можно всего на 5 (2 - 3х3 и 3 - 2х2). Есть книга И.М. Яглома "Как разрезать квадрат", но там подобного ничего нет. Заранее спаасибо. |
||
Вернуться к началу | ||
FEBUS |
|
|
Нет никакого универсального способа. Для каждого прямоугольника своё решение.
Схема решения одна: привести пример разбиения и доказать, что на меньшее число разбить нельзя. AZbest писал(а): Жадный алгоритм не дает нужного резльтата. Это неверно. Например, для прямоугольника [math]\;6 \times 8[/math], как раз жадный даёт минимум. |
||
Вернуться к началу | ||
swan |
|
|
Интересует как математическая или вычислительная задача? В книге Яглома рассказан базовый подход к проблеме, связь с электрическими цепями и приведены оценки. Есть несколько книг/статей, где теория рассказывается на более продвинутом уровне (очень сложном) но, так как у Яглома не нашли ничего полезного, то видимо вас теория не интересует.
Тогда стоит предположить, что вам нужно вычислить точное значение для некоторого данного прямоугольника. Можно попробовать решить как задачу динамического программирования: прямоугольник разбить на два прямоугольника меньшего размера и искать наименьшее разбиение для них. Если вы видите здесь проблемы, то посвятите нас в них, расскажите чего достигли и с какими препятствиями столкнулись. Upd. Сейчас вижу, что данный подход не гарантирует минимальности, но разбиений будет гораздо меньше, чем при жадном |
||
Вернуться к началу | ||
AZbest |
|
|
FEBUS писал(а): Например, для прямоугольника 6×8 , как раз жадный даёт минимум. такой прямоугольник идентичен 3x4, для данной задачи если соотношение сторон можно сократить, то минимальное количество квадратов у них равно. если сторона больше ~1,5 раза, то первое приближения жадина дает правильное. Хуже дела обстоят когда длины числа большие и близкие. |
||
Вернуться к началу | ||
AZbest |
|
|
swan писал(а): Интересует как математическая или вычислительная задача? как вычислительная, а точнее хочу запрограммировать. Перебор - метод хороший, но медленный)) Динамическим программироваем тоже не очень, потому что нет алгоритма решения для задачи в общем виде для подзадач с меньшим прямоугольником. Думал что у, на первый взгляд, простой формулировке задачи есть не менее простое решение... |
||
Вернуться к началу | ||
[ Сообщений: 5 ] |
Похожие темы | Автор | Ответы | Просмотры | Последнее сообщение |
---|---|---|---|---|
Минимальное количество методов
в форуме Комбинаторика и Теория вероятностей |
10 |
699 |
26 фев 2018, 12:38 |
|
Задачка на минимальное количество шагов | 38 |
1823 |
17 июн 2015, 03:44 |
|
Минимальное количество функций для критерия Поста | 1 |
307 |
07 янв 2017, 03:51 |
|
Минимальное количество граней торическогого многогранника | 0 |
235 |
16 авг 2018, 00:05 |
|
Построить окружность за минимальное количество линий | 14 |
220 |
06 мар 2024, 04:54 |
|
Прямоугольник вписан в другой прямоугольник. Найти размеры
в форуме Геометрия |
5 |
1037 |
11 июл 2014, 10:39 |
|
Выбрать прямоугольник для вписывания в другой прямоугольник
в форуме Геометрия |
7 |
879 |
25 авг 2015, 12:17 |
|
Метод наименьших квадратов; почему именно квадратов?
в форуме Численные методы |
17 |
3038 |
04 апр 2015, 15:19 |
|
Минимальное кол-во цветов в квадрате 6х6
в форуме Комбинаторика и Теория вероятностей |
2 |
118 |
19 июл 2023, 15:10 |
|
Минимальное значение выражения | 14 |
514 |
02 мар 2019, 20:37 |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Кто сейчас на конференции |
Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 5 |
Вы не можете начинать темы Вы не можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете добавлять вложения |