Author |
Message |
18/03/2012 17:19:43
|
jovank
Joined: 01/01/2010 16:17:42
Messages: 127
Offline
|
Може некој да ми даде идеа за задачава?
|
|
|
18/03/2012 19:56:46
|
MOI
Joined: 07/07/2010 16:31:48
Messages: 447
Offline
|
Главната идеја е да ја делиме околината (divide & conquer) на помали правоаголници се додека не стигнеме до правоаголник за кој сигурно знаеме дека, сите раскрсници кои се наоѓаат во него се збунувачки или сите не се.
Нека имаме функција f(r, c) која враќа листа на раскрсници со ознаки (сини кругчиња) кои се најблиски до раскрсницата (r, c). Тогаш, за секој правоаголник (rx, cx, ry, cy), важи ->
ако f(rx, cx) = f(rx, cy) = f(ry, cx) = f(ry, cy) = X,
тогаш f(r, c) = X за секоја раскрсница во правоаголникот (rx, cx, ry, cy).
Значи, (рекурзивниот) алгоритам е
This message was edited 1 time. Last update was at 18/03/2012 22:55:52
|
|
|
22/03/2012 11:14:09
|
jovank
Joined: 01/01/2010 16:17:42
Messages: 127
Offline
|
На примерот даден на сликата, ќошовите на најголемиот правоаголник имаат само по една најблиска означена раскрсница, па според горниот алгоритам во најголемиот правоаголник нема збунувачки раскрсници, што не е точно... Некако не го сфаќам алгоритамот...
|
|
|
22/03/2012 13:44:51
|
MOI
Joined: 07/07/2010 16:31:48
Messages: 447
Offline
|
Хмм, кажав дека функцијата f(r, c) враќа листа на раскрсници со ознаки (сини кругчиња) кои се најблиски до раскрсницата (r, c), и дека тој резултат треба да го споредуваш за еднаквост.
Да го разгледаме примерот од сликата - ги означив раскрсниците со ознаки (сините кругчиња) со броевите од 1 до 4.
Сега, f(ќоше горе лево) = {3} (бидејќи 3 е најблиска раскрсница), f(ќоше горе десно) = {4}, f(ќоше доле лево) = {1}, f(ќоше доле десно) = {2}. Како што гледаш, не се сите листи исти, па продолжуваме со алгоритамот така што го делиме овој правоаголник на четири помали.
Да разгледаме сега еден помал правоаголник - означен на сликата (горе лево):
За ова правоаголниче, f(ќоше горе лево) = {3}, f(ќоше горе десно) = {3}, f(ќоше доле лево) = {3}, f(ќоше доле десно) = {3}. Како што гледаш, сите листи се исти. Тука, бидејќи листите вратија по само една раскрсница, ниту една од раскрсниците во правоаголникот не се збунувачки.
Да разгледаме сега, уште еден помал правоаголник - означен на сликата (лево средина):
За ова правоаголниче, f(ќоше горе лево) = {1, 3}, f(ќоше горе десно) = {1, 3}, f(ќоше доле лево) = {1, 3}, f(ќоше доле десно) = {1, 3}. Како што гледаш, сите листи се исти (всушност, бидејќи имаме само еден ред - ќошевите горе лево и доле лево, како и ќошевите горе десно и доле десно се исти). Тука, бидејќи листите вратија повеќе од една раскрсница (вратија две -> 1 и 3), сите раскрсници во правоаголникот се збунувачки.
Се надевам дека сега е појасно
This message was edited 2 times. Last update was at 22/03/2012 13:50:15
|
|
|
22/03/2012 16:44:14
|
bedzo
Joined: 18/01/2011 02:05:03
Messages: 234
Offline
|
@MOI кодот ми заглавува на најголемиот правоаголник, т.е не го дели на помали.
|
|
|
22/03/2012 17:05:06
|
MOI
Joined: 07/07/2010 16:31:48
Messages: 447
Offline
|
@bedzo: не ја анализирав целата програма, ама ако си пресметал minn за (rx, ry), зошто тоа ти влијае на 3те други ќошиња ((rx, y1), ...) - види ја втората слика што јас ја прикачив - ако растојанието minn кај едното ќоше (горе лево) е на пример 10 и со тоа си го пополнил векторот a, не би требало minn да има, никакво, влијание на пополнувањето на другите вектори - b, c и d. Ти, некако, очекуваш дека растојанието од една раскрсница со ознаки (сино кругче) треба да е еднакво до сите ќошеви.
Исто, внимавај на именувањето (ти сметаш дека X се редовите, а Y колоните), но всушност (R се редовите, а C колоните) - мислам дека ќе сфатиш што зборувам - во алгоритамот (rx, cx, ry, cy) означува правоаголник со ќошеви (rx, cx) и (ry, cy), а не правоаголник со ќошеви (rx, ry) и (cx, cy). Имаш ваква грешка уште во почетокот на програмата - ако делиш на половина како што ти е напишано во програмата [(rx+ry)/2, (cx+cy)/2] наместо d(1, N, 1, M), веројатно треба да биде d(1, 1, N, M). Ќе треба да ги смениш параметрите и кај другава функција f.
This message was edited 1 time. Last update was at 22/03/2012 18:07:06
|
|
|
22/03/2012 19:49:48
|
bedzo
Joined: 18/01/2011 02:05:03
Messages: 234
Offline
|
Ау ама сум се зафркнал со ова координатите... Благодарам на забелешката
|
|
|
22/03/2012 22:28:16
|
jovank
Joined: 01/01/2010 16:17:42
Messages: 127
Offline
|
@MOI извинете, моја грешка, мојата функција f(r,c) враќаше само број на најблиски раскрсници (во горниов случај, за сите 4 ќоша ми враќа 1, и затоа резултатот ми излегуваше 0)... Фала
|
|
|
|
|
|