Скачиваний:
89
Добавлен:
15.06.2014
Размер:
28.16 Кб
Скачать

КОНТРОЛЬНОЕ ЗАДАНИЕ 1

Задание состоит из п.п. А, Б С. Сначала прочитайте все внимательно.

А. Написать правила машины Тьюринга для решения указанной задачи.

ВАРИАНТЫ.

  1. На вход поступает последовательность из 0 и 1. Машина должна записать ее в обратном порядке. Пример 0001110 заменяется на 0111000.

  2. На вход поступает последовательность из 0 и 1. Машина должна заменить каждый второй 0 на 1. Пример. 000111 заменяется на 010111.

  3. На вход поступает последовательность из 0 и 1. Машина должна выдать 0 если число 0-ей больше и 1 – в противном случае. Пример. 000011. Машина выдает 0.

  4. На вход поступает последовательность из 0 и 1. Машина должна выдать 1, если не встречается комбинация 011 в данной последовательности и 0 – в противном случае. Пример 0001001. Машина выдает 1.

  5. На вход поступает последовательность из 0 и 1. Машина должна заменить каждые два подряд идущих нуля одной единицей. Пример 00010100 заменяется на 101011.

  6. На вход поступает последовательность из 0 и 1. Машина должна выдать 1, если число пар 01 четное, и 0 – если нечетное. Пример 001001 выдаем 1.

  7. На вход поступает последовательность из 0 и 1. Машина должна поменять местами соседние элементы по парам. Пример. 0100101001 заменяется на 1000010110.

  8. На вход поступает последовательность из 0 и 1. Машина должна заменить каждую единицу на 01. Пример. 00110010 заменяется на 00010100010.

  9. На вход поступает последовательность из 0 и 1. Машина должна дописать к ней слева единицу. Пример. 011001 заменяется на 1011001 (слева появилась 1).

Б. Для демонстрации правильности работы Вашей машины Тьюринга написать программу на Паскале или С, которая работает по правилам Вашей машины Тьюринга, чтобы можно было убедиться в правильности Вашей машины. Текст программы приложить к отчету.

С. Ваш вариант определяется так. Номер Вашей зачетки делите на 9 и берете целочисленный остаток, к которому добавляете 1. Пример. Пусть номер зачетки 542402-16. Берете число 54240216 и делите на 9. Получаете в остатке 6. Номер Варианта= 6+1=7.