| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > C/C++: Общие вопросы > просто С++ |
| Автор: olegtikh 16.2.2003, 02:24 |
| Здравствуйте! Прошу помощь, на экзамене дали вот такую задачу: есть двумерный массив заполненный нулями и единицами нужно найти сколько есть пятен в этом массиве и какой длины каждое пятно. Пятно состоит из единичек которые находятся в соседних клеткох, например: 1 0 0 1 0 0 0 0 1 1 1 0 1 0 0 0 0 1 1 1 0 0 1 0 ответ: есть 3 пятна длиной: 1 3 6 код C++. Заранее благодарен! |
| Автор: brb 16.2.2003, 02:52 |
| А что подразумевается под помощью? Все сделать вместо тебя? Это не помощь. Помести свой вариант кода и тебе помогут и подскажут, а так это не правильно! Что мне тут интересно, а размерность массива задана или как? И, потом, по-моему, ответ и картинка, по меньшей мере, не совпадают или я чего-то не понимаю. |
| Автор: Step 16.2.2003, 03:33 |
| раз ты знаешь код с++. то просто раскладываешь свои размышления по поиску пятен на мелкие этапы и программируешь их. так, например, 1. Поиск 1 единицы, 2. Поиск единиц рядом, если да то увеличить счетчик и прейти на найденную и т.д., .... .... ... здесь, определенно, рекурсия, с учетом просмотренного |
| Автор: Wowa 16.2.2003, 04:32 | ||
грамматика:
|
| Автор: Борец за права и лева 16.2.2003, 06:26 | ||
Анатолий. с уважением относитесь к русскому языку!!! Глаза режет! |
| Автор: Vaulter 16.2.2003, 07:31 |
| какая рекурсия? цикл, ищем первую единицу - уходим в подпрограммку определения пятна, причем метим единицы из этого пятна. выходим в цикл - ищем следующую непомеченую 1 и все. |
| Автор: Lobsang 16.2.2003, 17:09 |
| Рекусия, все верно. Только вот клиент не определил что является соседними единицами, только горизонталь, или вертикаль тоже? или их считать отдельными "пятнами"? К тому же как уже отмечалось ответ и пример у него не совпадают. 1.3.6. 1 -просто не может быть. |
| Автор: Step 16.2.2003, 18:26 | ||
|
| Автор: neutrino 16.2.2003, 19:35 |
| Algoritm Dii'kstra mojno primenit'. Predstav', chto edinicy - polja po kotorym mojno hodit', a nuli - prepjatstsvija. Dalee, kogda sovershaetsja shag, rekursivnaja funkcija uvelichivaet schetchik i peredaet ego na sledujuxhii' shag, esli konechno, on suxhestvuet. |
| Автор: Alex101 17.2.2003, 00:28 |
| Рекурсия здесь не нужна. Обходим массив волной. Общий цикл, до тех пор, пока есть, что искать. Ищем единицу, за нее "цепляемся" (присваиваем 2), просматриваем, все единицы, что рядом с 2 помечаем числом 2. Нашли. Увеличили счетчик. Теперь, ежели находим единицу, то присваиваем ей 3 - далее - аналогично. Без рекурсии, сложность N^3 ЗЫ Рекурсия может не прокатить, пример - таблица NxN, где N<=1000. Волной она быстро решается, а рекурсия в частных случаях вызовет переполнение стека. |
| Автор: Step 17.2.2003, 01:15 | ||||
только надо начать волну с 0 и в зависимости сколько будет тупиков волны расчитать количество пятен или начинать с найденной единици тогда и количество элементов пятна будет известно.
Alex101Кстати, как ты волну без рекурсии запускаеш. Я себе, конечно, такое представить могу, но это же абсурд. |
| Автор: brb 17.2.2003, 01:59 | ||
С уважением, Алексей, пожалуйста, относитесь к родному языку. По-крайней мере, запомните правило написания глаголов во втором лице единственном числе - ВСЕГДА на конце мягкий знак. ВСЕГДА! Для справки - второе лицо это когда вы к кому-то обращаетесь, например, я к Вам, понимаешь? Что такое: на конце, мякгий знак и единственное лицо прошу помощи форума для объяснения.  |
| Автор: Step 17.2.2003, 02:04 |
| brb да я уже понял, только еще в привычку не вошло. И вообще - русский для меня не родной. |
| Автор: Alex101 17.2.2003, 02:38 | ||
Просмотром всего массива. И никакой это не абсурд. Абсурдом было бы в приведенном мной ограничении для исходных данных делать рекурсию. Это не просто абсурд, а работать не всегда будет. |
| Автор: Step 17.2.2003, 02:42 | ||
|
| Автор: olegtikh 17.2.2003, 02:44 |
| Спасибо за отклики, соседи единицы такие: left, right, up, down, right-up, right-down, left-up, left-down. Я понимаю вы здесь все крутые, а ссылки на алгоритмы не даете. Если бы я знал код, то к Вам бы не обращался. Но все равно спасибо за реакцию! |
| Автор: olegtikh 17.2.2003, 03:03 |
| А вот функция которая не работает так как надо, rezult[] ето глобальный массив в который записывается результат. L это следующий ход, x_ , y_ позиция клетки. |
| Автор: olegtikh 17.2.2003, 03:03 |
| void find(int L,int x_, int y_) { //L = x_ + y_; result[x_ + y_] = L; if(L == ROWS*COLS) exit(0); if(arr[x_ + 1][y_] == 1) { find(L + 1,x_ + 1,y_); //right } else if (arr[x_ + 1][y_] == 0) find(L,x_+1,y_); if(arr[x_ - 1][y_] == 1) { find(L + 1,x_ - 1,y_); //left } else if (arr[x_ - 1][y_] == 0) find(L,x_ - 1,y_); if(arr[x_][y_ + 1] == 1) { find(L + 1,x_,y_ + 1); //up } else if(arr[x_][y_ + 1] == 0) find(L,x_,y_ + 1); if(arr[x_][y_ - 1] == 1) { find(L + 1,x_,y_ - 1); //down } else if(arr[x_][y_ - 1] == 0) find(L,x_,y_ - 1); if(arr[x_ + 1][y_ + 1] == 1) { find(L + 1,x_ + 1,y_ + 1);//right - up } else if(arr[x_ + 1][y_ + 1] == 0) find(L,x_ + 1,y_ + 1); if(arr[x_ + 1][y_ - 1] == 1) { find(L + 1,x_ + 1,y_ - 1);//rihgt-down } else if(arr[x_ + 1][y_ - 1] == 0) find(L,x_ + 1,y_ - 1); if(arr[x_ - 1][y_ + 1] == 1) { find(L + 1,x_ - 1,y_ + 1);//left-up } else if(arr[x_ - 1][y_ + 1] == 0) find(L,x_ - 1,y_ + 1); if(arr[x_ - 1][y_ - 1] == 1) { find(L + 1,x_ - 1,y_ - 1);//left-down } else if(arr[x_ - 1][y_ - 1] == 0) find(L,x_ - 1,y_ - 1); } |
| Автор: Alex101 17.2.2003, 07:53 | ||||
Все же решил с рекурсией? Первый вопрос: Пятном считается совокупность клеток не только по горизонтали-вертикали, но и по диагонали? Ежели так, то ругательств по поводу диагоналей не будет
А это для чего? (Это только один из твоих вариантов) Для чего искать дальше, ежели уже ничего не нашли? Ищем дальше в случае ненулевой клетки. Или ты просто дальше ищешь следующие пятна? Тогда снова надо просматривать таблицу, перед этим найденное пятно должно быть удалено. А вообще, по поводу готовых программ на форуме уже говорили. Здесь скажут, что именно у тебя неправильно или натолкнут на идею. А написать готовое решение - это уже в разделе "Работа". (Ну или кому совсем нечего делать) 2 Step
У меня подход универсальный - будет работать всегда, в случае рекурсии может не хватить стека. |