7 / 7 / 2
Регистрация: 25.12.2011
Сообщений: 111
|
|
1 | |
Найти количество заштрихованых квадратов12.08.2013, 14:32. Показов 1652. Ответов 21
Метки нет (Все метки)
Помогите решить задачку пожалуйста. Программа должна вывести количество заштрихованых квадратов (5) если квадраты прилегают друг к другу это щитается как 1.
0
|
12.08.2013, 14:32 | |
Ответы с готовыми решениями:
21
В файле с целыми числами найти количество парных, количество удвоенных нечетных, количество квадратов нечетных Найти количество квадратов размещенных на прямоугольнике Найти количество квадратов из единиц в двумерном массиве Найти количество квадратов в наборе из 10 целых положительных чисел |
55 / 55 / 6
Регистрация: 07.07.2013
Сообщений: 345
|
||||||
12.08.2013, 14:53 | 2 | |||||
2
|
7 / 7 / 2
Регистрация: 25.12.2011
Сообщений: 111
|
|
12.08.2013, 15:10 [ТС] | 3 |
0
|
12.08.2013, 15:14 | 4 |
vozup, Ставь условие конкретно! Я уверен, задача звучала не так:
А, например, так:
Дана матрица m на n Некоторые клетки в матрице заштрихованы, если их значение не равно 0 Фигурой будем называть группу всех клеток, прилегающих друг к другу по вертикали или горизонтали. Найти количество квадратов в наибольшей фигуре.
0
|
7 / 7 / 2
Регистрация: 25.12.2011
Сообщений: 111
|
|
12.08.2013, 15:28 [ТС] | 5 |
0
|
77 / 18 / 1
Регистрация: 03.02.2013
Сообщений: 52
|
|
12.08.2013, 15:56 | 6 |
Создаете двухмерный массив размером *ширина х длина*, подстать таблице с кубиками. Заполняете элементы массива, соответствующие заштрихованным кубикам единицами остальное -нулями. Создаете счетчик, пробегаетесь по массиву, в случае обнаружения элемента равного 1 увеличиваете счетчик на 1 и ставите его равным 0 проверяете все элементы вокруг этого счетчика (только по вертикали и горизонтали) и если хоть один из них равен 1 не трогаете счетчик, а просто обнуляете данный элемент. Далее просто выводим счетчик на экран.
Аминь.
1
|
_
317 / 151 / 27
Регистрация: 08.10.2011
Сообщений: 432
|
|
12.08.2013, 15:56 | 7 |
Сетку можно рассматривать как граф: заштрихованные квадраты на сетке - это узлы графа, если 2 таких квадрата касаются друг друга стороной, то значит между ними есть ребро.
ваша задача сводится к поиску связных компонентов в графе (с помощью любого вида обхода графа DFS/BFS/PFS или с помощью disjoint set).
0
|
7 / 7 / 2
Регистрация: 25.12.2011
Сообщений: 111
|
||||||
12.08.2013, 16:57 [ТС] | 8 | |||||
0
|
_
317 / 151 / 27
Регистрация: 08.10.2011
Сообщений: 432
|
|
12.08.2013, 17:21 | 9 |
1. сможете доказать корректность вашего алгоритма?
2. зачем циклы while если тело циклов всегда будет выполняться 1 раз?
0
|
7 / 7 / 2
Регистрация: 25.12.2011
Сообщений: 111
|
||||||
12.08.2013, 17:55 [ТС] | 10 | |||||
Никак не могу понять где ошибка, уже и по диагонали проверяю, все ровно не получается
0
|
_
317 / 151 / 27
Регистрация: 08.10.2011
Сообщений: 432
|
|
12.08.2013, 18:14 | 11 |
почему вы думаете, что ваш алгоритм решает поставленную задачу?
но т.к. ответа на вопрос я от вас всё равно не дождусь, опишу следующую ситуацию: есть фигура на сетке "3 заштрихованных квадрата в ряд (горизонтально)". Ваш алгоритм доходит до левого квадрата фигуры, увеличивает счетчик 1, обнуляет значение в соответствующей ячейке, а также обнуляет значение в ячейке левее. Далее идем к этой ячейке, которая левее, она имеет значение 0, следовательно пропускаем ее. Далее идем еще левее, к последнему квадрату фигуры. там стоит единица, следовательно увеличиваем счетчик на 1. Ошибка! счетчик не надо увеличивать, т.к. квадрат относится к уже помеченной фигуре. Следовательно ваш алгоритм не решает задачу.
0
|
12.08.2013, 18:16 | 12 | |||||
да сам подход неверный.
Насколько я понимаю твой алгоритм, -ты проходишь по всем клеткам. -при обнаружении заштрихованной увеличиваешь счётчик - ну и пытаешься обнулить всю фигуру, которой клетка принадлежит, чтобы счётчик срабатывал единожды на одну фигуру. только обнуление фигуры у тебя вообще бредовое! вот это
К тому же, проверять верхний, левый и верхний-левый квадраты смысла нет, так как по квадратам сверху и слева мы уже проходились циклом. + тут не учитывается выход за границы массива. + фигуру целиком ты так никогда не обнулишь - для этого нужен цикл или рекурсия, а то, что ты делаешь - это лишь обнуление восьми соседних клеток. + зачем их вообще проверять на заполненность, если ты мог записывать в них ноль вне зависимости от того, заполнена она или нет.
0
|
Кактус
67 / 67 / 19
Регистрация: 23.05.2012
Сообщений: 342
|
||||||
12.08.2013, 19:38 | 13 | |||||
1
|
7 / 7 / 2
Регистрация: 25.12.2011
Сообщений: 111
|
|
20.08.2013, 13:38 [ТС] | 14 |
Задача обновилась. Теперь нужно что бы при любых комбинациях выдавало правильное количество фигур
0
|
Кактус
67 / 67 / 19
Регистрация: 23.05.2012
Сообщений: 342
|
|||||||||||
20.08.2013, 13:54 | 15 | ||||||||||
1
|
7 / 7 / 2
Регистрация: 25.12.2011
Сообщений: 111
|
|
20.08.2013, 15:54 [ТС] | 16 |
Конечно спасибо, а нельзя ли как нибудь код попроще, просто если я принесу этот мне не поверят что я сделал))
0
|
Кактус
67 / 67 / 19
Регистрация: 23.05.2012
Сообщений: 342
|
|
20.08.2013, 16:05 | 17 |
С этой реализацией у вас больше шансов понять, что происходит. Берете листок в клеточку, рисуете 2 поля m * n, нумеруете от [0] до [m-1] / [n-1] грани этих полей. Первое поле - Ваше исходное поле, Второе поле - поле с вашими следами (грубо говоря на каждом шаге мы метим клеточку). Рисуете фигурки в первом поле и пошагово как в алгоритме, сами, ручками его выполняете, отмечая во втором поле ваши следы точечкой или крестиком.
1
|
7 / 7 / 2
Регистрация: 25.12.2011
Сообщений: 111
|
||||||
20.08.2013, 16:14 [ТС] | 18 | |||||
А без указателей никак не обойтись, а то я сними пока еще не сильно дружу)
Добавлено через 2 минуты Вот, я немножко переделал, не можете посмотреть правильный ли код?
0
|
Кактус
67 / 67 / 19
Регистрация: 23.05.2012
Сообщений: 342
|
|
20.08.2013, 16:22 | 19 |
Да, все правильно, можно и так. Однако чаще всего бывают ситуации, когда размер поля не известен - его получают только в ходе выполнения программы. Если размер поля не изменяется вы все правильно сделали.
1
|
7 / 7 / 2
Регистрация: 25.12.2011
Сообщений: 111
|
||||||
20.08.2013, 16:28 [ТС] | 20 | |||||
Размеры полей это пока что временно, что бы вручную не набирать. А не могли бы вы еще объяснить вот этот код:
0
|
20.08.2013, 16:28 | |
20.08.2013, 16:28 | |
Помогаю со студенческими работами здесь
20
Найти количество квадратов, имеющих общую точку с прямой Найти количество квадратов нечётных чисел среди компонентов файла Найти количество квадратов нечетных чисел среди компонент файла Найти количество квадратов, расположенных на прямоугольнике, не используя операции умножения и деления Задача Robot. Найти количество единичных квадратов, на которых робот побывал более одного раза Заполнить файл f натуральными случайными числами. Найти количество квадратов четных чисел среди компонентов и вывести их Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |