Третье домашнее задание (1127056)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Домашнее задание 3, последнееОбщее описаниеИмеется N городов, соединённых дорогами. Робот начинает движение в нолевом городе и перемещается между городами по дорогам согласно заложенной в него программе. Основная цель: проверить, может ли робот выполнить заложеннуюв него программу.Формат результатовЕсли робот может выполнить свою программу, то выдать “YES” в стандартный поток вывода и вернуть 0, иначевыдать “NO” и вернуть −1.ДорогиСеть дорог описывается в виде ориентированного графа. Вершины графа — неотрицательные целые числа, описывающие города (от 0 до N − 1, где N — число вершин графа).

Дуги графа — дороги, соединяющие эти города. Вершины идуги графа помечены неотрицательными целыми числами (типами городов и типами дорог соответственно).Граф считывается из файла, флаг: “-g <имя файла >”. Формат описания графа:• в первой строке записаны четыре числа:– число вершин графа (N),– число дуг графа (M),– верхняя граница меток вершин (P) и– верхняя граница меток дуг (Q);• в следующей строке записаны N чисел: метки вершин графа в порядке нумерации (целые числа от 0 до P);• в каждой из M следующих строк записаны три числа:– вершина, из которой исходит дуга– метка дуги (целое число от 0 до Q)– вершина, в которую ведёт дугаКомандыКоманды робота считываются из файла, флаг: “-c <имя файла >”.

В каждой строке файла записана одна команда.Команды имеют следующий вид:1. move <спецификация > — сдвинуться вперёд по исходящим дугам согласно спецификации2. back <спецификация > — сдвинуться назад по входящим дугам согласно спецификации3. check <единичная спецификация > — убедиться, что метка текущей вершины удовлетворяет единичной спецификацииСпецификация — это непустая конечная последовательность единичных спецификаций, разделённых двоеточием. Значение спецификации — последовательное движение согласно единичным спецификациям так, как они записаны слеванаправо.Единичная спецификация — это непустая конечная последовательность целых чисел, разделённых запятой, передкоторой может стоять ключевое слово not. Значение единичной спецификации:• без not: множество записанных в ней чисел;• с not: множество всех чисел, не указанных в спецификации;• в рамках команд move, back: сдвинуться по дуге, метка которой входит в множество, описываемое спецификацией;• в рамках команды check: убедиться, что метка текущей вершины лежит в множестве, описываемом спецификацией.ПримерыВходной формат графа:(начало файла)4 5 2 31 1 2 20 1 10 2 21 2 21 3 32 1 3(конец файла)Предложенная запись во входном формате описывает следующий граф:1111 032223 212Ответ “YES” для такого графа должен быть выдан для следующих программ:(перейти по дуге типа 1 )move 1(убедиться, что текущая вершина имеет тип 1 )check 1(убедиться, что тип текущей вершины — 1 или 2 )check 1,2(перейти по дуге типа 1 в вершину типа 1 )move 1check 1(перейти по дуге типа 1 или 2 в вершину типа 1 )move 1,2check 1(перейти по дуге типа 1 или 2 в вершины типа 2 )move 1,2check 2(перейти по дуге типа 2, а затем — типа 1,и убедиться, что получена вершина типа 2 )move 2:1check 2(перейти по дуге типа 1 или 2, затем — типа 1 или 3,и убедиться, что получена вершина типа 2 )move 1,2:1,3check 2(перейти по дуге любого типа, кроме 3, а затем по дуге типа 3 )move not 3:3(перейти по дуге типа 1 или 2, а затем по дуге любого типа, кроме 2 )move 1,2:not 2(перейти по дуге типа 1, затем — 3,потом вернуться по дуге типа 1, затем — 2,и убедиться, что получена вершина типа 1 )move 1:3back 1:2check 1Ответ “NO” для такого графа должен быть выдан для следующих программ:(убедиться, что начальная вершина имеет тип 2 )check 2(сдвинуться по дуге типа 3 )move 3(вернуться по дуге типа 1 )back 1Оценка задания• 50 баллов: реализация графа как набора BDD, анализ графа как применение операций к BDD.• 20 баллов: поддержка команды check <число >.• 30 баллов: поддержка команды move <число >.• 10 баллов: разбор команд робота на основе регулярных выражений.• 10 баллов: поддержка запятой в команде move, основанная на регулярных выражениях.• 10 баллов: поддержка запятой в команде check, основанная на регулярных выражениях.• 10 баллов: поддержка двоеточия в команде move, основанная на регулярных выражениях.• 10 баллов: поддержка оператора not в командах move, check, основанная на регулярных выражениях.Суммарное число баллов за задание: 150.

Характеристики

Тип файла PDF

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

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

Список файлов учебной работы