Задачи обхода лабиринта
- Обход лабиринта: классическая постановка задачи
- Решение по ?правилу правой руки?; хранение истории для предотвращения циклов
- Решение ?заливкой?; определение маршрута по номеру шага
- Общая постановка задачи
- Множество состояний поля: исходное (И) ? промежуточные (П) ? финальное (Ф)
- Правила перехода из состояния в состояние
Задача: проверить достижимость И ? Ф или минимальную длину преобразования И ? ? ? Ф
- Дополнительные ограничения
Объем входных данных ~ Na (a==2 в случае простого лабиринта)
Размер истории ~ Na (состояния не зависят от пути)
- Алгоритмы генерации простого лабиринта
Домашнее задание
Задача обхода лабиринта: см. предыдущее задание
Генератор: см. материалы прошлого года, не забыть о генерации лабиринта с циклами
Колесо разделено на K секторов, в каждом из которых находится число P0, P1, ? , PK. Вначале стрелка указывает на P1, после поворота колеса ? на P2 и так далее по кругу (?,Pk-1,PK, P1, P2,?). Вводится число A, На i-м шаге выбирается произвольная арифметическая операция среди ?+?, ?-? и ?*? и применяется к A и Pi (более точно Ai=Ai-1 +/-/* Pi%K ), после чего колесо поворачивается. Написать программу, которая определяет минимальное количество действий, которые нужно проделать для получения числа B из числа A (A<B). Pi, A, B и промежуточные значения не меньше 0 и не больше B*B.
Другая формулировка: в формуле (((?((A?P1)?P2)??PK-1)?PK)?P1)?P2)?)=B вместо знаков ??? расставить знаки арифметических операций таким образом, чтобы равенство выполнялось, а длина формулы была минимальной.
В случае, когда {Pi}={1?K}
В случае, когда {Pi} ? произвольное, но гарантируется достижимость B из A
- В случае, когда достижимость не гарантируется (возможен ответ "B нельзя получить из A")
Для четырех операций: ?+?, ?-?, ?*? и ?//?, где // ? это целочисленное деление (соответственно, X/Y*Y может быть не равно X)
- ? + вывести формулу
Рассмотреть случай, когда на числа и промежуточные результаты не накладывается ограничений. Можно ли определить, что B недостижимо из A?
Ввод: K чисел через пробел, на следующей строке ? A и B
Вывод: количество операций (или формула, если это требуется), НЕТ при недостижимости
Условные обозначения
? тема по Linux - ?? тема повышенной сложности
? теоретическое задание 
? тема для самостоятельного изучения