Russian Qt Forum
Ноябрь 01, 2024, 02:17
Добро пожаловать,
Гость
. Пожалуйста,
войдите
или
зарегистрируйтесь
.
Вам не пришло
письмо с кодом активации?
1 час
1 день
1 неделя
1 месяц
Навсегда
Войти
Начало
Форум
WIKI (Вики)
FAQ
Помощь
Поиск
Войти
Регистрация
Russian Qt Forum
>
Forum
>
Qt
>
Вопросы новичков
>
поле N x N заполненное двумя значениями
Страниц: [
1
]
2
Вниз
« предыдущая тема
следующая тема »
Печать
Автор
Тема: поле N x N заполненное двумя значениями (Прочитано 6642 раз)
Dia28
Гость
поле N x N заполненное двумя значениями
«
:
Октябрь 19, 2011, 17:40 »
Квадратный участок размером NxN метров (N<200) разбит на клетки со стороной 1 метр. Клетка считается занятой, если на ней растёт дерево. Деревья рубить нельзя. Найти для строительствадома прямоугольник максимальной площади, свободный от деревьев. Минимальная сторона прямоугольника k вводится пользователем с клавиатуры. Визуализация и пошаговая демонстрация...
К сожалению, не знаю с чего начать и Qt только начинаю...это задание возможно сделать через массив кнопок или таблицей?при этом каждой ячейке или кнопке добавить значение 1 или 0 и относительно него цвет её? или совсем не так?
Записан
Пантер
Administrator
Джедай : наставник для всех
Offline
Сообщений: 5876
Жаждущий знаний
Re: поле N x N заполненное двумя значениями
«
Ответ #1 :
Октябрь 19, 2011, 18:09 »
Для отображения использовать QTableView, а данные хранить в своей модели, отнаследованной от QAbstractItemModel.
Записан
1. Qt - Qt Development Frameworks; QT - QuickTime
2. Не используйте в исходниках символы кириллицы!!!
3. Пользуйтесь тегом code при оформлении сообщений.
Dia28
Гость
Re: поле N x N заполненное двумя значениями
«
Ответ #2 :
Октябрь 19, 2011, 18:26 »
А с чего нужно начать?
Записан
ecspertiza
Супер
Offline
Сообщений: 1053
С уважением, мастер конфетного цеха!
Re: поле N x N заполненное двумя значениями
«
Ответ #3 :
Октябрь 19, 2011, 19:19 »
С решения на коленке
А потом уже можно будет и визуальную часть прикрутить.
Записан
Dia28
Гость
Re: поле N x N заполненное двумя значениями
«
Ответ #4 :
Октябрь 19, 2011, 19:49 »
я просто хочу сначала сделать это поле заполненное двумя значениями и ячейками двухцветов а потом подумать над алгоритмом....а вот с чего начать не знаю
Записан
Пантер
Administrator
Джедай : наставник для всех
Offline
Сообщений: 5876
Жаждущий знаний
Re: поле N x N заполненное двумя значениями
«
Ответ #5 :
Октябрь 19, 2011, 19:54 »
Если ты хочешь изучить Qt, начни с чтения книг. Если тебе нужно выполнить лабораторную, проще заплатить тому, кто ее за тебя сделает.
Записан
1. Qt - Qt Development Frameworks; QT - QuickTime
2. Не используйте в исходниках символы кириллицы!!!
3. Пользуйтесь тегом code при оформлении сообщений.
Dia28
Гость
Re: поле N x N заполненное двумя значениями
«
Ответ #6 :
Октябрь 19, 2011, 19:58 »
Это курсовая и я бы хотела в ней разобраться пока есть время...
Записан
ecspertiza
Супер
Offline
Сообщений: 1053
С уважением, мастер конфетного цеха!
Re: поле N x N заполненное двумя значениями
«
Ответ #7 :
Октябрь 19, 2011, 20:04 »
Я бы конечно сначала начал с алгоритма решения, но раз хочешь наоборот, читай про модели и представления в книги Бланшета например.
Записан
Igors
Джедай : наставник для всех
Offline
Сообщений: 11445
Re: поле N x N заполненное двумя значениями
«
Ответ #8 :
Октябрь 20, 2011, 02:44 »
На мой взгляд придумывать алгоритм куда интереснее чем копаться в подробностях чужих (пусть хороших) классов. Здесь видно так
1) Берем клетку на которой нет дерева и которая не помечена флажком Checked
2) Пытаемся "захватить" площадь, вправо и вниз. Проходит ли квадрат 2х2? А 3х3? Когда по одному направлению уткнулись в дерево, продолжаем попытки расшириться только по другому
3) Когда больше не удается "расшириться", запоминаем результат и маркируем все вошедшие клетки флагом Checked. Возвращаемся к пункту 1 до тех пор пока не проверим все клетки
С чего начать: ну хоть с какой-то структуры данных для клетки. Отладить алгоритм печатая матрицу NxN в консоли, а потом уже рисовать UI (там ума много не надо)
«
Последнее редактирование: Октябрь 20, 2011, 03:31 от Igors
»
Записан
Bepec
Гость
Re: поле N x N заполненное двумя значениями
«
Ответ #9 :
Октябрь 20, 2011, 07:13 »
Предложенный Igors алгоритм прост и удобен
А данные можно спокойно в модели хранить.
Вот только по пунку 1 - вместо флажка использовать data(32) со своим енумом(1 - занято, 0 - свободна от построек)
Записан
BRE
Гость
Re: поле N x N заполненное двумя значениями
«
Ответ #10 :
Октябрь 20, 2011, 08:53 »
Цитата: Igors от Октябрь 20, 2011, 02:44
1) Берем клетку на которой нет дерева и которая не помечена флажком Checked
Если помечать все клетки очередного тестируемого прямоугольника, то возможна ситуация, когда мы клетку пометим при проходе небольшого прямоугольника и она будет не доступна, когда мы будет тестировать по настоящему максимальный прямоугольник.
Записан
Igors
Джедай : наставник для всех
Offline
Сообщений: 11445
Re: поле N x N заполненное двумя значениями
«
Ответ #11 :
Октябрь 20, 2011, 17:47 »
Цитата: BRE от Октябрь 20, 2011, 08:53
Если помечать все клетки очередного тестируемого прямоугольника, то возможна ситуация, когда мы клетку пометим при проходе небольшого прямоугольника и она будет не доступна, когда мы будет тестировать по настоящему максимальный прямоугольник.
Когда мы "расширяем" прямоугольник - флажок Checked игнорируется (учитывается только дерево). Только когда начинаем новый прямоугольник - флажок учитывается.
А вот с направлениями я наврал: надо расширяться не только "вправо и вниз" но еще и "вверх" - имеется ввиду проход строка за строкой
Записан
Igors
Джедай : наставник для всех
Offline
Сообщений: 11445
Re: поле N x N заполненное двумя значениями
«
Ответ #12 :
Октябрь 20, 2011, 23:48 »
А есть и лучший способ (во всяком случае который найдет решение быстрее): найти все "левые верхние" и все "правые нижние" углы, и потом их сопоставить - сразу получаются прямоугольники
Записан
SimpleSunny
Гость
Re: поле N x N заполненное двумя значениями
«
Ответ #13 :
Октябрь 21, 2011, 10:16 »
Если нет требований к скорости и задача учебная, то проще сделать за O(n
4
).
Перебор левых верхних вершин, перебор правых нижних и поиск максимального.
Записан
Dia28
Гость
Re: поле N x N заполненное двумя значениями
«
Ответ #14 :
Ноябрь 08, 2011, 19:15 »
Цитата: Igors от Октябрь 20, 2011, 23:48
А есть и лучший способ (во всяком случае который найдет решение быстрее): найти все "левые верхние" и все "правые нижние" углы, и потом их сопоставить - сразу получаются прямоугольники
не могли бы вы побольше рассказать про этот алгоритм?
Записан
Страниц: [
1
]
2
Вверх
Печать
« предыдущая тема
следующая тема »
Перейти в:
Пожалуйста, выберите назначение:
-----------------------------
Qt
-----------------------------
=> Вопросы новичков
=> Уроки и статьи
=> Установка, сборка, отладка, тестирование
=> Общие вопросы
=> Пользовательский интерфейс (GUI)
=> Qt Quick
=> Model-View (MV)
=> Базы данных
=> Работа с сетью
=> Многопоточное программирование, процессы
=> Мультимедиа
=> 2D и 3D графика
=> OpenGL
=> Печать
=> Интернационализация, локализация
=> QSS
=> XML
=> Qt Script, QtWebKit
=> ActiveX
=> Qt Embedded
=> Дополнительные компоненты
=> Кладовая готовых решений
=> Вклад сообщества в Qt
=> Qt-инструментарий
-----------------------------
Программирование
-----------------------------
=> Общий
=> С/C++
=> Python
=> Алгоритмы
=> Базы данных
=> Разработка игр
-----------------------------
Компиляторы и платформы
-----------------------------
=> Linux
=> Windows
=> Mac OS X
=> Компиляторы
===> Visual C++
-----------------------------
Разное
-----------------------------
=> Новости
===> Новости Qt сообщества
===> Новости IT сферы
=> Говорилка
=> Юмор
=> Объявления
Загружается...