Пошук - островів - на графі Програмування
Математика, Фізика, Computer Science, Machine Learning, LaTeX, Механіка та Техніка, Хімія,Біологія та Медицина, Економіка та Фінансова Математика, Гуманітарні науки| Вхід Реєстрація | Donate FAQ Правила Пошук |
пошук "острівів" на графі
| На сторінку1, 2 Слід. |
| Друкувати сторінку Друкувати всю тему | Попер. тема Слід. тема |
| Euler7 |
| Mysterious Light |
| Null |
| Euler7 |
| Alexu007 |
Робиться це рекурсією. Допустимо 0 – білий квадрат, 1 – синій, 2 – червоний.
1. перебираєте свою карту до знаходження першого кольорового квадрата (у моєму прикладі 0) - карту по-любому доведеться перебрати всю від початку до кінця - це питання складності алгоритму.
2. Початок функції: запам'ятовуєте, який колір ви знайшли, додаєте щось до знайденого квадрата, наприклад +10, тепер там 11 (або 12 якщо перший був знайдений червоний)
3. Шукайте в діапазоні +- 1 від знайденого квадрата, тут необхідновідстежувати вихід за межі поля (менше за нуль, більше макс.), можна не перевіряти діагоналі - якщо обидві змінні не рівні 0, і центр - якщо обидві рівні 0. Якщо знаходите ще квадрат потрібного кольору (колір ви запам'ятали на початку) - викликаєте знову функцію пункту 2.
І так далі до кінця поля. Щоб ваші знайдені поля відрізнялися, можна додавати різні цифри: +10, +20, +30 і так далі.
Сподіваюся, що зрозуміло.
| arseniiv |
| Alexu007 |
| arseniiv |
| Alexu007 |
Безглузде. Пошук углиб – цикл і стек. Пошук завширшки (згаданий вище Mysterious Light) - цикл і черга. Від циклу замість рекурсії у разі одні плюси. Ну і, плюс, у глибину замість ширини тут, начебто, гірше.
Як вас тягне поради давати...
У нас прямокутна (квадратична) карта, на якій потрібно перебрати всі комірки – тому щокомп'ютер не може подивитися на неї здалеку і побачити, що в "лівому нижньому кутку нічого немає, і шукати там не треба". В умовах завдання нічого не сказано про місце розташування та кількість кольорових осередків, можливо всього одна в нижньому правому кутку карти, і її потрібно знайти. Тому вкладений цикл і перебираємо послідовно всю карту в пошуку цікавих кольорових осередків.
Поясніть пжалста, що означає пошук завширшки, чи (тим більше) у глибину?
| Skeptic |
Розмічати карту не потрібно, вона і так вже розмічена. Потрібно виділити зони, і записати окремо. Форма запису зони повинна спрощувати наступну обробку. Складності програми боятися не слід - вона залежить від алгоритму. А ось алгоритм має бути прозорим.
Налагоджувати програму зручно на образі літери Ш, повертаючи її.
У цьому алгоритмі свідомо багато дубльованих дій, але вони усунуться на стадії оптимізації.
P.S. Залучення понять теорії графів зайве, де вони полегшують програмування, без них навіть простіше.
| arseniiv |
| Alexu007 |
Так можна і без циклу, для кожного осередку свій код писати і послідовно виконувати - і теж працюватиме. Все-таки програми пишуть як простіше та зрозуміліше. Ось код на Сі, який робить приблизно те саме: шукає і позначає злиплі боками квадрати (взято з морського бою, функція вважає кількість палуб у кораблі):
//функція визначає число палуб у корабля без урахування кутових клітин // отримує координати першої знайденої палуби x, y // повертає в Cx_Palube число палуб у корабля //-------- -------------------------------------------------- ----------------- void Detect_One_Ship_01 ( int x, int y ) < int x1, y1;
//додаємо 1 до лічильника палуб корабля Cx_Palube ++;
//встановлюємо в знайдену палубу 2 замість 1, щоб не рахувати ще раз pole_Homo [X] [Y] = 2;
for ( int i = - 1 ; i 2 ; i ++ ) < x1 = x + i; if ((x1 0) (x1 == Rz)) continue;
for ( int j = - 1 ; j 2 ; j ++ ) < y1 = y + j; if ((y1 0) (y1 == Rz)) continue;
// не перевіряємо кути if ((i! = 0) &(amp; (j! = 0)) continue;
//рекурсивно викликаємо функцію Detect_OneShip if (pole_Homo [x1] [y1] == 1) Detect_One_Ship_01 (x1, y1); > >
for ( int i = 0 ; i Rz ; i ++ ) for ( int j = 0 ; j Rz ; j ++ ) if ( pole_Homo [ i ] [ j ] == 1 ) < Cx_Palube = 0;
// виклик функції Detect_One_Ship_01 (i, j); >
| venco |
| Skeptic |
venco , як Alexu007 може зрозуміти недоліки пошуку в глибину, якщо на його прохання пояснити це ніхто не відгукнувся? Можливо ви поясните що таке пошук в глибину, а заразом, і в ширину?
Alexu007 Програми після написання зазвичай виконують, щоб переконатися в їх правильності. Де у вашій програмі вказані координати першої палуби? Навіщо без потреби застосовувати рекурсію? Для ускладнення програми чи наукоподібності? Пишіть простіше.
| Alexu007 |
| Сторінка1 із2 | [ Повідомлень: 27 ] | На сторінку1, 2 Слід. |
Хто зараз на конференції
Зараз цей форум переглядають: немає зареєстрованих користувачів