Deutsch
Germany.ruФорумы → Архив Досок→ Программирование

Как решать подобные задачи?

2077  1 2 3 все
AlexNek патриот07.01.24 21:00
AlexNek
NEW 07.01.24 21:00 

Вот знакомый спросил, может ли ему машина помочь решить головоломку. Сдуру сказал конечно же. Теперь дали порешатьсмущ

Есть несколько пересекающихся перемещений

А:1,8,9,5,1

Б:1,5,9,8,1

С:1,5,4,3,2,1

Д:6,7,8,9,10,6


Есть также начальное состояние и конечное.

Задача - построить цепочку перемещений из начального состояния в конечное

Пример:

Начальное


Конечное

Перемещения

Д,Б,А
#1 
alex445 коренной житель07.01.24 23:28
NEW 07.01.24 23:28 
в ответ AlexNek 07.01.24 21:00
AlexNek патриот07.01.24 23:48
AlexNek
07.01.24 23:48 
в ответ alex445 07.01.24 23:28
Поиск числа простых циклов графа.

никак не могу это всё связать смущ

То что переходы можно описать графом понятно. Но вот искать то что?

#3 
alex445 коренной житель08.01.24 00:55
NEW 08.01.24 00:55 
в ответ AlexNek 07.01.24 23:48, Последний раз изменено 08.01.24 01:01 (alex445)

Простые циклы, как я понял. Хотя описание задачи так себе.


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


Только поле не двухмерное, а любая случайная структура. Лучше тут, наверное. Разве что дерево замкнутое - локально (местные циклы) или полностью. Но замкнутым оно становится лишь когда дошли до вершины, в которой уже были, а так в принципе этому алгоритму должно быть всё равно, по какой структуре ходить - всё в основном определяется в условиях на каждой итерации.


Проще всего, наверное, рекурсией сделать, если граф не большой.

#4 
Murr патриот08.01.24 02:15
Murr
NEW 08.01.24 02:15 
в ответ AlexNek 07.01.24 23:48

никак не могу это всё связать

------

Описание задачи поправь - Я не понял что требуется.

#5 
AlexNek патриот08.01.24 17:48
AlexNek
NEW 08.01.24 17:48 
в ответ Murr 08.01.24 02:15
Я не понял что требуется

Похоже самый полезный коммент смущ


Попробуем... Кубик рубика то знаешь. Вот что то типа этого только сильно проще и в 2Д.

Есть 3 оси вращения, показанные цветными стрелками в первом посте. Вместо цифр нарисованы картинки.

Вначале картинки разбросаны "случайным" образом, в задаче требуется их разместить в определенном порядке.

Нужен алгоритм который указывает как именно нужно вращать "кольца" чтобы разместить картинки в определенном порядке.


Давай тогда начинать с того что еще непонятно.

#6 
AlexNek патриот08.01.24 17:51
AlexNek
NEW 08.01.24 17:51 
в ответ alex445 08.01.24 00:55
Хотя описание задачи так себе

ну вот с этого и надо было начинать...

Когда через пару дней читаешь видишь тоже по другому. смущ

#7 
Murr патриот08.01.24 19:37
Murr
NEW 08.01.24 19:37 
в ответ AlexNek 08.01.24 17:48

Чем и как определяется порядок?

#8 
AlexNek патриот08.01.24 19:55
AlexNek
NEW 08.01.24 19:55 
в ответ Murr 08.01.24 19:37
Чем и как определяется порядок?

В реальности - Начальная позиция вычисляется приложением для конкретного устройства/пользователя, конечная всегда остаётся фиксированной. /Картинка нарисована как должно быть./

Для расчётов - и начальная и конечная позиции задаются. В примерах это цифры на определённых местах


Можно даже попроще задание сделать, не нужны все повороты для перехода от исходной позиции к заданной.

Можно как в кубике Рубика, знать переходы для обмена двух элементов не стоящих на своем месте. Потому как поставить большинство позиций на правильные места можно относительно быстро вручную. Но вот постоянно два элемента остаются на неправильных позициях.

#9 
Murr патриот08.01.24 20:08
Murr
NEW 08.01.24 20:08 
в ответ AlexNek 08.01.24 19:55

Решение - вытряхни картинки в кучу и разложи как требуется.

#10 
AlexNek патриот08.01.24 20:15
AlexNek
NEW 08.01.24 20:15 
в ответ Murr 08.01.24 20:08
Решение - вытряхни картинки в кучу и разложи как требуется.

Не подходит. Есть только 4 кнопки которые можно нажимать Они вращают "круги". Вот последовательность нажатий и требуется найти.

Ты же не говоришь, что вот разбей кубик Рубика, а после сложи.

#11 
alex445 коренной житель08.01.24 21:22
NEW 08.01.24 21:22 
в ответ AlexNek 08.01.24 19:55, Последний раз изменено 08.01.24 21:30 (alex445)

Как от этого


"Есть также начальное состояние и конечное.

Задача - построить цепочку перемещений из начального состояния в конечное"


перейти к этому


"Есть 3 оси вращения, показанные цветными стрелками в первом посте. Вместо цифр нарисованы картинки.

Вначале картинки разбросаны "случайным" образом, в задаче требуется их разместить в определенном порядке.

Нужен алгоритм который указывает как именно нужно вращать "кольца" чтобы разместить картинки в определенном порядке."


???


вот разбей кубик Рубика, а после сложи

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

#12 
AlexNek патриот08.01.24 21:47
AlexNek
NEW 08.01.24 21:47 
в ответ alex445 08.01.24 21:22
Как от этого...перейти к этому...

Так не нужно переходить. Поначалу специально хотел абстрагироваться от конкретной задачи.

Если говорить про путь Эйлера, то необязательно переходить к мостам через реку. спок


Но опять отвлечение. Теперь задача более понятна или еще нет?

#13 
alex445 коренной житель08.01.24 22:51
NEW 08.01.24 22:51 
в ответ AlexNek 08.01.24 21:47, Последний раз изменено 08.01.24 22:54 (alex445)

Нет, не понятно. И сравнение с "кубик-рубиком" лишь путает. У кубик-рубика "картинки" связаны с осями вращения - поменяв одну картинку, поменяется группа других. А у вас непонятно, есть ли связи и какие - какие оси на какие картинки как влияют.

#14 
AlexNek патриот08.01.24 23:00
AlexNek
NEW 08.01.24 23:00 
в ответ alex445 08.01.24 22:51

То есть синие и зеленые стрелки ни о чём не говорят?

Я тут нашел картинки, надо только нужно "выкусить".

#15 
AlexNek патриот08.01.24 23:22
AlexNek
NEW 08.01.24 23:22 
в ответ alex445 08.01.24 22:51

вот решение для конкретного расположения

Walkthrough: B, B, B, B, A, A, D, D, D, D, A, D, D, D.

А вот что прислали, там только змея и кабан не на своём месте

А теперь с цифрами

А теперь оставляем только цифры и делаем что то типа графа

#16 
Murr патриот08.01.24 23:48
Murr
NEW 08.01.24 23:48 
в ответ AlexNek 08.01.24 20:15

Помнится был чемпионат по разламыванию кубика-рубика...


По задаче - какие кнопки? откуда?

По прежнему - непонятно с чем надо работать.


Была такая головоломка - Волшебные шарики - можно долго гонять, а можно - построить граф.

#17 
AlexNek патриот09.01.24 00:03
AlexNek
NEW 09.01.24 00:03 
в ответ Murr 08.01.24 23:48, Последний раз изменено 09.01.24 00:04 (AlexNek)
По задаче - какие кнопки? откуда?

На картинке выше не видно разве кнопок с красными стрелками?


#18 
alex445 коренной житель09.01.24 00:34
NEW 09.01.24 00:34 
в ответ Murr 08.01.24 23:48

По задаче - какие кнопки? откуда?

По прежнему - непонятно с чем надо работать.

Да в игрульки он играет. Донатить поди не хочет. ))

#19 
alex445 коренной житель09.01.24 00:37
NEW 09.01.24 00:37 
в ответ AlexNek 09.01.24 00:03
На картинке выше не видно разве кнопок с красными стрелками?

И что они могут означать? Там хоть всплывающие подсказки есть?

#20 
1 2 3 все