Дополнительное задание

Задания:

  1. EJudge: NiceLab 'Красивый лабиринт'

    Написать генератор «достаточно случайного» двумерного лабиринта, в котором стены представлены символом '#', а комнаты/коридоры — '.'. Программа вводит три числа через запятую — ширину и высоту лабиринта (нечётные), а также — должен ли он быть проходим из левого верхнего угла в правый нижний (1 — должен, 0 — нет). Выводится сам лабиринт. Разумеется, не такой, как в примере, тестирующая программа будет проверять следующтие свойства:

    • в проходимом лабиринте не должно быть недоступных комнат,
    • не должно быть сплошных блоков из стен или комнат размером 2×2
    • лабиринт может не иметь циклических/альтернативных путей (в том числе, может никогда их не иметь)

    • для построения непроходимого дабиринта недостаточно заткнуть вход или выход в районе левого верхнего/правого нижнего углов (это можно получиться только случайно)
    • алгоритм не обязан быть «полностью» случайным (в примерах видно, что мой алгоритм любит ходить вдоль стен :) )

    • (далее см. подсказки)
    Input:

    13,11,1
    Output:

    .#...#.......
    .###.#.#.###.
    ...#...#.#.#.
    ##.#####.#.#.
    .#.....#.#...
    .#####.#.####
    ...#.#.#.....
    .#.#.#.#.###.
    .#...#.#.#...
    .#####.###.#.
    ...........#.
  2. EJudge: TuringMachine 'Машина Тьюринга'

    Написать программу, эмулирующую машину Тьюринга. Программа читает со стандартного ввода программу для машины Тьюринга в табличном виде (синтаксис описан тут, с упрощением: полностью «пустых» правил, как в третьем примере, быть не должно), если в очередной строке не содержится пробелов — она последняя, и содержит входное слово. Выводится результат работы МТ (предполагается, что программа применима к этому слову). Если программа не заканчивается после 100000 шагов, эмулятор останавливается без какой-либо диагностики. Пояснение к синтаксису см. в подсказках:

    Input:

          a      b     c      _      #
    0    ,R,    ,R,   ,R,   #,L,1   ,N,
    1    ,L,    ,L,   ,L,    ,R,2   ,L,
    2   _,R,   _,R,3 _,R,4   ,R,!  _,R,!
    3    ,R,    ,R,   ,R,   b,L,1   ,R,
    4    ,R,    ,R,   ,R,   c,L,1   ,R,
    bacab
    Output:

    bcb
  3. EJudge: DodgsonDet 'Определитель'

    Ввести квадратную целочисленную матрицу построчно и посчитать её определитель (например, методом конденсации Доджсона). Размер матрицы (1<N<14) определяется длиной её нулевой строки. Описание предлагаемого метода в подсказках. Пользоваться numpy нельзя:)

    Input:

    8, 8, 5, 6, 3
    1, 4, 4, 9, 0
    9, 6, 7, 7, 3
    4, 1, 0, 1, 4
    6, 7, 9, 7, 3
    Output:

    2784

LecturesCMC/PythonIntro2019/AdditionalTask (last edited 2020-01-14 19:50:57 by FrBrGeorge)