Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 5 ] 
Автор Сообщение
 Заголовок сообщения: Разделить прямоугольник на минимальное количество квадратов
СообщениеДобавлено: 28 авг 2020, 23:42 
Не в сети
Начинающий
Зарегистрирован:
01 янв 2015, 23:40
Сообщений: 7
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Кто-то встречал или может помочь в поиске способа решения задачи разделения прямоугольника на минимальное количество квадратов.
Жадный алгоритм не дает нужного резльтата. Нарпимер для прямоугольника 5 на 6 по жадному дает 6 штук (1 - 5х5 и 5 - 1х1). Но можно всего на 5 (2 - 3х3 и 3 - 2х2).
Есть книга И.М. Яглома "Как разрезать квадрат", но там подобного ничего нет.
Заранее спаасибо.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Разделить прямоугольник на минимальное количество квадратов
СообщениеДобавлено: 29 авг 2020, 00:55 
Не в сети
Beautiful Mind
Аватара пользователя
Зарегистрирован:
01 мар 2018, 02:28
Сообщений: 1309
Cпасибо сказано: 294
Спасибо получено:
363 раз в 299 сообщениях
Очков репутации: 2

Добавить очки репутацииУменьшить очки репутации
Нет никакого универсального способа. Для каждого прямоугольника своё решение.
Схема решения одна: привести пример разбиения и доказать, что на меньшее число разбить нельзя.

AZbest писал(а):
Жадный алгоритм не дает нужного резльтата.

Это неверно.
Например, для прямоугольника [math]\;6 \times 8[/math], как раз жадный даёт минимум.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Разделить прямоугольник на минимальное количество квадратов
СообщениеДобавлено: 29 авг 2020, 06:28 
Не в сети
Последняя инстанция
Зарегистрирован:
06 дек 2014, 09:11
Сообщений: 7070
Cпасибо сказано: 115
Спасибо получено:
1662 раз в 1508 сообщениях
Очков репутации: 283

Добавить очки репутацииУменьшить очки репутации
Интересует как математическая или вычислительная задача? В книге Яглома рассказан базовый подход к проблеме, связь с электрическими цепями и приведены оценки. Есть несколько книг/статей, где теория рассказывается на более продвинутом уровне (очень сложном) но, так как у Яглома не нашли ничего полезного, то видимо вас теория не интересует.
Тогда стоит предположить, что вам нужно вычислить точное значение для некоторого данного прямоугольника. Можно попробовать решить как задачу динамического программирования: прямоугольник разбить на два прямоугольника меньшего размера и искать наименьшее разбиение для них. Если вы видите здесь проблемы, то посвятите нас в них, расскажите чего достигли и с какими препятствиями столкнулись.
Upd. Сейчас вижу, что данный подход не гарантирует минимальности, но разбиений будет гораздо меньше, чем при жадном

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Разделить прямоугольник на минимальное количество квадратов
СообщениеДобавлено: 29 авг 2020, 22:08 
Не в сети
Начинающий
Зарегистрирован:
01 янв 2015, 23:40
Сообщений: 7
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
FEBUS писал(а):
Например, для прямоугольника 6×8
, как раз жадный даёт минимум.

такой прямоугольник идентичен 3x4, для данной задачи если соотношение сторон можно сократить, то минимальное количество квадратов у них равно.

если сторона больше ~1,5 раза, то первое приближения жадина дает правильное.
Хуже дела обстоят когда длины числа большие и близкие.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Разделить прямоугольник на минимальное количество квадратов
СообщениеДобавлено: 29 авг 2020, 22:12 
Не в сети
Начинающий
Зарегистрирован:
01 янв 2015, 23:40
Сообщений: 7
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
swan писал(а):
Интересует как математическая или вычислительная задача?

как вычислительная, а точнее хочу запрограммировать. Перебор - метод хороший, но медленный))
Динамическим программироваем тоже не очень, потому что нет алгоритма решения для задачи в общем виде для подзадач с меньшим прямоугольником.

Думал что у, на первый взгляд, простой формулировке задачи есть не менее простое решение...

Вернуться к началу
 Профиль  
Cпасибо сказано 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему      Страница 1 из 1 [ Сообщений: 5 ]

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Минимальное количество методов

в форуме Комбинаторика и Теория вероятностей

an2ancan

10

699

26 фев 2018, 12:38

Задачка на минимальное количество шагов

в форуме Интересные задачи участников форума MHP

Abra-Kadabra

38

1823

17 июн 2015, 03:44

Минимальное количество функций для критерия Поста

в форуме Дискретная математика, Теория множеств и Логика

igor89

1

307

07 янв 2017, 03:51

Минимальное количество граней торическогого многогранника

в форуме Аналитическая геометрия и Векторная алгебра

numitus

0

235

16 авг 2018, 00:05

Построить окружность за минимальное количество линий

в форуме Интересные задачи участников форума MHP

ferma-T

14

220

06 мар 2024, 04:54

Прямоугольник вписан в другой прямоугольник. Найти размеры

в форуме Геометрия

Germm

5

1037

11 июл 2014, 10:39

Выбрать прямоугольник для вписывания в другой прямоугольник

в форуме Геометрия

Rest

7

879

25 авг 2015, 12:17

Метод наименьших квадратов; почему именно квадратов?

в форуме Численные методы

tushkan

17

3038

04 апр 2015, 15:19

Минимальное кол-во цветов в квадрате 6х6

в форуме Комбинаторика и Теория вероятностей

McMurphy

2

118

19 июл 2023, 15:10

Минимальное значение выражения

в форуме Задачи со школьных и студенческих олимпиад

Fediono

14

514

02 мар 2019, 20:37


Часовой пояс: UTC + 3 часа [ Летнее время ]



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 5


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2023 MathHelpPlanet.com. All rights reserved