быдлокодер
1724 / 911 / 106
Регистрация: 04.06.2008
Сообщений: 5,679
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
1 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
предлагаю людям класс "рекурсивный обход матрицы" для решения задач на такую тематику29.07.2011, 21:59. Показов 8965. Ответов 96
Метки быдлокодерство (Все метки)
Друзья!
Ввиду возникшей необходимости мной был написан класс "рекурсивный обход матрицы"; Теперь задачи на такую тематику будут решаться легко и просто. С меня интерфейс, с вас- мозги. подробнее
Рассмотрим одну из таких задач, на её примере я покажу как надо решать такие задачи и познакомлю с терминами. Вот ей текст
................................................................................ .... 1 Попытка к бегству Время на тест - 3 секунды. Узник пытается бежать из замка, который состоит из MN квадратных комнат, расположенных в виде прямоугольника M?N. Между любыми двумя соседними комнатами есть дверь , однако некоторые комнаты закрыты и попасть в них нельзя. В начале узник находится в угловой комнате и для спасения ему надо попасть в противоположную угловую комнату. Времени у него немного, всего он может побывать не более, чем в M+N-1 комнате, включая начальную и конечную комнату на своем пути, то есть с каждым переходом в соседнюю комнату расстояние до выхода из замка должно уменьшаться. От вас требуется найти количество различных маршрутов, ведущих к спасению. Формат входных данных Первая строчка входных данных содержит натуральные числа M и N, не превосходящих 1000. Далее идет план замка в виде M строчек из N символов в каждой. Один символ соответствует одной комнате: если символ равен 1, то в комнату можно попасть, если он равен 0, то комната закрыта. Первоначальное положение узника - левый нижний угол (первый символ последней строки), выход находится в правом верхнем углу (последний символ первой строки, оба этих символа равны 1). Формат выходных данных Программа должна напечатать количество маршрутов, ведущих узника к выходу и проходящих через M+N-1 комнату, или слово impossible, если таких маршрутов не существует. Входные данные подобраны таким образом, что искомое число маршрутов не превосходит 2.000.000.000. Пример Входные данные 3 5 11111 10101 11111 Выходные данные 3 Входные данные 3 5 11101 10101 10101 Выходные данные impossible ................................................................................ ... ОК, ну что ж, не будем размениваться по мелочам. Я думаю если мы найдём цепочки клеток, по которым из левого нижнего угла можно добраться до правого верхнего, количество цепочек вы найдёте сами. ...Кстати, вот эти цепочки: (4 0) (3 0) (2 0) (1 0) (0 0) (0 1) (0 2) (0 3) (0 4) (4 0) (3 0) (2 0) (2 1) (2 2) (1 2) (0 2) (0 3) (0 4) (4 0) (3 0) (2 0) (2 1) (2 2) (2 3) (2 4) (1 4) (0 4) (4 0) (4 1) (4 2) (3 2) (2 2) (1 2) (0 2) (0 3) (0 4) (4 0) (4 1) (4 2) (3 2) (2 2) (2 3) (2 4) (1 4) (0 4) (4 0) (4 1) (4 2) (4 3) (4 4) (3 4) (2 4) (1 4) (0 4) ................................................................................ .... Для того чтобы найти такие цепочки необходимо прежде всего создать объект класса rek_obhod_matr. Перечисляю по порядку параметры, которые он принимает: собственно матрицу, количество строк, количество столбцов, номер строки и столбца начальной точки. То есть в нашем случае будет такой код:
А взамен получаете вектор векторов пар элементов типа int, каждая пара- координаты очередной точки. Ну то есть вот такую штуку получаете:
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ +++ Сосредоточимся на функциях- членах класса Смотрите. Если мы "стоим" в некоторой клетке, объект, созданный нами называется obhod, то её координаты текущие. Их можно найти с помощью функций-членов:
Вернёмся к задаче. Представьте себе, что мы каким-то образом (пока неважно, каким, объяснение позже) "добрались" до клетки, например (1, 0) и стоим в ней. Вопрос: какой путь мы прошли? Правильно, вот он: (4, 0) (3, 0) (2, 0) И возвращается он такой функцией- членом:
(4, 0)(3, 0)(2, 0)(2, 1) или (4, 0) (4, 1) (4, 2) (3, 2) Внимание! Координаты текущей клетки в пройденныё путь не входят! \\\\\\\\\\\\\\\\ Ещё один вектор, который может нам пригодиться- вектор точек, куда мы можем пойти. Допустим, мы стоим в точке (2, 0). Можем пойти в две точки: (1, 0) или (2, 1) Вектор этих пар вернёт нам функция-член
Ещё две полезных функции-члена могут нам пригодиться: Преобразования типа, эта херь позволит перегрузить оператор [][] Это я сам придумал подачи ребят
Это возвращает вектор найденнных путей клеток
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ ++++ А теперь сосредоточимся на авторских функциях. 111111111111111 Первая функция-предикат, вот её прототип:
222222222222222222222 Вторая функция-предикат. Необходима для того, чтобы определить- очередной путь закончился или нет? А применительно к нашей задаче- создана ли ЛЮБАЯ из цепочек путей? Прототип у неё попроще будет, принимает просо указатель на объект
!!!Помним, что она пока ещё не занесена в пройденный путь!
3333333333333333333333333 А третья функция изменения. Она нужна для изменения содержания клетки. В данном примере она совсем не нужна. Так как содержимое клеток мы не меняем. Но ниже я приведу пример, когда она нужна. Прототип:
вариант прототипа конструктора
И чтобы никто не кговорил, что вот я лох, подогнал клас под одну задачу, представляю ещё две задачи, решённые таким же способом. Итак, знаменитое заполнение матрицы по спирали, стоим в левом нижнем углу, матрица 6X9 (может быть любая). За содержание функций-предикатов не пинайте, кто может сделать проще пусть напишет проще. Комменты опущу. Тут применяется функция изменения, поскольку мы изменяем клетки, заполняя их числами
Значит, у меня белая шашка это единичка, чёрные двойки, остальные ноли. Всё то же самое. Два предиката, пустое изменение, массив, создание объекта и любование результатом.
В классе есть недостатки, так я например не уверен, что всегда надо передавать матрицу в него и делать там копию. Но я для надёжности передаю всё же. В общем, правьте, уточняйте тестируйте. Говорите чё не так, буду исправлять. РАспространяется по лицензии GPL
0
|
29.07.2011, 21:59 | |
Ответы с готовыми решениями:
96
Предлагаю людям класс для написания специфических снимков системы предлагаю людям класс "каждому потоку- своё окно" для тестирования многопоточных приложений. Предлагаю заголовочный файл с реализацией функций и классов, необходимых для решения задач по комбинаторике Рекурсивный обход матрицы Написать программы, реализующие рекурсивный и итерационный методы решения задач |
быдлокодер
1724 / 911 / 106
Регистрация: 04.06.2008
Сообщений: 5,679
|
|
30.07.2011, 19:02 [ТС] | 41 |
ОК, это действенный способ окатить меня ледяным душем. Конкретизируй условия не до конечных, но: угол левый верхний или нижний (или любой, то же касается и правого угла)? Ограничение я так понял любое (будет рандомное)... вроде ничё не пропустил. Да, числа рандомные тоже? Тип?
По второму: начально где нахожусь (или где угодно?), сколько выходов может быть (или тоже сколько угодно?)
0
|
30.07.2011, 19:02 | 42 |
Мда..... Считайте, что я опять вам завидую. Минусую.
ЗЫ Вот когда хоть кто то другой скажет на форуме "kravam - крут" - это будет чего то стоить, пока об это говорите только вы - прямой путь к состоянию ламерства. Можно до умопомрачения говорить что вы написали целый класс для обхода матрицы. Но вы даже не можете толком его протестировать - т.к. мало представляете круг задач в которых это будет помощью. И как всегда не можете адекватно реагировать на критику. Только и делаете, что визжите "Я крут. Я вам счастье принес"
0
|
Делаю внезапно и красиво
1313 / 1228 / 72
Регистрация: 22.03.2011
Сообщений: 3,744
|
||||||
30.07.2011, 19:06 | 43 | |||||
Всё, мне надоела таинственность и я написал альтернативу этому классу.
Распространяется без лицензии, код принадлежит всему программирующему сообществу. Поиск происходит из любой точки во всех направлениях. Пользователю достаточно задать предикат принадлежности точки пути, предикат определения конечной точки (т.е. завершения поиска) и функцию изменения точки в матрице. А потом функция Process будет крутиться-вертеться и САМА всё за вас сделает! Воть.
1
|
быдлокодер
1724 / 911 / 106
Регистрация: 04.06.2008
Сообщений: 5,679
|
|
30.07.2011, 19:10 [ТС] | 44 |
Всё бы ничё, но многое из прочитанного мной, именно таково. То есть понятно автору и никому больше. (Я не имею ввиду С\С++, скорее это касается формата PE файлов и прочая)
Что делать? Вот что делаю я: я просто засучиваю рукава и начинаю вникать вникать и вникать. В бредятину. И ты знаешь, получается... Это тяжело. И я не гоню на авторов. А знаешь, почему? Потом, что сам пишу то, что мне трудно. Хотя формально ты прав: не можешь объяснить- не пиши. А вообще это философский вопрос- что считать приоритетом- знания языка или знания грамматики языка. Я грамотно говорю, но правил не знаю. (Хотя я уже говорил про двойные стандарты, где-то мы против того, чтобы разжевать и положить в рот, а где-то именно нужно разжевать и положить в рот) Учился бы в институте- знал бы.
0
|
Делаю внезапно и красиво
1313 / 1228 / 72
Регистрация: 22.03.2011
Сообщений: 3,744
|
||||||
30.07.2011, 19:11 | 45 | |||||
0
|
быдлокодер
1724 / 911 / 106
Регистрация: 04.06.2008
Сообщений: 5,679
|
|
30.07.2011, 19:16 [ТС] | 46 |
Не сделает.
Хотя бы: в одну и ту же точку нельзя войти дважды. Как ты в предикате будешь осуществлять проверку, был ты в этой точке или нет? У глупого меня для этого существует вектор пар пройденных пар. И он возвращается функцией методом. Её можно вызывать из предиката и проверять координаты потенциальных точек на принадлежность к такому вектору. Если они там есть- возвращается false, если нет, то bool А у умного тебя такого нет.
0
|
Делаю внезапно и красиво
1313 / 1228 / 72
Регистрация: 22.03.2011
Сообщений: 3,744
|
|
30.07.2011, 19:22 | 47 |
Что значит нет? Там так же создаётся список посещённых координат, в функции CorrectPoint. Просто я этот код под GPL буду поставлять, а остальную часть за бесплатно. Вот бесплатная всем и доступна.
Добавлено через 1 минуту Кто сказал, что нельзя? Вот Evg привёл задачу, где разрешается многократно проходить по одной и той же точке, но её "стоимость" не учитывается. Мой вариант с этой задачей справится, твой - нет. И я умный, да. Добавлено через 1 минуту Ах да, версию в виде класса и без глобальных переменных готов подарить за 100 денег на мой счёт в швейцарском банке, плиз.
0
|
быдлокодер
1724 / 911 / 106
Регистрация: 04.06.2008
Сообщений: 5,679
|
||||||
30.07.2011, 19:26 [ТС] | 48 | |||||
Deviaphan, этот ход
Я просил в GetWidth объявить локальную переменную и её же возвратить. Просьба: не компиль больше в уме, а то мой компилятор за тобой не поспевает. Добавлено через 2 минуты Deviaphan, я юмор твой оценил, всё на этом.
0
|
Делаю внезапно и красиво
1313 / 1228 / 72
Регистрация: 22.03.2011
Сообщений: 3,744
|
||||||
30.07.2011, 19:27 | 49 | |||||
0
|
быдлокодер
1724 / 911 / 106
Регистрация: 04.06.2008
Сообщений: 5,679
|
|
30.07.2011, 19:30 [ТС] | 50 |
Проблема в том, что локальная переменная должна вернуться МЕТОДОМ в main
В общем, избавь меня от необходимости уточнять и без того уточнённую просьбу. До свидания.
0
|
Делаю внезапно и красиво
1313 / 1228 / 72
Регистрация: 22.03.2011
Сообщений: 3,744
|
|
30.07.2011, 19:33 | 51 |
И снова здравствуй.
Несколькими постами выше я тебе привёл код, как из main передать локальную переменную в класс и как вернуть её из него обратно. Причём сразу двумя различными способами: непосредственно и через метод. Какие такие утончённые вопросы могут у тебя оставаться после столь конкретного ответа?
0
|
30.07.2011, 23:39 | 52 |
Принципиальной разницы нет. Я тебе просто привёл пример задач, которые в теории можно решать при помощи матрицы и универсального класса поиска пути. Какая в пень разница какие конкретные цифры и начальные точки?
С учётом того, что твой код строго засекречен, а внятного объяснения, как пользоваться этим интерфейсом нет, то непонятно, во что вообще вникать
0
|
быдлокодер
1724 / 911 / 106
Регистрация: 04.06.2008
Сообщений: 5,679
|
|
31.07.2011, 00:41 [ТС] | 53 |
Я уже решаю первую задачу. Вникать надо в шаблон тык скыть решения какой я предложил. Кто заинтересуется- тому дам и класс.
Добавлено через 13 минут И да, кстати. Если ты уж даёшь задание, то позаботься хотя бы о его некоторой корректности Вот матрица: 1 2 3 4 Начинаем с левого нижнего угла, идём в правый верхний. Сумма пройденых клеток,включая начальную и конечную должна быть не больше 6-ти. А теперь вопрос на засыпку: сколько ты видишь путей?
0
|
Делаю внезапно и красиво
1313 / 1228 / 72
Регистрация: 22.03.2011
Сообщений: 3,744
|
|
31.07.2011, 07:31 | 54 |
Ах да, там в моём коде ещё одна функция есть, которая генерирует список допустимых перемещений. А то как-то жёстко закодировал, что только в четыре соседних можно. Нехорошо поступил. Теперь можно по любым правилам перемещаться...
0
|
31.07.2011, 10:44 | 55 |
Вопросы типа "сколько путей" пользователя не должны заботить, потому как это исключительно забота твоего класса. Потому что нафига пользователю твой класс, если ему самому придётся пути перебирать?
0
|
быдлокодер
1724 / 911 / 106
Регистрация: 04.06.2008
Сообщений: 5,679
|
|
31.07.2011, 12:26 [ТС] | 56 |
А вы не пользователь. Вы задаёте задачу ученику, чтобы он протестил класс, вы учитель. Я потом скажу: путей столько-то, а вы сверите с ответом. Учитель задаёт задачу (это ваша задача, кстати) и он должен знать ответ. Задача проще некуда. Так каков ответ?
(А за меня решение найдёт мой класс, а вы решение уже должны знать).
0
|
31.07.2011, 12:33 | 57 |
Я не учитель. Ровно так же, как не пионервожатый и не воспитатель. Я тебе обозначил направление, в котором двигаться, но вести тебя за ручку не собираюсь. Если при такой общей постановке вопроса ты не в состоянии самостоятельно поставить сам себе конкретную задачу, то лучше завязывай с программированием
0
|
быдлокодер
1724 / 911 / 106
Регистрация: 04.06.2008
Сообщений: 5,679
|
|
31.07.2011, 13:06 [ТС] | 58 |
Да я-то в состоянии, я давно уже поставил. А вы не удосужились этого сделать. Причём сделать надо было МИНИМУМ. Но западло, ладно. Ну раз вам западло, то вот: ваша задача имеет бесконечное множество решений. Тут любой класс крякнет. Думать надо прежде чем говорить.
0
|
Делаю внезапно и красиво
1313 / 1228 / 72
Регистрация: 22.03.2011
Сообщений: 3,744
|
|
31.07.2011, 13:16 | 60 |
Ничего подобного. Задача была чётко ограничена двумя условиями: "стоимостью" пути и максимальным количеством шагов. Соответственно, количество решений конечно.
0
|
31.07.2011, 13:16 | |
31.07.2011, 13:16 | |
Помогаю со студенческими работами здесь
60
Предлагаю людям как усовершенствовать IDE Dev-Cpp 4.9.9.2 Рекурсивный обход. Не могу сделать табуляцию. Обход с выводом имен файлов Составьте программы для решения следующих задач обработки строк, столбцов и диагоналей матрицы предлагаю программу людям "альтернативное копирование файлов в проводнике" Решение задач на С++ (написание программы для решения задач) Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |