Russian Qt Forum
Ноябрь 01, 2024, 02:17 *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

Войти
 
  Начало   Форум  WIKI (Вики)FAQ Помощь Поиск Войти Регистрация  

Страниц: [1] 2   Вниз
  Печать  
Автор Тема: поле N x N заполненное двумя значениями  (Прочитано 6642 раз)
Dia28
Гость
« : Октябрь 19, 2011, 17:40 »

Квадратный участок размером NxN метров (N<200) разбит на клетки со стороной 1 метр. Клетка считается занятой, если на ней растёт дерево. Деревья рубить нельзя. Найти для строительствадома прямоугольник максимальной площади, свободный от деревьев. Минимальная сторона прямоугольника k вводится пользователем с клавиатуры. Визуализация и пошаговая демонстрация...

К сожалению, не знаю с чего начать и Qt только начинаю...это задание возможно сделать через массив кнопок или таблицей?при этом каждой ячейке или кнопке добавить значение 1 или 0 и относительно него цвет её? или совсем не так?

Записан
Пантер
Administrator
Джедай : наставник для всех
*****
Offline Offline

Сообщений: 5876


Жаждущий знаний


Просмотр профиля WWW
« Ответ #1 : Октябрь 19, 2011, 18:09 »

Для отображения использовать QTableView, а данные хранить в своей модели, отнаследованной от QAbstractItemModel.
Записан

1. Qt - Qt Development Frameworks; QT - QuickTime
2. Не используйте в исходниках символы кириллицы!!!
3. Пользуйтесь тегом code при оформлении сообщений.
Dia28
Гость
« Ответ #2 : Октябрь 19, 2011, 18:26 »

А с чего нужно начать?
Записан
ecspertiza
Супер
******
Offline Offline

Сообщений: 1053


С уважением, мастер конфетного цеха!


Просмотр профиля
« Ответ #3 : Октябрь 19, 2011, 19:19 »

С решения на коленке Улыбающийся А потом уже можно будет и визуальную часть прикрутить.
Записан
Dia28
Гость
« Ответ #4 : Октябрь 19, 2011, 19:49 »

я просто хочу сначала сделать это поле заполненное двумя значениями и ячейками двухцветов а потом подумать над алгоритмом....а вот с чего начать не знаю
Записан
Пантер
Administrator
Джедай : наставник для всех
*****
Offline Offline

Сообщений: 5876


Жаждущий знаний


Просмотр профиля WWW
« Ответ #5 : Октябрь 19, 2011, 19:54 »

Если ты хочешь изучить Qt, начни с чтения книг. Если тебе нужно выполнить лабораторную, проще заплатить тому, кто ее за тебя сделает.
Записан

1. Qt - Qt Development Frameworks; QT - QuickTime
2. Не используйте в исходниках символы кириллицы!!!
3. Пользуйтесь тегом code при оформлении сообщений.
Dia28
Гость
« Ответ #6 : Октябрь 19, 2011, 19:58 »

Это курсовая и я бы хотела в ней разобраться пока есть время...
Записан
ecspertiza
Супер
******
Offline Offline

Сообщений: 1053


С уважением, мастер конфетного цеха!


Просмотр профиля
« Ответ #7 : Октябрь 19, 2011, 20:04 »

Я бы конечно сначала начал с алгоритма решения, но раз хочешь наоборот, читай про модели и представления в книги Бланшета например.
Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #8 : Октябрь 20, 2011, 02:44 »

На мой взгляд придумывать алгоритм куда интереснее чем копаться в подробностях чужих (пусть хороших) классов. Здесь видно так

1) Берем клетку на которой нет дерева и которая не помечена флажком Checked

2) Пытаемся "захватить" площадь, вправо и вниз. Проходит ли квадрат 2х2? А 3х3? Когда по одному направлению уткнулись в дерево, продолжаем попытки расшириться только по другому

3) Когда больше не удается "расшириться", запоминаем результат и маркируем все вошедшие клетки флагом  Checked. Возвращаемся к пункту 1 до тех пор пока не проверим все клетки

С чего начать: ну хоть с какой-то структуры данных для клетки. Отладить алгоритм печатая матрицу NxN в консоли, а потом уже рисовать UI (там ума много не надо)
« Последнее редактирование: Октябрь 20, 2011, 03:31 от Igors » Записан
Bepec
Гость
« Ответ #9 : Октябрь 20, 2011, 07:13 »

Предложенный Igors алгоритм прост и удобен Улыбающийся

А данные можно спокойно в модели хранить.

Вот только по пунку 1 - вместо флажка использовать data(32) со своим енумом(1 - занято, 0 - свободна от построек) Улыбающийся
Записан
BRE
Гость
« Ответ #10 : Октябрь 20, 2011, 08:53 »

1) Берем клетку на которой нет дерева и которая не помечена флажком Checked
Если помечать все клетки очередного тестируемого прямоугольника, то возможна ситуация, когда мы клетку пометим при проходе небольшого прямоугольника и она будет не доступна, когда мы будет тестировать по настоящему максимальный прямоугольник.
Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #11 : Октябрь 20, 2011, 17:47 »

Если помечать все клетки очередного тестируемого прямоугольника, то возможна ситуация, когда мы клетку пометим при проходе небольшого прямоугольника и она будет не доступна, когда мы будет тестировать по настоящему максимальный прямоугольник.
Когда мы "расширяем" прямоугольник - флажок Checked игнорируется (учитывается только дерево). Только когда начинаем новый прямоугольник - флажок учитывается.

А вот с направлениями я наврал: надо расширяться не только "вправо и вниз" но еще и "вверх" - имеется ввиду проход строка за строкой
Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #12 : Октябрь 20, 2011, 23:48 »

А есть и лучший способ (во всяком случае который найдет решение быстрее): найти все "левые верхние" и все "правые нижние" углы, и потом их сопоставить - сразу получаются прямоугольники
Записан
SimpleSunny
Гость
« Ответ #13 : Октябрь 21, 2011, 10:16 »

Если нет требований к скорости и задача учебная, то проще сделать за O(n4).
Перебор левых верхних вершин, перебор правых нижних и поиск максимального.
Записан
Dia28
Гость
« Ответ #14 : Ноябрь 08, 2011, 19:15 »

А есть и лучший способ (во всяком случае который найдет решение быстрее): найти все "левые верхние" и все "правые нижние" углы, и потом их сопоставить - сразу получаются прямоугольники
не могли бы вы побольше рассказать про этот алгоритм?
Записан
Страниц: [1] 2   Вверх
  Печать  
 
Перейти в:  


Страница сгенерирована за 0.108 секунд. Запросов: 22.