Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Oracle Новый топик    Ответить
Топик располагается на нескольких страницах: Ctrl  назад   1 [2] 3 4 5   вперед  Ctrl      все
 Re: пятничная задачка (про) коня  [new]
ukku
Member

Откуда: 59
Сообщений: 195
orawish, по чуть-чуть нельзя( - это ж брутфорс. Первые 63 этапа могут быть логичные, а вот 64ий не сойдется.
А никто не считал, сколько в теории верных результатов? А то у мя уже час считается, чую надо будет ждать маленькую вечность с тупым перебором.
2 апр 12, 16:06    [12352308]     Ответить | Цитировать Сообщить модератору
 Re: пятничная задачка (про) коня  [new]
orawish
Member

Откуда: Гадюкино-2 (City)
Сообщений: 15487
ukku,

ваш алгоритм, похоже, скорее мёртв, чем жив.
не позднее 19 хода он фатально ошибается и весело продолжает скакать по первому возможному варианту до 60-го
на 60-м ходов не остается совсем и начинается вечный балет по перемалыванию заведомо неживого хвоста
(из минимум ~сорока одного уровня)
2 апр 12, 16:32    [12352515]     Ответить | Цитировать Сообщить модератору
 Re: пятничная задачка (про) коня  [new]
mayton
Member

Откуда: loopback
Сообщений: 49800
orawish
SQL> with tt as (select  1 dx , 2 dy from dual
  2  	   union select  1    ,-2    from dual
  3  	   union select  2    , 1    from dual
  4  	   union select  2    ,-1    from dual
  5  	   union select -1    , 2    from dual
  6  	   union select -1    ,-2    from dual
  7  	   union select -2    , 1    from dual
  8  	   union select -2    ,-1    from dual
 ..
101  	;удачи!

Тут можно расширить постановку и искать обходы не только конём но и королём, ферзём
и произвольной фигурой которая ходит вовсе не по правилам шахмат.
2 апр 12, 16:34    [12352533]     Ответить | Цитировать Сообщить модератору
 Re: пятничная задачка (про) коня  [new]
-2-
Member

Откуда:
Сообщений: 15330
mayton
и произвольной фигурой которая ходит вовсе не по правилам шахмат.
и по площади занимает произвольные 8х8 клеток шахматной доски.
2 апр 12, 16:38    [12352555]     Ответить | Цитировать Сообщить модератору
 Re: пятничная задачка (про) коня  [new]
ukku
Member

Откуда: 59
Сообщений: 195
Поэтому и назвал тупым перебором :) Кто дойдет до 64 только тот и будет верный. Ладно хватит работать сегодня, надо будет завтра подумать чтобы заведомо не верные отсекались.
2 апр 12, 16:38    [12352557]     Ответить | Цитировать Сообщить модератору
 Re: пятничная задачка (про) коня  [new]
dbms_photoshop
Member

Откуда: sqlmdx.net
Сообщений: 5151
orawish
ну так за чем же дело стало? вперёд! ;)
Первое, что приходит на ум - воспользоваться правилом Варнсдорфа. Если вдруг не сошлось - вернуться до того момента когда был выбор из нескольких и выбрать другое. Если опять не сошлось - опять вернуться и т. д.
Если ~перебором - то решать задачу для половины доски как рекомендуют здесь, при этом так чтоб конь из конечного положения мог заскочить на другую половину. Потом подход повторить.
Но слишком много рутины - это отталкивает от задачи.
2 апр 12, 23:12    [12354225]     Ответить | Цитировать Сообщить модератору
 Re: пятничная задачка (про) коня  [new]
orawish
Member

Откуда: Гадюкино-2 (City)
Сообщений: 15487
dbms_photoshop
orawish
ну так за чем же дело стало? вперёд! ;)
Первое, что приходит на ум - воспользоваться правилом Варнсдорфа. Если вдруг не сошлось - вернуться до того момента когда был выбор из нескольких и выбрать другое. Если опять не сошлось - опять вернуться и т. д.
Если ~перебором - то решать задачу для половины доски как рекомендуют здесь, при этом так чтоб конь из конечного положения мог заскочить на другую половину. Потом подход повторить.
Но слишком много рутины - это отталкивает от задачи.

насколько я понимаю, решение от ukku и есть инкарнация алгоритма Варнсдорфа, по сути - тот же перебор.
т.е. сам по себе, без дополнительных приседаний - абсолютно никаких шансов
3 апр 12, 00:18    [12354380]     Ответить | Цитировать Сообщить модератору
 Re: пятничная задачка (про) коня  [new]
dbms_photoshop
Member

Откуда: sqlmdx.net
Сообщений: 5151
orawish,

Абсолютно нет.
Правило Варнсдорфа
При обходе доски коня следует всякий раз ставить на поле, из которого он может сделать наименьшее число ходов на еще не пройденные поля; если таких полей несколько, то можно выбрать любое из них.
3 апр 12, 00:29    [12354391]     Ответить | Цитировать Сообщить модератору
 Re: пятничная задачка (про) коня  [new]
orawish
Member

Откуда: Гадюкино-2 (City)
Сообщений: 15487
dbms_photoshop
orawish,

Абсолютно нет.
Правило Варнсдорфа
При обходе доски коня следует всякий раз ставить на поле, из которого он может сделать наименьшее число ходов на еще не пройденные поля; если таких полей несколько, то можно выбрать любое из них.

согласен. (посмотрел в код :) в части алгоритма выбора - принципиально разные подходы.
3 апр 12, 00:49    [12354437]     Ответить | Цитировать Сообщить модератору
 Re: пятничная задачка (про) коня  [new]
ukku
Member

Откуда: 59
Сообщений: 195
Метод Варнсдорфа pl-sql-ный отрабатывает за 15 сотых секунд.
Sql-ый вариант не справился за 990 минут :) Ни у кого идей нету, как на sql можно реализовать "память"? Чтобы запоминать, где конь уже был (кроме connect nocycle)
3 апр 12, 10:17    [12355220]     Ответить | Цитировать Сообщить модератору
 Re: пятничная задачка (про) коня  [new]
wurdu
Member

Откуда: Владивосток
Сообщений: 4441
ukku
Метод Варнсдорфа pl-sql-ный отрабатывает за 15 сотых секунд.
Sql-ый вариант не справился за 990 минут :) Ни у кого идей нету, как на sql можно реализовать "память"? Чтобы запоминать, где конь уже был (кроме connect nocycle)
Через recursive subquery factoring можно, но там куча ограничений на запрос.
3 апр 12, 10:25    [12355264]     Ответить | Цитировать Сообщить модератору
 Re: пятничная задачка (про) коня  [new]
orawish
Member

Откуда: Гадюкино-2 (City)
Сообщений: 15487
ukku
Метод Варнсдорфа pl-sql-ный отрабатывает за 15 сотых секунд.
Sql-ый вариант не справился за 990 минут :) Ни у кого идей нету, как на sql можно реализовать "память"? Чтобы запоминать, где конь уже был (кроме connect nocycle)

вы же траекторию рисуете - в ней всё есть
3 апр 12, 10:48    [12355401]     Ответить | Цитировать Сообщить модератору
 Re: пятничная задачка (про) коня  [new]
mayton
Member

Откуда: loopback
Сообщений: 49800
ukku
Метод Варнсдорфа pl-sql-ный отрабатывает за 15 сотых секунд.
Sql-ый вариант не справился за 990 минут :) Ни у кого идей нету, как на sql можно реализовать "память"? Чтобы запоминать, где конь уже был (кроме connect nocycle)

В классике алгоритмизации это состояние хранит стек рекурсии. Попытка развернуть это
в таблицу - конечно оригинально - но будет антипаттерном с точки зрения ресурсов IMHO.
3 апр 12, 12:05    [12355915]     Ответить | Цитировать Сообщить модератору
 Re: пятничная задачка (про) коня  [new]
ukku
Member

Откуда: 59
Сообщений: 195
mayton
Попытка развернуть это в таблицу - конечно оригинально - но будет антипаттерном с точки зрения ресурсов IMHO.

Смысл извращения в самом извращение :) Надо было б написать по-человечески взяли бы плюсы или тому подобное.
3 апр 12, 12:14    [12355991]     Ответить | Цитировать Сообщить модератору
 Re: пятничная задачка (про) коня  [new]
mayton
Member

Откуда: loopback
Сообщений: 49800
В прошлом году мы где-то доказывали полноту языка SQL по Тьюрингу.
Если доказали то можно решить любую задачку.
3 апр 12, 12:28    [12356151]     Ответить | Цитировать Сообщить модератору
 Re: пятничная задачка (про) коня  [new]
dbms_photoshop
Member

Откуда: sqlmdx.net
Сообщений: 5151
mayton
В прошлом году мы где-то доказывали полноту языка SQL по Тьюрингу.
Если доказали то можно решить любую задачку.
1-е апреля было позавчера.
3 апр 12, 12:54    [12356428]     Ответить | Цитировать Сообщить модератору
 Re: пятничная задачка (про) коня  [new]
mayton
Member

Откуда: loopback
Сообщений: 49800
dbms_photoshop
mayton
В прошлом году мы где-то доказывали полноту языка SQL по Тьюрингу.
Если доказали то можно решить любую задачку.
1-е апреля было позавчера.

Не важно. Жанр пятничных задачек мне интересен вне зависимости от праздников.
Просто не понятна была глубина извращённости решения которую хотел получить
автор.
3 апр 12, 12:58    [12356466]     Ответить | Цитировать Сообщить модератору
 Re: пятничная задачка (про) коня  [new]
orawish
Member

Откуда: Гадюкино-2 (City)
Сообщений: 15487
dbms_photoshop
mayton
В прошлом году мы где-то доказывали полноту языка SQL по Тьюрингу.
Если доказали то можно решить любую задачку.
1-е апреля было позавчера.

offtop:

кстати, про первое апреля (тема же как раз от этого числа)
признаться, ждал, что первым решением будет селект из дуала заранее понятно какой строки.
:)
3 апр 12, 13:30    [12356755]     Ответить | Цитировать Сообщить модератору
 Re: пятничная задачка (про) коня  [new]
ukku
Member

Откуда: 59
Сообщений: 195
orawish
dbms_photoshop
пропущено...
1-е апреля было позавчера.

offtop:
кстати, про первое апреля (тема же как раз от этого числа)
признаться, ждал, что первым решением будет селект из дуала заранее понятно какой строки.
:)

Была мысль стишок из вики распарсить )
3 апр 12, 13:41    [12356850]     Ответить | Цитировать Сообщить модератору
 Re: пятничная задачка (про) коня  [new]
dbms_photoshop
Member

Откуда: sqlmdx.net
Сообщений: 5151
orawish,

Мне как-то сразу показалось, что на вход поступает начальная позиция, на выходе - маршрут.
Если начальная позиция любая, то есс-но задача особого смысла не имеет.
3 апр 12, 14:12    [12357172]     Ответить | Цитировать Сообщить модератору
 Re: пятничная задачка (про) коня  [new]
_bob
Member

Откуда: Москва
Сообщений: 1654
ukku
Метод Варнсдорфа pl-sql-ный отрабатывает за 15 сотых секунд.
Sql-ый вариант не справился за 990 минут :) Ни у кого идей нету, как на sql можно реализовать "память"? Чтобы запоминать, где конь уже был (кроме connect nocycle)


память реализуется записью в табличку
у меня подобная задача считалась за ночь
метод решения - построение дерева всех возможных ходов, с проверками на "такое уже было"
3 апр 12, 16:23    [12358610]     Ответить | Цитировать Сообщить модератору
 Re: пятничная задачка (про) коня  [new]
orawish
Member

Откуда: Гадюкино-2 (City)
Сообщений: 15487
dbms_photoshop
orawish,

Мне как-то сразу показалось, что на вход поступает начальная позиция, на выходе - маршрут.
Если начальная позиция любая, то есс-но задача особого смысла не имеет.

недопонял я, про что вы.
если решение циклическое, то начальная позиция для него - любая.
(т.е. если замкнёте, то решать можно, начиная с какой хотите позиции)
3 апр 12, 17:52    [12359483]     Ответить | Цитировать Сообщить модератору
 Re: пятничная задачка (про) коня  [new]
dbms_photoshop
Member

Откуда: sqlmdx.net
Сообщений: 5151
orawish
dbms_photoshop
orawish,

Мне как-то сразу показалось, что на вход поступает начальная позиция, на выходе - маршрут.
Если начальная позиция любая, то есс-но задача особого смысла не имеет.

недопонял я, про что вы.
если решение циклическое, то начальная позиция для него - любая.
(т.е. если замкнёте, то решать можно, начиная с какой хотите позиции)
Начиная с произвольной - неинтересно.
В этом решении можно увидеть определенные закономерности и заставить двигаться коня согласно их:
Картинка с другого сайта.
То же самое касательно закономерностей здесь:
Картинка с другого сайта.
А вот если на входе может быть любое поле, а не a1 это уже интересней.
3 апр 12, 18:30    [12359704]     Ответить | Цитировать Сообщить модератору
 Re: пятничная задачка (про) коня  [new]
mayton
Member

Откуда: loopback
Сообщений: 49800
Я и предлагал рассмотреть самый общий случай.
И поле - произвольной области. Не прямогуольное.
Или объединение множества прямогольников.
Или лабиринт.
3 апр 12, 18:33    [12359734]     Ответить | Цитировать Сообщить модератору
 Re: пятничная задачка (про) коня  [new]
orawish
Member

Откуда: Гадюкино-2 (City)
Сообщений: 15487
mayton
Я и предлагал рассмотреть самый общий случай.
И поле - произвольной области. Не прямогуольное.
Или объединение множества прямогольников.
Или лабиринт.

а кто против? во всяком случае - я не против.
рассматривайте
3 апр 12, 19:06    [12359949]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: Ctrl  назад   1 [2] 3 4 5   вперед  Ctrl      все
Все форумы / Oracle Ответить