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

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

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

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

  3. Колесо разделено на 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

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

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


CategoryClass CategoryVmsh

LecturesVMSH/Python/2013-01-25 (последним исправлял пользователь FrBrGeorge 2013-02-01 17:22:22)