рекурсия- разбиение и сборка квадрата |
1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!
рекурсия- разбиение и сборка квадрата |
Екатерина7 |
Сообщение
#1
|
Новичок Группа: Пользователи Сообщений: 43 Пол: Женский Репутация: 0 |
помогите, пожалуйста, разобраться с задачей
Лист бумаги в клетку квадратной формы размера NxN произвольно разрезан на прямоугольные части, каждая из которых имеет целое число клеток. Полученные прямоугольные куски перемешаны. Требуется из заданных прямоугольников снова составить квадрат. Квадрат не обязательно должен быть составлен из прямоугольников в том же порядке, в каком он разрезан. При сборке прямоугольники можно поворачивать. (число N не задано, можно брать любое) |
Unconnected |
Сообщение
#2
|
mea culpa Группа: Пользователи Сообщений: 1 372 Пол: Мужской Реальное имя: Николай Репутация: 24 |
А как входные данные выглядят?
-------------------- "Знаешь, стыдно - когда не видно, что услышал всё, что слушал.."
|
Гость |
Сообщение
#3
|
Гость |
может входными данными могут быть массивы этих прямоугольников,состоящие из клеточек?
|
Lapp |
Сообщение
#4
|
Уникум Группа: Пользователи Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
может входными данными могут быть массивы этих прямоугольников,состоящие из клеточек? Unconnected верно заметил - в этой проге подготовка входных данных - это, считай, отдельная задача. Собственно, я поэтому посоветовал именно такое название для этой темы.. )) Но об этом потом.Общая стратегия состоит в том, что мы (используя полный перебор, организованный рекурсией) набрасываем прямоугольники из имеющегося у нас набора на квадрат, а в процессе этого смотрим, пересекаются они или нет. Если мы находим такое их распределение, что они не пересекаются - все, задача решена. Так что нам нужно уметь делать - смотреть, пересекаются ли два определенных прямоугольника. Представлений информации в этой задаче может быть несколько. Во-первых, сам прямоугольник может быть представлен своими размерами: длиной и шириной. Затем, есть по крайней мере два способа привязать прямоугольник к координатной сетке (то есть "положить"). Первое, что приходит в голову - сразу завести массив NxN скажем, из целых, и каждую клетку помечать номером того прямоугольника разбиения, к которому она принадлежит. Этот способ требует довольно много памяти.. А другой подход состоит в том, чтобы задавать прямоугольник координатами его двух противоположных вершин либо координатами одной вершины (с минимальными координатами) плюс все те же длина и ширина. Итак, давай остановимся на следющем. Каждый прямоугольник сам по себе обозначаем длиной и ширинойобозначаем по двум противоположным углам (вершинам). Таким образом, прямоугольник представляется переменной такого типа: type, где lx - размер по x, а ly - размер по y, а x,y - положение угла с минимальными координатами. У нас координаты будут идти так: x - слева направо; y - сверху вниз. То есть как в матрице (или, если хотите, на графическом экране). Это будет важно только для вывода информации (псевдографика в основном), но если уж так, то будем называть угол по которому мы указываем положение прямоугольника левым-верхним (top-left). Теперь, когда у нас есть, с чем иметь дело, будем иметь дело. Вопрос, который стоит перед нами, я уже поставил выше: Допустим, у нас есть два прямоугольника, а также их положения; нужно найти способ определения, пересекаются они или нет. Или, более конкретно: var То есть прежде всего нужно написать функцию, которая выдает TRUE, если два прямоугольника, переданные в параметрах, пересекаются и FALSE, если они не пересекаются. Перед написанием, конечно, неплохо было бы описать, как будет работать эта функция, словами плюс обычная математика. То есть пока без программирования, просто основные принципы работы. Вот с этого и начнем. Ekaterina7, какие у тебя соображения на этот счет? -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
Екатерина7 |
Сообщение
#5
|
Новичок Группа: Пользователи Сообщений: 43 Пол: Женский Репутация: 0 |
может просто сравнивать положения этих прямоугольников, их воординаты? если совпадут-то пересекаются.. может там цикл нужен?
|
Текстовая версия | 5.05.2024 11:48 |