Гость
Войти | Профиль | Очистить
Целевая тема:
Создать новую тему:
Автор:
Действия ...
Форумы / Oracle [игнор отключен] [закрыт для гостей] / Помощь с рекурсией и графами / 14 сообщений из 14, страница 1 из 1
21.11.2014, 11:27
    #38812858
sektorist
sektorist
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Помощь с рекурсией и графами
Добрый день, есть такая задача:
В таблице содержится информация о произвольном наборе косточек домино (левое число косточки, правое число косточки). Создать программу для определения списка “рыбных” ситуаций (т.е. ситуаций, когда остается одна или более косточек исходного набора, которые некуда положить) и количества таких ситуаций.

Реализовать надо на PL/SQl, но функциями и процедурами пользоваться нельзя, только циклы и условные операторы.

Суть в том, что я не понимаю как сделать рекурсию на начальный элемент? То есть допустим цепочка доходит до последнего элемента, мы выводим её на экран, как опять вернуться на узел выбора последнего элемента? После чего, если все возможные варианты последнего элемента выбраны вернуться уже к предпоследнему, поменять его и опять выбирать последние? И так далее до самого первого элемента. Конечно можно написать огромное количество циклов, но как по мне - должно быть иное решение.

Очень надеюсь на ваши подсказки, заранее спасибо.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
21.11.2014, 11:36
    #38812875
123йй
123йй
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Помощь с рекурсией и графами
sektorist,

STFF
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
27.11.2014, 12:53
    #38818285
sektorist
sektorist
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Помощь с рекурсией и графами
Что то поиск никаких положительных вариантов не родил(
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
27.11.2014, 12:59
    #38818294
varlamovvp
varlamovvp
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Помощь с рекурсией и графами
sektorist,

ну тут банально надо обойти дерево вариантов
вот только как пользоваться рекурсией, если нельзя пользоваться процедурами и функциями?
на этот вопрос у меня нет ответа

P.S. рекурсия (почти) всегда заменяется нерекурсивным алгоритмом
но она часто более читабельна и удобна
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
27.11.2014, 13:02
    #38818301
varlamovvp
varlamovvp
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Помощь с рекурсией и графами
sektorist,

кстати, интересно, но мне так кажется что на SQL эту задачу решить гораздо проще.
Вам разрешено внутрь PL/SQL вставить SQL?
если да - тогда вперед!
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
27.11.2014, 13:33
    #38818332
expel
expel
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Помощь с рекурсией и графами
sektorist,

Вообщем выкатывайте вашу таблицу с произвольным набором и ответ который ожидаете получить.
Будем фигачить одним запросом :D
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
27.11.2014, 13:41
    #38818343
Sayan Malakshinov
Sayan Malakshinov
Модератор форума
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Помощь с рекурсией и графами
Задача чисто алгоритмическая: берешь любой алгоритм для connected elements /groups,например, weighted quick-union algorithm и тупо кодишь
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
27.11.2014, 13:43
    #38818347
Sayan Malakshinov
Sayan Malakshinov
Модератор форума
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Помощь с рекурсией и графами
Ой, неправильно прочитал задание - но за основу вышенаписанное пойдет
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
27.11.2014, 13:52
    #38818366
dbms_photoshop
dbms_photoshop
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Помощь с рекурсией и графами
varlamovvpрекурсия (почти) всегда заменяется нерекурсивным алгоритмомкоторый работает быстрее: 15415737
expelsektorist,

Вообщем выкатывайте вашу таблицу с произвольным набором и ответ который ожидаете получить.
Будем фигачить одним запросом :DЯ могу за ТС.
Есть начальный набор костей:
Код: plsql
1.
2.
3.
4.
select distinct least(id1,id2) id1, greatest(id1,id2) id2
from
(select rownum-1 id1 from dual connect by level <= 7),
(select rownum-1 id2 from dual connect by level <= 7)

Получить вывод типа такого:
Код: plsql
1.
end1 end2 remaining_pairs

Где первые два столбца - числа с обоих концов, а третий - конкатенация оставшихся костяшек.

PS. Решать мне пока некогда.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
27.11.2014, 14:10
    #38818390
dbms_photoshop
dbms_photoshop
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Помощь с рекурсией и графами
Хотя тут и решать видимо ничего не надо.
Максимальное число оставшихся костей для каждой из комбинаций 15
Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
with t
     as (select distinct least(id1, id2) id1, greatest(id1, id2) id2
           from (select rownum - 1 id1
                   from dual
                 connect by level <= 7)
               ,(select rownum - 1 id2
                   from dual
                 connect by level <= 7))
select t1.*, 28 - count(1) cnt
  from t t1 join t t2 on (t1.id1 = t2.id1 or t1.id1 = t2.id2 or t1.id2 = t2.id1 or t1.id2 = t2.id2)
 where t1.id1 <> t1.id2
group by t1.id1, t1.id2
order by 1, 2

Также очевидно их может быть 14, 13, ..., 1.
Соответственно число возможных рыб: 21 * (1 + 15)/2 = 168 если я ничего не упустил.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
27.11.2014, 14:20
    #38818407
dbms_photoshop
dbms_photoshop
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Помощь с рекурсией и графами
dbms_photoshopесли я ничего не упустил.А я очевидно кое-что упустил.
Концы могут быть одинаковые. То есть их всего 28 а не 21.
Для одинаковых и не одинаковых концов разное число возможных оставшихся на руках.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
27.11.2014, 16:50
    #38818573
sektorist
sektorist
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Помощь с рекурсией и графами
Ну как я понимаю(а я понимаю скорее всего неправильно) то можно воспользоваться алгоритмом нерекурсивного обхода графа в глубь. Но вот в чем мой затык, причем во всех попытках и всех , сделанных мною вариантах, когда я дохожу до конечного элемента в цепочке, то помечаю его как посещённый, сдвигаюсь на предыдущий элемент, последний уже помеченный и на него не попадаю, и это правильно, сдвигаюсь ещё на один назад и вот в этот момент тот последний который был помечен, должен стать не помеченным, но как и в какой момент это реализовать - я не понимаю, или может мой ход мысли вообще неправильный? в кратце я делаю так - записываю первую кость , ищу к ней совпадение, если есть, то ставлю на место первой кости и помечаю как посещенную, и дальше проделываю тоже самое со второй и так далее в цикле, потом дохожу до последний и тут затык описанный выше. Как быть?)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
27.11.2014, 19:24
    #38818763
Sayan Malakshinov
Sayan Malakshinov
Модератор форума
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Помощь с рекурсией и графами
sektorist,

решение "в лоб" достаточно примитивно. Можно отталкнуться от:
1. всего разных костей 28, поэтому наборы можно экономично хранить в массиве на 28 элементов
2. все решения можно представить в виде деревьев, где корнями будут являться все варианты расположения костей.
3 каждая вершина дерева при решении может содержать необработанный остаток исходного набора
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.11.2014, 11:28
    #38819239
sektorist
sektorist
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Помощь с рекурсией и графами
xtender,

1) Что значит хранить наборы в массиве на 28 элементов? - я так понял, что есть один массив на 28 элементов и каждый раз он перезаписывается?
2) В качестве корней вы имеете в виду, что в начале очереди должны быть все вершины по очереди? - это я в целом так и делал.
3) На счет третьего пункта вообще не очень понял.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
Форумы / Oracle [игнор отключен] [закрыт для гостей] / Помощь с рекурсией и графами / 14 сообщений из 14, страница 1 из 1
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение  
Полит. конфиден.  
созд. / загр.: 381ms
Закрыть
start [/forum/topic.php?fid=52&mobile=1&tid=1892547]:
 0ms
get settings:
 9ms
get forum list:
 16ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 51ms
get topic data:
 9ms
get forum data:
 2ms
get page messages:
 48ms
get tp. blocked users:
 1ms
others: 239ms
total:  381ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]