Задачи обхода лабиринта

• Обход лабиринта: классическая постановка задачи
  • Решение по «правилу правой руки»; хранение истории для предотвращения циклов
  • Решение «заливкой»; определение маршрута по номеру шага
• Общая постановка задачи
  1. Множество состояний поля: исходное (И) → промежуточные (П) → финальное (Ф)
  2. Правила перехода из состояния в состояние

  3. Задача: проверить достижимость И → Ф или минимальную длину преобразования И → … → Ф

  4. Дополнительные ограничения

     • Объём входных данных ~ N^a (a==2 в случае простого лабиринта)

     • Размер истории ~ N^a (состояния не зависят от пути)

• Алгоритмы генерации простого лабиринта

Домашнее задание

1. Задача обхода лабиринта: см. предыдущее задание

   • 2013-01-25.lab.py

2. Генератор: см. материалы прошлого года, не забыть о генерации лабиринта с циклами

   • 2013-01-25.labgen.py

3. Колесо разделено на K секторов, в каждом из которых находится число P₀, P₁, … , P_K. Вначале стрелка указывает на P₁, после поворота колеса — на P₂ и так далее по кругу (…,P_k-1,P_K, P₁, P₂,…). Вводится число A, На i-м шаге выбирается произвольная арифметическая операция среди «+», «-» и «*» и применяется к A и P_i (более точно A_i=A_i-1 +/-/* P_i%K ), после чего колесо поворачивается. Написать программу, которая определяет минимальное количество действий, которые нужно проделать для получения числа B из числа A (A<B). P_i, A, B и промежуточные значения не меньше 0 и не больше B*B.

   • Другая формулировка: в формуле (((…((A×P₁)×P₂)…×P_K-1)×P_K)×P₁)×P₂)…)=B вместо знаков «×» расставить знаки арифметических операций таким образом, чтобы равенство выполнялось, а длина формулы была минимальной.

   • В случае, когда {P_i}={1…K}

   • В случае, когда {P_i} — произвольное, но гарантируется достижимость B из A

   • В случае, когда достижимость не гарантируется (возможен ответ "B нельзя получить из A")

   • Для четырёх операций: «+», «-», «*» и «//», где // — это целочисленное деление (соответственно, X/Y*Y может быть не равно X)

   • … + вывести формулу

   • Рассмотреть случай, когда на числа и промежуточные результаты не накладывается ограничений. Можно ли определить, что B недостижимо из A?

   Ввод: K чисел через пробел, на следующей строке — A и B

   Вывод: количество операций (или формула, если это требуется), НЕТ при недостижимости

Условные обозначения

• — тема по Linux

• ­— тема повышенной сложности

• — теоретическое задание

• — тема для самостоятельного изучения

CategoryClass CategoryVmsh