АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Задача 9

Читайте также:
  1. C) Любой код может быть вирусом для строго определенной среды (обратная задача вируса)
  2. БУДУЩЕЕ – ПЕРЕД ВАМИ СТОИТ НЕЛЕГКАЯ ЗАДАЧА. В ОДИНОЧКУ ВЫ С НЕЙ НЕ СПРАВИТЕСЬ.
  3. Вопрос 10. Задача
  4. Вопрос 18. Задача
  5. Вопрос 24. Задача
  6. Вопрос 26. Задача
  7. Вопрос 36. Задача
  8. Вопрос 38. Задача
  9. Вопрос 40. Задача
  10. Вопрос 42. Задача
  11. Вопрос 6. Задача
  12. Задача 1

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

Идея решения (условие останова). На ленте есть два исходных массива штрихов.

Штрихи начинаем стирать с левого конца массива m. И поочередно стираем самый левый штрих в массиве m и самый правый штрих в массиве n. Но прежде чем стереть правый штрих в массиве n, проверяем, единственный он (т.е. последний, который надо стереть) или нет.

Опишем сначала состояния машины Тьюринга, которые необходимы для решения нашей задачи, а затем составим программу-таблицу.

Состояние q 1 — поиск разделителя между массивами штрихов при движении справа налево;

состояние q 2 — поиск левого штриха в массиве m;

состояние q 3 — удаление левого штриха в массиве m;

состояние q 4 — поиск разделителя при движении слева направо;

состояние q 5 — поиск правого штриха в массиве n;

состояние q 6 — проверка единственности этого штриха в массиве n, т.е. определяем, был ли он последним;

состояние q 7 — если он был последним, то останов, иначе переход на новый цикл выполнения алгоритма.


1 | 2 | 3 | 4 | 5 | 6 | 7 |

Поиск по сайту:

Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.002 сек.)