ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Oracle [игнор отключен] [закрыт для гостей] / Помощь с рекурсией и графами
14 сообщений из 14, страница 1 из 1
Помощь с рекурсией и графами
    #38812858
sektorist
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
sektorist
Гость
Добрый день, есть такая задача:
В таблице содержится информация о произвольном наборе косточек домино (левое число косточки, правое число косточки). Создать программу для определения списка “рыбных” ситуаций (т.е. ситуаций, когда остается одна или более косточек исходного набора, которые некуда положить) и количества таких ситуаций.

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

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

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

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

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

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

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

Вообщем выкатывайте вашу таблицу с произвольным набором и ответ который ожидаете получить.
Будем фигачить одним запросом :D
...
Рейтинг: 0 / 0
27.11.2014, 13:33
| Ответить | Цитировать | Написать  
Помощь с рекурсией и графами
    #38818343
Фотография Sayan Malakshinov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Sayan Malakshinov
Модератор форума
Задача чисто алгоритмическая: берешь любой алгоритм для connected elements /groups,например, weighted quick-union algorithm и тупо кодишь
...
Рейтинг: 0 / 0
27.11.2014, 13:41
| Ответить | Цитировать | Написать  
Помощь с рекурсией и графами
    #38818347
Фотография Sayan Malakshinov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Sayan Malakshinov
Модератор форума
Ой, неправильно прочитал задание - но за основу вышенаписанное пойдет
...
Рейтинг: 0 / 0
27.11.2014, 13:43
| Ответить | Цитировать | Написать  
Помощь с рекурсией и графами
    #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, 13:52
| Ответить | Цитировать | Написать  
Помощь с рекурсией и графами
    #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:10
| Ответить | Цитировать | Написать  
Помощь с рекурсией и графами
    #38818407
Фотография dbms_photoshop
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
dbms_photoshop
Участник
dbms_photoshopесли я ничего не упустил.А я очевидно кое-что упустил.
Концы могут быть одинаковые. То есть их всего 28 а не 21.
Для одинаковых и не одинаковых концов разное число возможных оставшихся на руках.
...
Рейтинг: 0 / 0
27.11.2014, 14:20
| Ответить | Цитировать | Написать  
Помощь с рекурсией и графами
    #38818573
sektorist
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
sektorist
Гость
Ну как я понимаю(а я понимаю скорее всего неправильно) то можно воспользоваться алгоритмом нерекурсивного обхода графа в глубь. Но вот в чем мой затык, причем во всех попытках и всех , сделанных мною вариантах, когда я дохожу до конечного элемента в цепочке, то помечаю его как посещённый, сдвигаюсь на предыдущий элемент, последний уже помеченный и на него не попадаю, и это правильно, сдвигаюсь ещё на один назад и вот в этот момент тот последний который был помечен, должен стать не помеченным, но как и в какой момент это реализовать - я не понимаю, или может мой ход мысли вообще неправильный? в кратце я делаю так - записываю первую кость , ищу к ней совпадение, если есть, то ставлю на место первой кости и помечаю как посещенную, и дальше проделываю тоже самое со второй и так далее в цикле, потом дохожу до последний и тут затык описанный выше. Как быть?)
...
Рейтинг: 0 / 0
27.11.2014, 16:50
| Ответить | Цитировать | Написать  
Помощь с рекурсией и графами
    #38818763
Фотография Sayan Malakshinov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Sayan Malakshinov
Модератор форума
sektorist,

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

1) Что значит хранить наборы в массиве на 28 элементов? - я так понял, что есть один массив на 28 элементов и каждый раз он перезаписывается?
2) В качестве корней вы имеете в виду, что в начале очереди должны быть все вершины по очереди? - это я в целом так и делал.
3) На счет третьего пункта вообще не очень понял.
...
Рейтинг: 0 / 0
28.11.2014, 11:28
| Ответить | Цитировать | Написать  
14 сообщений из 14, страница 1 из 1
Форумы / Oracle [игнор отключен] [закрыт для гостей] / Помощь с рекурсией и графами
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=52&msg=38812858&tid=1892547]:
 0ms
get settings:
 8ms
get forum list:
 15ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 47ms
get topic data:
 10ms
get forum data:
 2ms
get page messages:
 51ms
get tp. blocked users:
 2ms
others: 224ms
total:  365ms
созд. / загр.: 365ms
x
x
Закрыть


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