Дискуссионный математический форумМатематический форум
Математический форум 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
Сообщений: 1282
Cпасибо сказано: 286
Спасибо получено:
345 раз в 283 сообщениях
Очков репутации: 8

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

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

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Разделить прямоугольник на минимальное количество квадратов
СообщениеДобавлено: 29 авг 2020, 06:28 
Не в сети
Light & Truth
Зарегистрирован:
06 дек 2014, 09:11
Сообщений: 5658
Cпасибо сказано: 87
Спасибо получено:
1229 раз в 1122 сообщениях
Очков репутации: 242

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

504

26 фев 2018, 12:38

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

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

Abra-Kadabra

38

1549

17 июн 2015, 03:44

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

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

numitus

0

152

16 авг 2018, 00:05

Прозвонка многожильного кабеля за минимальное количество раз

в форуме Начала анализа и Другие разделы школьной математики

Talanov

14

1756

10 фев 2012, 07:25

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

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

igor89

1

167

07 янв 2017, 03:51

Какое минимальное количество опытов нужно провести

в форуме Теория вероятностей

An1974

9

1321

06 ноя 2010, 10:36

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

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

Germm

5

487

11 июл 2014, 10:39

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

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

Rest

7

571

25 авг 2015, 12:17

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

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

tushkan

17

1798

04 апр 2015, 15:19

Найти минимальное ДНФ

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

Jack-shade

30

1765

29 май 2011, 18:09


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



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

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


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

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

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

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