IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

 
 Ответить  Открыть новую тему 
> Теория графов., Раскраска карты минимальным кол_вом цветов
сообщение
Сообщение #1


Гость






Программа раскрашивания карты минимальным количеством цветов.

Исходные данные:

- Список регионов с указанием соседей каждого региона.

Выходные данные:

- Список регионов с приписанными им цветами.
- Общее число использованных цветов.

Требованния к фунуциональности:

- Эфективность решения.
- Наглядный вывод результата(раскраска карты).
- Опционально редактор карт(с возможностью рисовать мышью).

Вопрос следуюший, как сделать редактор карт с возможностью рисования мышью и удомным для пользователя меню.
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Гость






Ну, это смотря какими средствами тебе можно пользоваться, смотря какой компилятор, опять же... ООП? Встроенный ASM? Внешние процедуры на ассемблере?
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Гость






Цитата(volvo @ 29.04.2006 18:22) *

Ну, это смотря какими средствами тебе можно пользоваться, смотря какой компилятор, опять же... ООП? Встроенный ASM? Внешние процедуры на ассемблере?

Была мысль использовать ООП но с реализацией не задалось, так-как я знаю только основы Паскаля. А вобше эта работа курсовик, пользоватся можно всем (ООП,ASM). Правда на серьезную реализацию времени нет, 10 мая сдача работы а пока только оболочка и меню готовы. Если можеш помоги.
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Гость






Нет, до 10-го мая я ничего серьезного сделать не успею, а что-то недоделанное выкладывать не буду... Надо было раньше обращаться. Чего тянул?
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Гость






Цитата(volvo @ 29.04.2006 21:50) *

Нет, до 10-го мая я ничего серьезного сделать не успею, а что-то недоделанное выкладывать не буду... Надо было раньше обращаться. Чего тянул?

Я курсовик 26 апреля взял. А можно все сделать но только на Graph'e?
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Гость






Да кстати 10 мая промежуточная сдача, основная будет 25-27 мая.
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Гость, ты много всего перечислил, и не совсем понятно, насколько тебя волнует основной алгоритм - процесс раскрашивания. Если волнует, то могу помочь с этим. Задача очень любопытная, меня заинтересовало уже то, что проблема четырех красок как раз не так давно была решена теоретически (с помощью компьютера, это как бы наглядный пример, как комп помогает в чистой математике), и захотелось самому прикоснуться.. smile.gif

Я тут набросал прогу, которая производит правильную (то есть соседние области - разноцветные) раскраску, не гарантируя минимальности количества цветов. Основной принцип - рекуррентная окраска областей. Написано без ООП, да и вообще довольно просто. Надеюсь, разберешься. А уж минимальность обеспечивай сам.. smile.gif (можешь задавать вопросы)

const
Nx=100; {максимальное число областей}

var
N, {реальное число областей}
i,j:integer;
Col:array[1..Nx]of byte; {массив цветов}
Nn:array[1..Nx]of byte; {сколько соседей у каждой области}
Nei:array[1..Nx,1..Nx]of byte; {массив соседей}
Trace:array[1..Nx]of boolean; {для отметки пройденных областей}
Empty:set of byte; {для очистки списка цветов}
f:text;

const
MaxCol:byte=0;

function Paint(m:byte):byte;
var
i:integer;
Used:set of byte;
begin
Used:=Empty; {очищаем список использованных цветов}
if Col[m]=0 then begin {если область еще не покрашена..}
Trace[m]:=false; {отмечаем пройденные области}
for i:=1 to Nn[m] do if Trace[Nei[m,i]] then Include(Used,Paint(Nei[m,i])); {опрашиваем цвета соседей}
i:=1;
while i in Used do Inc(i); {выбираем первый цвет из свободных}
if i>MaxCol then MaxCol:=i; {запоминаем максимальный цвет (несущественно)}
Col[m]:=i; {заполняем массив цветов областей}
Paint:=i;
Trace[m]:=true {необязательно}
end
else Paint:=Col[m] {если область уже покращена, просто возвращаем ее цвет}
end;

begin
for i:=0 to 255 do Exclude(Empty,i);
for i:=1 to Nx do begin
Col[i]:=0;
Trace[i]:=true
end;
{формат данных:}
{число строк равно чилу областей}
{первое число в строке - количество соседей области}
{затем перечисляются соседи}
{пустых строк не должно быть ни внутри, ни в конце}
Assign(f,'reg_nei.dat');
Reset(f);
N:=0;
while not EoF(f) do begin
Inc(N);
Read(f,Nn[N]);
for i:=1 to Nn[N] do Read(f,Nei[N,i]);
ReadLn(f)
end;
Close(f);

Paint(1); {красим область 1}
WriteLn('MaxCol = ',MaxCol);
for i:=1 to N do Write(' ',Col[i]);
WriteLn;
ReadLn;
end.


А вот пример файла с областями, reg_nei.dat
Код
5 2 3 4 5 6
3 1 3 6
3 1 2 4
3 1 3 5
3 1 4 6
3 1 5 2

Это расположение представляет собой пятилепестковую ромашку smile.gif. На нем (и на более простых) я проверял прогу. Вроде, не врет..


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8





Группа: Пользователи
Сообщений: 8
Пол: Мужской

Репутация: -  0  +


Попробовал сделать основную программу для раскраски карты:

Вот код: (Показать/Скрыть)

но она не работает. В чем проблема?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Гость






Во-первых, что значит "не работает"? Вылетает, или не выполняет того, что требуется?

Ну, и на всякий случай присоедини твой файл map.dat... Чтоб можно было прогнать при таких же данных...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10





Группа: Пользователи
Сообщений: 8
Пол: Мужской

Репутация: -  0  +


Провел поиск багов и получил следующее: (Показать/Скрыть)

.
Теперь все работает smile.gif . Осталось только все в графическом
виде представить.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #11


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(strangerfx @ 1.05.2006 18:24) *

Теперь все работает smile.gif . Осталось только все в графическом
виде представить.

Немного странная манера: попросить о помощи, а потом даже не замечать постов с той самой помощью.
И если уж постишь свою прогу (кстати, без единого комментария), то по крайней мере прилагай файл данных, как просил тебя volvo, или хотя бы опиши его формат. Или ты считаешь мы должны просто распечатать, повестить твое бессмертное творение на стену и восхищаться?..


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #12





Группа: Пользователи
Сообщений: 8
Пол: Мужской

Репутация: -  0  +


Цитата(lapp @ 2.05.2006 4:10) *

Немного странная манера: попросить о помощи, а потом даже не замечать постов с той самой помощью.
И если уж постишь свою прогу (кстати, без единого комментария), то по крайней мере прилагай файл данных, как просил тебя volvo, или хотя бы опиши его формат. Или ты считаешь мы должны просто распечатать, повестить твое бессмертное творение на стену и восхищаться?..

1. За помощь спасибо(кстати я ее всегда замечаю), но рекурентное решение задачи неподходит по условию написания работы (обязательно использование списков и/или деревьев).
2. Я бы приложил фаил если бы знал как это сделать.
3. Коментариев к проге неписал по причине нехватки времени, и распечатывать ее совершенно необязательно!.
4. Вопрос: где можно скачать TPU фаил для работы с мышью?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #13


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


> 1. За помощь спасибо(кстати я ее всегда замечаю),
Я не зрение твое имел в виду. Замечать - значит "реагировать". Игнорировать в разговоре = не замечать. Или я неправильно трактую русский язык? Спасибо, вытянуте клещами, звучит странновато.. но ничего, принимаю.

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

> 2. Я бы приложил фаил если бы знал как это сделать.
Кнопочки "Browse" и "Добавить файл" настолько малозаметны?.. Ну, в таком случае можно было бы спросить..

> 3. Коментариев к проге неписал по причине нехватки времени,
Комментарии - твой личный вопрос, но только пока ты не показываешь прогу другим. Простая вежливость требует писать их, если ты передаешь программу, особенно с целью поиска ошибок. Не верю, что на написание нескольких слов уходит много времени. В качестве примера можешь посмотреть мой код (выше).

> и распечатывать ее совершенно необязательно!.
Но что тогда с ней делать? Никакого вопроса с ней задано не было..

> 4. Вопрос: где можно скачать TPU фаил для работы с мышью?
Это отдельный вопрос, отдельная тема..


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #14





Группа: Пользователи
Сообщений: 8
Пол: Мужской

Репутация: -  0  +


Цитата(lapp @ 8.05.2006 12:46) *

> 1. За помощь спасибо(кстати я ее всегда замечаю),
Я не зрение твое имел в виду. Замечать - значит "реагировать". Игнорировать в разговоре = не замечать. Или я неправильно трактую русский язык? Спасибо, вытянуте клещами, звучит странновато.. но ничего, принимаю.

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

> 2. Я бы приложил фаил если бы знал как это сделать.
Кнопочки "Browse" и "Добавить файл" настолько малозаметны?.. Ну, в таком случае можно было бы спросить..

> 3. Коментариев к проге неписал по причине нехватки времени,
Комментарии - твой личный вопрос, но только пока ты не показываешь прогу другим. Простая вежливость требует писать их, если ты передаешь программу, особенно с целью поиска ошибок. Не верю, что на написание нескольких слов уходит много времени. В качестве примера можешь посмотреть мой код (выше).

> и распечатывать ее совершенно необязательно!.
Но что тогда с ней делать? Никакого вопроса с ней задано не было..

> 4. Вопрос: где можно скачать TPU фаил для работы с мышью?
Это отдельный вопрос, отдельная тема..

>1 Критиковать других каждый может, "Игнорировать в разговоре = не замечать" странная формула помоему smile.gif , твои код я просмотрел и кое что из него подчерпнул для себя, но не больше.
>2 Без коментариев.
>3 Код моей программы ненастолько сложен для человека разбирающегося в Pascal, я считаю что именно такие люди отвечают здесь на вопросы.
>4 Вопрос неотдельный, если бы ты посмотрел требования к функциональности программы то заметил бы следующее - Опционально редактор карт(с возможностью рисовать мышью)., а это означает что мыш надо сначала подключить smile.gif .
Вопрос по теме: Как создать меню на ООП и подключить к нему мою программу?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 




- Текстовая версия 23.08.2017 3:21
Хостинг предоставлен компанией "Веб Сервис Центр" при поддержке компании "ДокЛаб"